[Python] 재귀 호출과 그 응용

재귀 호출과 그 응용

recursion

• 함수의 정의부에서 자기 자신을 재귀적으로 호출할 수 있음
• 재귀 호출을 이용하여 다양한 형태의 문제를 해결할 수 있음

자연수를 인자로 받아 factorial을 계산하는 함수를 재귀적으로 정의하면?

def fact_func(n):
  if n==1:
    return 1
  else: 
    return n * fact_func(n-1)

fact_func(5)

자연수 n에 대해 n번째 피보나치 수를 반환하는 함수를 재귀적으로 정의하면?

def fibo_func(n):
  print(*)
  if (n==1) or (n==2):
    return 1
  else:
    return fibo_func(n-1) + fibo_func(n-2)

 fibo_func(7)

• n이 2일 때도 1을 반환하는 이유는?
• → 두 번째 피보나치 수도 1로, 첫 번째와 두 번째 피보나치수가 먼저 결정되어야 다른 수들이 결정될 수 있다.
• fibo_func()가 호출되는 총 횟수는?→ 25번 호출됨 (1+2+4+8+8+2 = 25)
• → fibo_func(7) = (6) + (5) = (5) + (4) + (4) + (3) = (4) + (3) + (3) + (2) + (3) + (2) + (2) + (1) = (3) + (2) + (2) + (1) + (2) + (1) + (2) + (1) +4 = (2) + (1) + 11 = 13