[백준 알고리즘] 10870 피보나치 수 5

 

 재귀 

: 원래의 자리로 되돌아가거나 되돌아옴

다시 자신의 함수를 호출하는 것을 재귀 함수라고 생각하면 쉽다.

 

재귀 함수를 작성할 때 중요한 것이 2가지가 있다.

1. base case를 만들 것

2. 스택이 줄어들어야 할 것

 

문제:    

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

풀이방법:    

int fibo(int n){
    if( n == 0){
        return 0;
    }else if (n == 1){
        return 1;
    }else{
        return fibo(n-1) + fibo(n-2);
    }
}

문제의 일부)

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

 

1. base case를 만들 것

    if( n == 0){
        return 0;
    }else if (n == 1){
        return 1;
    }

--> 프로그램이 끝이 나야하니까 계속적인 호출을 무한 반복을 해서는 안된다. 호출의 끝을 만들어줘야 한다 ! 피보나치 수열의 경우에는 n이 0인 경우와 1인 경우 모두 작성해주어야 한다.

 

2. 스택이 줄어들어야 할 것

else{
        return fibo(n-1) + fibo(n-2);
    }

--> 피보나치의 기본 식이 Fn = Fn-1 + Fn-2(n ≥ 2)이기 때문에 위와 같이 재귀 함수를 이용해 코드를 작성했다.

 

작성한 코드는 다음과 같다.

#include <iostream>
using namespace std;

int fibo(int n){
    if( n == 0){
        return 0;
    }else if (n == 1){
        return 1;
    }else{
        return fibo(n-1) + fibo(n-2);
    }
}

int main() {
    int n;
    cin >> n;
    int fibo_answer = fibo(n);
    cout << fibo_answer<<"\n";
    return 0;
}

성공한 사진!