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

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

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

 

다음과 같은 재귀적인 수식(정확히는 recurrence relation, 점화식)을 있는 그대로 작성하게 해준다는 장점은 있지만,

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

$$
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
$$

 

참고로, recursive function은 다음의 2가지로 구성됨:

1. base case : recursion이 더 이상 recursive call을 하지 않고 바로 특정 값을 반환하는 조건.
2. recursive step : 자기 자신을 바뀐 argument로 다시 호출

base case는 recursion이 멈추는 조건이며 문제의 가장 작은 크기(base problem)에 해당하고,

recursive step(case라고 해도 됨)은 문제를 더 작은 하위 문제(subproblem)로 변환하고, 그 하위 문제를 해결하기 위해 자기 자신을 다시 호출한다.

반드시 아래의 Python 구현 예에서 확인해 볼 것.

 

Recursive function과 Recurrence relation에 대해 보다 자세한 건 다음을 참고:

https://ds31x.tistory.com/561

Recursive Function and Recurrence Relation

---

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

def fibonacci_recur(num):
  ret = -1
  if num <0:
    # error 대처
    print('ERROR: negative is not supported')
  elif num <=1 :
    # base case
    ret = num      
  else: 
    # recursive step
    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')

• 가장 recurrence relation을 그대로 작성한 형태이나,
• 같은 값의 계산이 여러 번 반복해서 이루어짐.
• fibonacci_recur 함수에 대한 같은 인자의 호출이 수차례 반복됨.
• 가장 시간 ($O(2^n)$)및 공간 복잡도($O(n)$)가 높음.
  • 각 호출이 두 개의 하위 호출로 이루어짐.

---

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

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

처음 접할 때, 용어 때문에 여러 오해를 일으키는 용어임: status를 기억하는 dynamic system 처럼 memory를 사용! 

2023.08.21 - [.../Signals and Systems] - [SS] System의 종류 (3)

[SS] System의 종류 (3)

 

쉽게 설명하면

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

 

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

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

 

쉽게 애기하면, "dynamic" 은 memory 를 사용한다는 의미로 공학에서 많이 사용됨:
dynamic system 과 instaneous system 등의 공학적 의미에서
dynamic은 memory를 이용한다(=status를 이용한다)는 의미가 있음.

 

Dynamic Programming은 1952년 Bellman 에 의해 제안되었는데, Bellman 의 설명에 따르면 다음을 의미한다.

• dynamic : 시간이 흐르면서 단계적으로 진행되는 decision process
• programming : 여기서 programming은 수학적 계획(planning) 의미

즉, dynamic programming은

"시간에 따라 단계적으로 의사결정을 최적화하는 계획 방법"

을 의미한다고 보면 된다

Bellman은 
오늘날 강화학습에서 매우 중요한 역할을 하는
유명한 Bellman Equation을 제안한 이임.

https://ds31x.tistory.com/631

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

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

 

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

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

[Math] Linear Programming and Quadratic Programming

---

Memonization 과 DP tabulation은 Dynamic programming 내의 세부 분류와 관련됨:

 

Dynamic programming 에서 top-down 방식과 bottom-up 방식으로 나뉘며
각각이 memoization과 tabulation을 통해 메모리에 값을 기억함.

구분	memoization	tabluation
방식	Top-down	Bottom-up
구현	recursion	iteration
계산 순서	필요할 때 계산	작은 값부터 순차 계산
계산 범위	필요한 값만	모든 값
자료구조	memo cache	DP table

 

이렇게 엄밀히 나누는 경우보다는 tabulation DP를 Dynamic Programming으로 보통 가리키며, memoization은 DP를 recursion 으로 구현한 형태로 설명하는 경우도 많음.

 

Fibonacci sequence의 경우

• top-down 방식을 적용한다면 recursion  구조를 유지하면서 값을 기억하여 재사용하는 memoization 을 이용하는 것이고
  (top-down은 문제의 정의에서 출발하여 필요한 subproblem으로 내려가면서 계산: recursion + momoization)
• bottom-up 방식을 채택하는 경우엔 iteartion(순환)의 loop 문을 통해 가장 작은 문제부터 시작하여 전체 큰 문제의 해를 구해나가는 방식이다: loop + DP tabulation 이라고도 부름.
  (bottom-up은 가장 작은 subproblem 부터 계산하여 점차 큰 문제로 올라감: iteration 즉, loop를 이용함)

우선 다음은 top-down DP(Dynamic Programming)임:

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]

    if n <= 1:
        result = n
    else:
        result = fib_memo(n-1, memo) + fib_memo(n-2, memo)

    memo[n] = result
    return result
    
for i in range(0,10,1):
  # print(i)
  print(fib_memo(i), end=",")
print('\n')

• 여전히 재귀호출은 존재하지만, 중복 계산은 제거되었음.
• 시간복잡도는 $O(n)$이고, 공간복잡도는 memoization을 위해서 $O(n)$이, recusion stack 을 위해서 $O(n)$이 각각 요구됨.

 

다음은 Bottom-up (=Iterative DP)방식임.

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')

• 시간 복잡도는 $O(n)$으로 같으나,
• 공간복잡도는 2개의 변수만 저장하면 되므로 $O(1)$에 불과함.

 

사실 while문을 이용한 dynmaic programming 방법(Bottom-up)을 이용한 경우

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

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

 

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

 

좀 더 개선한다면,

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

 

참고로, Fibonacci sequence의 경우, matrix exponentiation이 가장 효과적인 알고리즘임