재귀함수 (팩토리얼, 피보타치 수열, 하노이 타워)

자기 자신을 호출하는 함수 

 

장점 : 문제 해결을 단순화시킨다.

단점 :  성능 저하 (호출의 반복)

 

주의점

– 호출할 때마다 범위를 줄여가야 한다.

    •  줄이지 못하면 무한루프 -> 프로그램 비정상 종료 (메모리 부족)

– return을 통한 복귀가 있어야 한다.

   •  호출된 수만큼 복귀해야 한다.

 

팩토리얼 : 4! = 1 *2 * 3* 4

 n! = n * (n-1)!

int  factorial (int  n)
{
    if (n == 0) return 1;  // 0! = 1 
    return  n * factorial (n-1);   //  fact (n) = n * fact(n-1) 
}
 
int main( )
{
    int  i = 4;
    printf(“%d! = %d\n”, i, factorial(i));
}

 

피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

 

fib(n) = 0 (n=1)

           1 (n=2)

        fib(n-1)+fib(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); //재귀 함수
}

int main(void)
{
  int  i;
  for (i = 0; i < 15; i++)
    printf("%d ", Fibo(i));

  return 0;
}

 

하노이의 타워 :

출발점의 원반을 목표점으로 옮겨라

–경유점을 써도 좋다.

–한번에 하나의 원반만 옮기고, 작은 원반 위에 큰 원반이 올 수 없다.

 

하노이의 타워

void hanoi(int n, char from, char by, char to)
{
    if (n == 1)           // 블록이 하나 뿐일 때에는 그냥 옮기면 된다.
        printf("move 1 from %c to %c\n", from, to);
    else {
        hanoi(n - 1, from, to, by);    // N-1개의 원반 전체를 경유지로 옮기고
        printf("move %d from %c to %c\n", n, from, to); 
                                       //  n번 블록을 목적지로 옮기고
        hanoi(n - 1, by, from, to);    // 경유지에 있는 n-1개의 원반 전체를 목
                                       // 목적지로 옮긴다.
    }
}
 
int main(void)
{
    hanoi(8, 'A', 'C', 'B');
}