[Recursion] Fibonacci

for loop : O(n)

recursion : O(2^n)

재귀는 시간복잡도가 기하급수적으로 늘어나기 때문에 큰 자료에는 전혀 적합하지 않다.

하지만 자료가 크지 않고, 데이터에 사용되는 연산이 모두 동일한 경우에는 재귀만큼 가독성이 좋고 간편한 것이 없다.

특히 트리같이 같은 연산을 중복하여 훑는 경우에는 작은 모듈을 반복하듯이 처리할 수 있다.

 

모든 재귀는 반복문으로 대체할 수 있지만, 재귀만이 갖는 효용성은 Merge Sort, Quick Sort, Tree Traversal, Graph Traversal을 쉽게 처리한다.