[프로그래밍언어론] 23. 파이썬 피보나치 수열 재귀

지난 강좌의 재귀(Recursion)와 꼬리 재귀(Tail Recursion)로 피보나치 수열을 구현해보고 시간을 측정해보자.

 

---

 

먼저 파이썬에서 시간 측정은 time 모듈을 통해 할 수 있다.

import time
start_time = time.time()
.
.
.
end_time = time.time()
print(f"exec.time = {end_time-start_time}")

 

우리는 피보나치 수열에 40을 넣어보고 값을 구할때 까지의 시간을 측정해볼 것이다.

 

재귀

import time
start_time = time.time()

def fib(n):
	if n == 1 or n == 2:
		return 1
	else:
		return fib(n-1) + fib(n-2)
        
print("fib(40) = ", fib(40))

end_time = time.time()
print (f"exec.time = {end_time-start_time}")

결과

fib(40) = 102334155
exec.time = 29.930135011672974

시간은 대략 30초가 소요되었다.

 

---

 

꼬리재귀

import time
start_time = time.time()

def fib_tr(n, pp, p):
	if n == 1:
    		return n*p
	else:
		return fib_tr(n-1, pp+p, pp)
        
print("fib_tr(40) = ", fib_tr(40, 1, 1))

end_time = time.time()
print(f"exec.time = {end_time-start_time}")

결과

fib_tr(40) = 102334155
exec.time = 0.00000000000001

시간은 0초대이다.

 

---

 

꼬리재귀를 통해 효율적인 코드를 작성할 수 있음을 확인할 수 있다.