3주차: 트리와 재귀

출처
📚 쉽게 배우는 자료구조 with 파이썬
📚 이것이 자료구조+알고리즘이다 with C언어
✏️ 기존에 공부했던 내용
💻 스택 - 상속 구현 참고한 블로그

---

지난 포스팅에 이어서!

재귀 (recursion)

대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출 기능을 지원한다. 수학 시간에 배웠던 점화식과 귀납법이 재귀의 틀 안에 속한다.

재귀 구조의 예

피보나치 수열

Fn = Fn-1 + Fn-2 (n ≥ 2)

첫 두 항은 1이고, 나머지 항은 각각 직전의 두 항을 더한 것이다.
이를 의사코드로 구현하면 다음과 같다.

fib(n):
	if (n=1 or n=2)
    	return 1
    else
    	return fib(n-2) + fib(n=1)

하지만 이는 시간복잡도 측면에선 치명적인 코드이다. 한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문에, 시간복잡도가 지수함수적으로 증가한다.

❗️ 사실 재귀로 구현하는 피보나치 수열은 O(n^2)의 시간복잡도를 가진 대표적인 알고리즘이다. n이 100 이상이면 평생 값을 반환받지 못할 수도 있다.

이 문제를 다음과 같이 비재귀적으로 계산하면 시간복잡도가 획기적으로 줄어든다.

fib_fast(n):
	f[1], f[2] <- 1
    for i <- 3 to n
    	f[i] <- f[i-1] + f[i-2]
        return f[n]

재귀는 문제를 해결하는 유용한 도구지만, 잘못 쓰면 치명적이다. 복잡도를 고려하여 재귀를 사용하는 것이 유용할 경우에만 사용해야 한다.

---

재귀/비재귀 피보나치 문제풀이 링크