2# | 재 귀(Recursion)

재귀 

팩토리얼

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

피보나치 수열

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

#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. 작은 원반 n-1 개를 A --> B로 이동 

2. 큰 원반 1개를 A --> C로 이동

3. 작은 원반 n-1개를 B ->C 로 이동  

#include<stdio.h>
 
int HanoiTower(int num, char from , char by , char to)
{
    if (num == 1)
    {
        printf("원반을1 을 %c 에서 %c로 이동 \n ", from , to);
        
    }
    else
    {
        HanoiTower(num-1,from,to,by);
        printf("원반 %d를 %c -> %c 로 이동 \n", num,from,to);
        HanoiTower(num-1,by,from,to);
        
    }
}
int main(void)
{
    // 막대 A의 원반  3개를 막대 B 를 경유하여 막대 C로 옮기기 
    HanoiTower(3,'A','B','C');
    return 0; 
}