Data Structure - Recursion
Recursion이란?
동일한 함수의 되풀이, 점화식 S(n) = n + S(n-1)이 그 예시.
Recursion의 장단점을 살펴보기에 앞서 Recursion의 종류를 살펴보자.
1) Linear Recursion
함수 호출 시 동일한 함수가 최대 한번 되풀이 되는 것.
2) Binary Recursion
함수 호출 시 그 함수가 두번 되풀이 되는 것.
ex) 피보나치 수열
F(0) = 0
F(1) = 1
F(i) = F(i-1) + F(i-2) (for i>1)
3) Linear Recursion VS Binary Recursion at Fibonacci Algorithm
방금 위에서 보여주었떤 Binary Recursion을 이용한 피보나치 수열 알고리즘과 아래 Linear Recursion을 이용한 피보나치 수열 알고리즘을 비교해 보자.
Linear Recursion을 이용하여 피보나치 수열을 구하기 위해서는 총 k-1번 LinearFibonacci함수가 되풀이 된다 (k>1). 하지만 위의 BinaryFib함수를 살펴보면 BinaryFib(k)를 구하기 위해서는 BinaryFib(k-1)과 BinaryFib(k-2)가, 다시 그 둘을 구하려면 BinaryFib(k-2), BinaryFib(k-3) 을 구하고 더하는 과정과 BinaryFib(k-3)과 BinaryFib(k-4)를 구하고 더하는 과정이 진행되어야한다(k>4). k의 값이 커질수록 BinaryFib가 되풀이되는 횟수는 늘어나는데 식을 적어보면,
Count(BinaryFib(k))=Count(BinaryFib(k-1))+Count(BinaryFib((k-2)) (Count()는 괄호 안의 함수가 호출되는 횟수이다.)
BinaryFib(1) = BinaryFib(0) = 1 은 정의이므로 Count(BinaryFib(1)) = Count(BinaryFib(0)) = 1이다.
BinaryFib(2) = BinaryFib(1) + BinaryFib(0) = 2 이므로 Count(BinaryFib(2)) = 2이고
BinaryFib(3) = BinaryFib(2) + BinaryFib(1) = BinaryFib(1) + BinaryFib(0) + BinaryFib(1), 즉 Count(BinaryFib(3))= 4이다.
이를 토대로 Count(Binary(n))의 수열을 나열해보면 (n>=0) ( 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 .......)가 된다.
그래프를 그려서 살펴보면
LinearFibonacci의 기울기는 1인 반면, BinaryFib의 기울기는 n의 각 구간에 따라 0에서 1로, 1에서 2로.... 나중에는 BinaryFib(n-2)가 되므로 n이 3이상인 구간에서는 언제나 1보다 크다. 따라서 피보나치 수열을 계산할 경우, BinaryFib()보다는 LinearFibonacci() 함수를 쓰는게 더 좋은 알고리즘이다.
4) Recursive VS Iterative
그럼 이 Recursive 기술과 for,while등의 함수인 Iterative와 무슨 차이가 있을까?
처음에 언급했듯이 그 함수 정의 안에서 동일한 함수가 호출되는지가 내가 보기에 가장 큰 차이점인 것 같다.
그리고 부가적으로 자료에 Stack 구조도가 그려져 있고, Top of Stack과 Bottom of Stack에 각각 Most recently called function과 Initial function이 배정되어 있다는데, 그 옆의 Iteration에는 아마 그런 구조도가 없으니 Iteration시에는 Stack 영역에 쌓이지 않는 것 같다.
5) Recursion의 장단점
Recursion은 코드를 더 빨리 처리하지도, 더 적은 메모리공간을 사용하지도 않는다. 오히려 같은 함수를 다시 호출하는 만큼 더 느리게 처리되고, 더 많은 메모리공간을 사용한다. 그럼 왜 우리는 Recursion을 사용할까? Recursion을 사용하는 것이 코드를 훨씬 심플하게 적고 이해할 수 있기 때문이다. 예를 들어, Iteration, 즉 for나 while을 사용하여 팩토리얼값을 구하는 코드를 짜는 것 보다는 Recursion을 사용하는게 조금 더 느리고 공간을 많이 차지하더라도 심플하게 코드를 적고, 이해할 수 있다는 것이다.
