02-1. 함수의 재귀적 호출의 이해

재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수

void recursive(void)
{
    printf(“Recursive call! \n”);
    recursive();
}

함수를 구성하는 명령문은 CPU로 이동(복사)이 되어서 실행된다.

재귀의 탈출 조건

#include <stdio.h>

void Recursive(int num)
{
    if (num <= 0) // 재귀의 탈출 조건
    {
        return; // 재귀의 탈출!
    }
    printf("Recursive call! %d \n", num);
    Recursive(num-1);
}

int main(void)
{
    Recursive(3);
    return 0;
}

재귀함수의 디자인 사례

1. 팩토리얼
   정수 n의 팩토리얼 : n! = n x (n-1) x (n-2) x … x 3 x 2 x 1
   
   

• n 이 1 이상인 경우

if(n >= 1) return n * factorial(n-1)

• n 이 0인 경우

if(n == 0) return 1;

factorial 함수

#include <stdio.h>
int Factorial(int n)
{
    if(n == 0) return 1;
    else return n*Factorial(n-1);
}

02-2. 재귀의 활용

피보나치 수열 : Fibonacci Sequence

피보나치 수열의 전개 : 0, 1, 1, 2, 3, 5, 8, …
앞의 것 두개를 더해서 현재의 수를 만들어가는 과정

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

#include <stdio.h>
int Fibo(int n)
{
    if(n == 1) return 0;
    else if(n == 2) return 1;
    else return Fibo(n-1) + Fibo(n-2);
}

피보나치 함수의 전개 과정

이진 탐색 알고리즘

이진 탐색 알고리즘 패턴
1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

탐색의 실패
탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우

#include <stdio.h>
int BsearchRecur(int ar[], int first, int last, int target)
{
    int mid;
    if(first > last)
    {
        return -1;  // -1의 반환은 탐색의 실패를 의미
    }
    mid = (first + last) / 2;  // 탐색 대상의 중앙을 찾는다
    
    if(ar[mid] == target)
    {
        return mid; // 탐색된 타겟의 인덱스 값 반환
    }
    else if(ar[mid] > target)
    {
        return BsearchRecur(ar, first, mid-1, target);
    }
    else
    {
        return BsearchRecur(ar, mid+1, last, target);
    }
}

02-3. 하노이 타워 : The tower of Hanoi

하노이 타워 문제의 이해

하나의 막대에 쌓여 있는 원반을 다른 원반에 그대로 옮기는 법

조건

• 원반은 하나에 하나씩만 옮길 수 있다.
• 옮기는 과정에서 작은 원반의 위에 큰 원반이 올라갈 수 없다.

과정

두 원반을 막대 B에 가져다 놓으면 3번 원반을 막대 C에 가져다 놓을 수 있다

반복패턴

세 원반을 막대 B에 가져다 놓으면 4번 원반을 막대 C에 가져다 놓을 수 있다

하노이 타워 문제의 해결

1. 작은 원반 n-1개(맨 아래의 원반을 제외한 나머지 원반)를 A에서 B로 이동
2. 큰 원반 1개(맨 아래의 원반)를 A에서 C로 이동
3. 작은 원반 n-1개(위의 1단계에서 옮겨진 원반)를 B에서 C로 이동

void HanoiTowerMove(int num, char from, char by, char to)
{
    …
}

num개의 원반을 by를 거쳐서 from에서 to로 이동한다

탈출 조건
이동해야 할 원반의 개수가 1개인 경우

#include <stdio.h>
void HanoiTowerMove(int num, char from, char by, char to)
{
    if(num == 1)
    {
        printf("원반 1을 %c에서 %c로 이동\n", from, to);
        
    }
    else
    {
        HanoiTowerMove(num-1, from, to, by);
        printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
        HanoiTowerMove(num-1, by, from, to);Think
    }
}