피보나치 (Fibonacci) 수열과 재귀(Recursive) 알고리즘

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

피보나치(Fibonacci) 수열

첫째 및 둘째 항이 1이며(또는 첫째 항이 0일 수도 있다),

그 뒤의 항들은 바로 앞 두 항의 합인 수열이다. 

 

반복(Repetitive) 알고리즘

단순하게 반복문(for문, while문) 사용하여 같은 작업을 수행한 후, 해답을 구하는 알고리즘

반복 알고리즘에 의한 함수 호출은 기본적으로 한 번만 이루어진다. 

 

재귀(Recursive) 알고리즘

피보나치 수열을 구하는 재귀 알고리즘을 시각화한 이진 트리(binary tree)

같은 내용을 담고 있는 함수가 중복해서 호출되는 것을 알 수 있다. 

이처럼 재귀 알고리즘은 중복되는 연산을 수행하는 경우가 존재하기 때문에 이를 고려하여 재귀 연산을 활용해야 한다.

 

또한 재귀 함수는 무조건 특정 입력에 대해서는 재귀적으로 호출하지 않고 종료되어야 한다. 

 

그렇지 않다면, 재귀 함수는 무한 루프(loop)에 빠질 수 있기 때문이다.

 

기본적으로 재귀 알고리즘은 적재적소에 사용하면 코드를 깔끔하게 정리할 수 있다. 

하지만 함수 호출은 꽤나 비용이 큰 연산이기 때문에 메모리와 시간 측면에서는 손해를 본다는 단점이 존재한다. 

 

아래는 피보나치 수열을 재귀 연산으로 구현한 코드이다.

int recursiveFibonacci(int n){
    if(n <= 1)
    	return n;
    else 
        return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
}