본문 바로가기

(비정기) Mr.K's Post/Weekly paper

Recursion vs. Iteration : Round 1

부제 : 그대, 피보나치 수열이라고 들어보았는가?

Fibonacci Numbers

Consider the following sequence of numbers, which begins with two 1's and where each successive term is equal to the sum of the preceding pair of terms. These numbers, called Fibonacci numbers, are arranged in the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... .

If F1 = 1, F2 = 1, F3 = 2, F4 = 3, and so on, then this sequence can be written recursively as

Fn+2 = Fn+1 + Fn    for all nN, where F1 = F2 = 1.
(위 내용은 A Friendly Introduction to ANALYSIS 2/e에서 일부 발췌했음을 알려드립니다)


피보나치 수열이란, 첫째 항과 둘째 항이 모두 1이고 그 뒤로는 직전의 두 항의 합으로 이루어진 수열입니다
(쓰는 곳에 따라 0번째(F0) 항을 0으로, 1번째(F1) 항을 1로 놓고 얘기하기도 하지만, 여기서는 1, 1, 2, …인 형태로 얘기합니다)

수열 자체의 알고리즘이 매우 간단하여 프로그래밍을 배우는 사람이라면 꼭 한번은 보고 지나가게 되는 내용입니다

이것의 구현 방법은 재귀(Recursion)와 반복(Iteration)이 있습니다, 먼저 재귀부터 보시죠




간단하죠? 함수 자체가 위의 점화식의 모양대로 호출이 됩니다
허나 이것의 경우 단점이 있는데,

재귀로 자기 자신을 2번이나 호출하기 때문에 처음의 input이 크면 클 수록 호출회수가 많아져서 그만큼 시간이 오래 걸린다는 것,
또 하나는 함수를 계속 호출하는 것이기 때문에 함수를 위한 메모리가 부족하면 원하는 결과를 얻을 수 없다는 것입니다

메모리에 대해서는 잘 모르니 저정도만 언급하기로 하고,
input이 적당히 커지면 실행시간이 얼마나 오래걸리는지 보도록 하죠

사용자 삽입 이미지

F40을 재귀로 구하는 프로그램입니다
10회 실행 후 평균을 재었더니 9.3156초가 나왔습니다

반복시의 결과는 아래에서 보기로 하죠




함수의 body부분이 위의 점화식만큼 간단하지는 않습니다
비교를 용이하게 하기 위해 base case는 재귀와 같게 하였습니다

n이 3 이상일 때 if문 내의 for문이 작동하는데
int형 변수의 선언이 있긴 하지만 재귀 때와 달리 메모리의 소비가 그리 크진 않을 것 같습니다

그리고 함수의 추가 호출도 없이 for문 내에서 모든 것을 해결하고 있으니
짐작하시기에도 이게 더 빠를 것 같다는 느낌이 들지 않나요?

확인해봅시다

사용자 삽입 이미지

보이십니까? 이 차이가;

재귀 때의 40과 비교하기 위해 일부러 4×10ⁿ 형태의 것들만 입력해봤는데
심지어 4억번째 값을 구하기 위해 함수호출을 하여도 재귀 때의 40번째 값을 구하기 위한 것보다 약 3배정도 빠르죠 (2.656초;)


일반적인 경우, 재귀와 반복이 비슷한 수준일 것으로 추측되나
피보나치에서는 재귀의 명백한 패배입니다 ㅠ

다음번에는 재귀가 반복보다 더 나은 경우를 가지고 찾아오겠습니다 (__)

(포스팅 소요시간 : 약 80분)