재귀 팩토리얼 피보나치 구현

2019.01.03.

 

먼저 책에서는 main함수에서 Recursive함수를 계속 호출하는것으로 재귀함수의 개념에 대해서

설명해 주었다. 재귀함수에서 중요한것은 탈출 조건이다.

 

 이를 응용하여 가장 기본적인 재귀함수 의 예시인

 

1) 팩토리얼

 

2) 피보나치 수열

 

3) 하노이 탑

 

들의 코드를 짜보고 구현해보고자 하였다.

 

 

 

먼저 팩토리얼은 다음과 같다

 

0! = 1

1! = 1

2! = 2

3! = 6

4! =24

 

직접 써보면서 반복되는 부분을 확인하고 반환하기 전에 자기자신을 곱해주는 형식으로 만들어주었다.

 

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>  
 
 
int main()
{
    int num;
    int result;
 
    scanf("%d", &num);
 
    result = Factorial(num);
 
    printf("%d", result);
 
    return 0;
}
 
int Factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    return n * Factorial(n - 1);
}

 

관련된 문제로 https://www.acmicpc.net/problem/10872이 있어서 확인 할 수 있었다.

 

 

 

두번째로 피보나치 수열은 너무 많이 본 구조라서 쉽게 구현할 수 있었다.

 

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>  
 
 
int main()
{
    int num;
 
    scanf("%d", &num);
 
    for (int i = 1;i < num+1;i++)
    {
        printf("%d  ", Fibo(i));
    }
 
    return 0;
}
 
int Fibo(int n)
{
    if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }
    else
    {
        return Fibo(n - 1) + Fibo(n - 2);
    }
}

 

 

 

 

참고: 윤성우의 열혈 자료구조