사실 피보나치수를 재귀함수로 구하는 건 굉장히 비효율적입니다
반복문을 사용해보는 건 어떨까요..?
1. fib(n)을 계산하려면 fib(n-1)와 fib(n-2)를 계산해야 합니다
2. 1의 fib(n-1)을 계산하려면 fib(n-2)와 fib(n-3)을 계산해야 합니다
3. 1의 fib(n-2)를 계산하려면 fib(n-3)과 fib(n-4)를 계산해야 합니다
4. 2의 fib(n-2)를 계산하려면 fib(n-3)과 fib(n-4)를 계산해야 합니다 (3이랑 똑같은거 한번 더 함)
최종적으로 fib(n)을 재귀함수로 구하려면 fib(n-1)을 1번, fib(n-2)를 2번, fib(n-3)을 3번, fib(n-4)를 5번, fib(n-5)를 8번, ... n이 커질수록 계산 횟수가 기하급수적으로 증가합니다
