# 재귀 함수

재귀 함수에 대해 정리하고자 게시글을 작성하게 되었습니다. 재귀함수가 대표적으로 원리만 들었을 때는 이해가 쉬운 것 같지만 육안으로 확인하기 어렵기에 많은 사람들이 저 포함하여 헷갈리는 듯한 느낌이 들어 이를 정리하고자 합니다.

 

def fact(n, depth=0):
    indent = "  " * depth 

    print(f"{indent}fact({n}) 호출")

    if n == 0:
        print(f"{indent}→ 1 리턴")
        return 1

    result = n * fact(n - 1, depth + 1)

    print(f"{indent}fact({n}) 종료, {result} 리턴")
    return result

fact(3)

재귀의 콜스택이 어떻게 이루어지는지 확인하기 위해 다음과 같은 코드를 구현하였습니다.

 

fact(3) 호출
  fact(2) 호출
    fact(1) 호출
      fact(0) 호출
      → 1 리턴
    fact(1) 종료, 1 리턴
  fact(2) 종료, 2 리턴
fact(3) 종료, 6 리턴

실행시켜보면 다음과 같은 응답을 눈으로 확인할 수 있습니다. 

 

여기서 알 수 있는 것은 재귀함수는 LIFO 형태로 진행된다는 점을 알 수 있습니다. 미리 호출한 것을 스택에 담아두고 가장 마지막에 들어온 호출부터 처리합니다. 

 

재귀는 콜스택에 먼저 넣고 이를 처리하는데 만약 무한 재귀에 빠지게 되면 어떻게 될까요? 이는 스택 오버플로우 현상이 발생하여 프로그램 자체에서 강제 종료되어집니다. 

 

10870번

백준의 10870번 문제를 통해 재귀함수의 이해를 확인해보았습니다. 일단 총 3가지의 문제 풀이법을 확인했고 이에 대한 답은 다음과 같습니다.

 

n = int(input())

def fibonacci(n):
  if (n == 0): return 0
  elif (n <= 2): return 1

  return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(n))

피보나치 수열에 관한 문제고 재귀가 돌아가는 동작 방식을 다시 정리하면 다음과 같습니다.

 

fibonacci(5)를 요청하게 되면 base case부터 먼저 검증을 진행합니다. 검증 조건에 부합하지 않아 fibonacci(4)와 fibonacci(3)을 요청하게 됩니다. 이렇게 함수를 반복해서 요청하고 마침내 base case를 만나게 되면 나중에 요청 들어왔던 연산들이 시작됩니다.

 

fibonacci(2)는 fibonacci(1) + fibonacci(0)으로 1과 0입니다. 따라서 1이 연산되었고 fibonacci(3)은 fibonacci(2) + fibonacci(1)로 1과 1이므로 2가 저장됩니다. 이런 식으로 연산이 이어진다면 재귀로써 값을 얻을 수 있습니다.

 

n = int(input())

def memoization(n):
  MAX = 20
  arr = [0] * (MAX + 1)

  arr[1] = 1
  arr[2] = 1

  for i in range(3, len(arr)):
    arr[i] = arr[i - 2] + arr[i - 1]
  
  return arr[n]

print(memoization(n))

두번째는 메모이제이션을 활용한 기법입니다. 메모이제이션은 미리 값을 연산해두고 필요 시에 꺼내쓰는 방식으로 재귀가 아니더라도 구현해낼 수 있는 방법입니다.

 

n = int(input())

def memonacci(n):
  global arr

  if (arr[n] != -1): return arr[n]
  arr[n] = memonacci(n - 2) + memonacci(n - 1)
  return arr[n]


MAX = 20
arr = [-1] * (MAX + 1)
arr[0] = 0
arr[1] = 1

print(memonacci(n))

마지막으로 재귀와 메모이제이션을 같이 활용하는 방식입니다. base case가 기존과는 조금 달라진 점을 확인할 수 있는데요, 배열의 인덱스 부분에 재귀 연산으로 참조를 시켜두기에 크게 문제되지는 않습니다.