[Python] recursive call : Fibonacci Sequence (and dynamic programming)

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

https://media.clear.uconn.edu/geospatial/workshops/Python/pythonlecturenotes/2d%20-%20for%20loops.pdf

 

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

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

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

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

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

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

---

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

def fibonacci_recur(num):
  ret = -1
  if num <0:
    print('ERROR: negative is not supported')
  elif num <=1 :
    ret = num      
  else: 
    ret = fibonacci_recur(num-1) + fibonacci_recur(num-2) 
 
  # # 다음이 원래 구현되는 방식임 (성능도 우수)
  # ret = -1
  # if num > 1:
  #   ret = fibonacci_recur(num-1) + fibonacci_recur(num-2)
  # elif num >= 0:
  #   return num
  # else:
  #   print('ERROR: negative is not supported')
 
  return ret 


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

---

Python 구현 : while 문을 이용한 dynamic programming 기법

이 dynamic programming 은 "동적계획법" 이라고 번역되는 방식으로

처음 접할 때, 용어 때문에 여러 오해를 일으키는 용어임.

 

쉽게 설명하면 dynamic programming은 중복되어 사용되는 변수를 한번만 계산하고 이를 기억하여 재사용하는 방식을 칭함 (memory기능을 사용).

이를 전문 용어로 애기하면 다음과 같음:

Dynamic Programming 이란?
중복되는 부분 문제(subproblem)를 한 번만 계산하고
이를 저장(memoization 또는 tabulation)한 후,
나중에 재사용하는 방식으로 문제를 해결하는 기법

 

여기서 "dynamic" 은 memory 를 사용한다는 의미임: dynamic system 과 instaneous system 등의 공학적 의미에서 dynamic은 memory를 이용한다는 의미가 있음.

 

그리고, "programming"은 코드를 작성하는 오늘날의 프로그래밍의 의미가 아닌 TV 프로그램 순서와 같은 의미로 다음과 같은 뜻을 가짐.

여기서 "programming"은
계획을 세우는 일련의 과정 또는 최적화된 순서를 짜는 것을 의미함

 

여기서 사용된 "programming"이라는 용어는 보다 자세한 건 다음 접은 글을 참조:

2023.07.08 - [.../Math] - [Math] Linear Programming and Quadratic Programming

[Math] Linear Programming and Quadratic Programming

---

def fibonacci_loop(num):
  if num == 0 or num == 1:    
    return num
  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문을 이용한 dynmaic programming 방법을 이용한 경우

fibonacci_loop함수 내에서 수열을 출력하도록 수정하면 훨씬 효과적으로 피보나치 수열을 출력할 수 있다.

(위의 경우, fibonacci_loop에서는 수열을 출력하기 보다 최종값만을 구하는 형태임).

 

사실 fibonacci 문제에서 dynamic programming 방법이 아닌, recursive call 로 구현하면 엄청난 실행시간을 요구함.

 

좀 더 개선한다면,

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