재귀 함수 이론 정리와 피보나치 수열

재귀함수 : 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 따라서 순환적으로 정의된 문제나 알고리즘을 풀기 적합하다. 예를들어 팩토리얼, 피보나치수열, 이항계수, 이진트리, 이진탐색, 하노이탑 문제를 풀기 적절하다.

 

재귀함수는 호출부분과 멈추는 부분으로 나뉘어진다. 멈추는 부분이 없으면 무한히 호출하게 된다.

 

장점: 알고리즘을 명확하고 간결하게 쓸 수 있다.

 

단점: 함수호출을 여러번 하므로 메모리와 속도면에서 성능이 떨어진다.

 

반복문보다 재귀가 더 빠른 경우가 있다. 재귀함수는 재귀호출을 할 때마다 더 작은 문제로 쪼개지는데, 선형적으로 작아진다면 시간복잡도는 O(n)으로 반복문과 동일하다. 문제를 반으로 쪼개서 해결하는 경우 시간복잡도는 O(logn)으로 효율적이다.

 

Head Recursion : 재귀 호출이 메소드 첫 부분에서 호출된다. 반복문으로 바꾸기 어렵다.

 

Tail Recursion : 재귀 호출이 메소드 마지막 부분에서 호출된다. 메소드 내 모든 Statement를 실행하고 다시 자기 자신을 호출하기 때문에 반복문으로 바꾸기 쉽다.

 

 

메모이제이션을 이용한 피보나치 수열. look_up_table이 없다면 계산량이 굉장히 많아진다. 만약 멀티스레딩으로 구현한다면 look_up_table을 critical section으로 정의해야하는지 궁금하다. look_up_table은 값이 추가만 되므로 상관없을 것같다.

#include <iostream>
#include "Timer/Timer.h"

int look_up_table[100];

int fibonacci(int n){
    if(look_up_table[n]) {
        return look_up_table[n];
    }
    else if(n<=2){
        return 1;
    }
    return look_up_table[n] = fibonacci(n-1) + fibonacci(n-2);
}


int main() {
    std::fill_n(look_up_table,100,0);
    kh::Timer timer;
    std::cout << fibonacci(46) << std::endl;
    timer.elapsed();
    return 0;
}