피보나치 시퀀스 및 재귀 알고리즘

피보나치 수열

첫 번째 및 두 번째 항은 1(또는 첫 번째 항은 0일 수 있음),

후속 용어는 이전 두 용어의 합계입니다.

반복 알고리즘

간단한 반복문(for문, while문)을 이용하여 같은 작업을 수행한 후 해를 찾는 알고리즘

반복 알고리즘에 의한 함수 호출은 기본적으로 한 번만 수행됩니다.

재귀 알고리즘

같은 내용을 담고 있는 함수가 반복적으로 호출되는 것을 볼 수 있습니다.

이와 같이 재귀 알고리즘은 때때로 중복 연산을 수행하므로 이를 고려하여 재귀 연산을 사용해야 합니다.

또한 재귀 함수는 특정 입력에 대해 재귀적으로 호출하지 않고 항상 종료해야 합니다.

그렇지 않으면 재귀 함수 무한 루프에 빠질 수 있기 때문에

기본적으로 재귀 알고리즘은 올바른 위치에서 사용하면 코드를 정리할 수 있습니다.

그러나 함수를 호출하는 것은 상당히 비용이 많이 드는 작업이므로 메모리와 시간 면에서 손해를 보는 단점이 있습니다.

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

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