7-3 : 스택 (3) - 함수 호출, 재귀

스택 (3)

스택 응용 예시 2 - 함수 호출

• 후입선출 구조로 함수 수행순서 관리
  1. 함수 수행과 관련된 정보를 스택 프레임에 저장
  2. 함수 실행이 끝나면 시스템 스택의 top 원소를 삭제(pop)하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀
  3. 이 과정이 반복되어 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 됨

재귀 호출

• 자기 자신을 호출하여 순환 수행되는 것
• 스택 프레임으로 스택에 저장되는 값이 입력 값이 다른 같은 함수의 스택 프레임을 저장한다.

# python 예시 - 피보나치 수열(1): 재귀 호출

def fibo(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

result = []
for i in range(1,11):
    result.append(fibo(i))

print(*result)

# 출력
>>> 1 1 2 3 5 8 13 21 34 55

–> 중복 호출이 많이 일어난다.

• 참고: 메모이제이션(Memoization)

  • 이전에 계산한 값을 저장해서 매번 다시 계산하지 않도록 하는 기술
  • DP(동적계획법, Dynamic Programming)의 핵심이 되는 기술

  # python 예시 - 피보나치 수열(2): 재귀 호출 + 메모이제이션
  def fibo_memo(n):
      global memo
      if n >= 2 and len(memo) <= n: 
          # 계산 값을 저장한 리스트(memo)의 길이로 제약조건을 걸어 
          # 한 번 계산한 값에 대해 다시 함수를 호출하지 않도록 한다.
          # 부등호를 정할 때, 계산 되기 이전에는 함수를 불러올 수 있도록 한다.
          memo.append(fibo_memo(n-1) + fibo_memo(n-2))
      return memo[n]
    
  memo = [0, 1]
  result = []
  for i in range(1, 11):
      result.append(fibo_memo(i))
  print(*result)
    
  # 출력
  >>> 1 1 2 3 5 8 13 21 34 55
  

출처: SW Expert Academy - Learn - Course - Programming Intermediate

SW Expert Academy - Programming Intermediate course