알고리즘 - 재귀함수 (Recursive Function)

재귀(Recursion) 함수

영화 인셉션을 보면 꿈속에서 꿈을 꾸고 그 꿈속에서 또 꿈을 꾼다. 재귀함수는 간단하게 말해서 자기 자신을 호출하는 함수이다.

# 카운트다운
def count_down(n):
  if n > 0:
    print(n)
    count_down(n - 1)

count_down(3)  # 3, 2, 1

팩토리얼을 계산하는 함수

def factorial(n):
  if n == 0:
      return 1
  return factorial(n-1) * n

재귀적으로 문제를 풀기 위해서는 부분 문제(Subproblem)을 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 방식을 이용하면 효율적이다. 따라서 Base Case와 Recursive Case를 생각해보고 문제에 접근해보는 방법이 도움이 될 것이다. 여기서 n이 0일때 1을 리턴하는데 이를 Base Case라고 한다. 그게 아닐 경우 factorial 함수를 호출해서 리턴하는데 이를 Recursive Case라고 한다. 좀 더 쉬운 이해를 위해 그림을 보자면 이렇다.

팩토리얼 함수에 인자로 4를 넣는다고 가정해보자. 그렇다면 Factorial(4), Factorial(3), Factorial(2), Factorial(1), Factorial(0)이 계속해서 호출되다가 1이 리턴될 것이다. 그러면 그 리턴 값으로 인해 Factorial(1)의 리턴 값은 Factorial(1-1) * 1이 되면서 1이 될 것이고, Factorial(2)의 리턴 값은 2가 될 것이고, Factorial(3)의 리턴 값은 6이 될 것이고, Factorial(4)의 리턴 값은 24가 될 것이다.

피보나치 수열을 계산하는 재귀함수

def fib(n):
    if n < 3:
        return 1
    return fib(n-2) + fib(n-1)

n이 1 혹은 2일 경우를 Base Case로 생각해볼 수 있다. 이 경우 1을 반환하고, Base Case를 이렇게 잡았다면 Recursive Case는 이전 항(A)과 A의 이전 항(B)를 합한 값을 리턴해준다.

Stack Over Flow?

재귀함수에는 치명적인 단점이 하나 있다. 함수를 호출하면 위치를 기록하기 위해서 CallStack이라는 것을 쓰는데 함수를 재귀적으로 너무 많이 호출하게 되면 CallStack이 계속 쌓이면서 더이상 기록할 공간이 없어지고, 결국 프로그램은 중단된다. 개발자 커뮤니티로도 불리는 stackoverflow는 CallStack이 너무 많이 쌓여서 한계치에 도달하고나면 생기는 에러의 이름이다. CallStack이 너무 많이 쌓일 것 같다면 가급적이면 반복문을 이용하는게 좋다.