[Python] recursive call : Fibonacci Sequence

Recursive call의 경우, 특정 함수가 내부에서 자기자신을 다시 호출하는 것을 가르킴.

다음과 같은 재귀적인 수식을 있는 그대로 작성하게 해준다는 장점은 있지만,

속도 및 메모리 사용 등의 측면에서는 그리 환영받지는 못함 (때문에 많이 사용되지 않음).

$$
f(t) = f(t-1) + ...
$$

$f(t)$를 정의하는데에 같은 함수가 사용되는 경우를 recursive call로 작성하면 매우 직관적인 구현이 가능하다.

대표적인 예로 Fibonacci sequence를 들 수 있다.

$$
f(0) = 0, \\
f(1) = f(2) = 1 \\
f(n) = f(n-1) + f(n-2) \text{ , where }n >2
$$

---

Python 구현 : Recursive call 이용한 경우.

def fibonacci_recur(num):
  ret = -1
  if num <0:
    print('ERROR: negative is not supported')
  elif num <=1 :
    ret = num
  elif num == 2: 
    ret = 1      
  else: 
    ret = fibonacci_recur(num-1) + fibonacci_recur(num-2) 
  return ret 


for i in range(0,10,1):
  # print(i)
  print(fibonacci_recur(i), end=",")
print('\n')

---

Python 구현 : while 문을 이용한 경우.

def fibonacci_loop(num):
  if num == 0 or num == 1:    
    return num
  elif num == 2:
    return 1
  else:
    length = num - 2

    first = 1
    second = 1    

    while length > 0:
      tmp = second
      second = first + second
      first = tmp

      length -=1    
    return second

for i in range(1,10,1):
  # print(i)
  print(fibonacci_loop(i), end=",")
print('\n')

사실 while문을 이용한 경우, fibonacci_loop함수 내에서 수열을 출력하도록 수정하면 훨씬 효과적으로 피보나치 수열을 출력할 수 있다. (위의 경우, fibonacci_loop에서는 수열을 출력하기 보다 최종값만을 구하는 형태임).

 

즉, while문을 이용하여 fibonacci_print함수를 만들고 호출시 argument로 수열을 출력해줄지 최종 값만 반환할지를 선택케 하는 형태로 만들면 효과적이다. 이 구현은 간단하니 한번 만들어 보길...