1. 피보나치 수열에서는 Recursion이 좋은 선택이 아니다.
2. 피보나치 수열은 이진 탐색을 통해서 재귀적으로 탐색할 수 있다.
3. 피보나치 수열은 한 번 콜 될 때마다 2개의 자식 함수를 호출하기 때문에 노드 개수의 worst 한 개수는 2^n개이다.
4. 트리에서 depth 는 첫 뿌리는 세지 않고 두 번째 층부터 1, 아래로 가면서 1씩 증가된다.
5. 이터레이션으로 피보나치 수열의 시간 복잡도를 구해 보면 T(n) = O(n)

여기서 코드가 세 줄이어도 곱하기 3 이렇게 생각할 필요가 없음. 어차피 상수배는 중요하지 않기 때문에.

1. Recursion 으로 구할 경우, T(n) = T(n-1) + T(n-2) + 1 → 이건 파스칼의 삼각형으로 풀 수 있음. 여기서 + 1 이 의미하는 바는 fib(n-1) + fib(n-2) 에서의 + 를 의미한다.
2. 하노이 탑

1. A 에서 C 로 넘어가는 과정. 이건 divide & conquer 로 해결할 수 있음. 서브 문제 두 단계로 나누어 보자.

1. A에서 B로 옮기는 과정 + B에서 C로 옮기는 과정 + A를 C로 옮기는 과정으로 분리할 수 있음.

1. 이걸 코드로 작성하면 이렇게 됨. 가운데 printf 의 경우, A에서 C 로 하나 옮기는 것을 의미한다. ?질문: pritnf 는 단순 출력이고 실제로 A에서 C 로 옮기는 것이 아닌데 이렇게 해도 되는 것인지!
2. T(n) = 2(T(n-1))+ 1 이 되고 T(1) = 1, T(2) = 2T(1) + 1 = 3, T(3) = 2T(2) + 1 = 7 = 2^2 + 2 + 1, T(4) = 2T(3) + 1 = 15 = 2^3 + 2^2 + 2 + 1 즉 T(n) = 2^n - 1 이 됨. 이는 Power computation 과 비교하면 엄청나게 복잡하다. T(n) = T(n/2) + 1 이기 때문에 인풋의 개수가 반으로 줄어들어 시행 횟수가 반으로 준다.
3. Hierarchial Structure of Recursion

1. 3개 디스크 옮기는 것 안에 2개 디스크 옮기는 것이 상속되어 있고 2개 디스크 옮기는 것 안에 1개 디스크 옮기는 것이 2개씩 상속되어 있다. 이러한 상속 구조를 hierarchial Structure Recursion → 프랙탈과 비슷한 구조이다.