재귀 함수/재귀적 호출(Recursion Function/Recursion Call)

 

프로그래밍을 하거나, 알고리즘을 공부하다보면 꼭 만나게 되는 것이 재귀 함수이다. 재귀는 한 번 이해하면 쉬운 개념이지만, 한번에 이해가 샤라락 되는 난이도는 아니다. 적어도 나는 그렇다.

 

재귀는 말 그대로 반복 혹은 되풀이를 뜻하며 재귀 함수, 재귀적 호출 모두 같은 말이다. 영어로는 Recursive Call 혹은 Recursive Fucntion이라고 한다. 함수 내에서 자기 자신을 계속 재호출하는 형태를 말한다. 보통 재귀 함수는 원하는 결과값을 얻기까지 반복해서 이루어진다.

 

가장 대표적인 재귀 함수의 예로 팩토리얼(Factorial)이 있다. 아래는 재귀 함수를 코드로 구현한 예시이다. 자기 자신을 호출하여 n-1을 계산하고, 이 값에 n을 곱하는 과정을 n이 1이 될 때까지 반복하여 최종 값을 얻어낸다.

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

 

이를 직관적으로 살펴보면 다음과 같다. 함수를 호출하는 것은 Stack처럼 관리되기 때문에 예컨대 4팩토리얼(4!)를 구하기 위해서 재귀 함수를 실행 시키게 되면 메모리상으로는 아래와 같이 저장되고 실행된다.

이런 식으로 n이 1이 될 때까지 스택이 쌓이게 되고, n이 1이 되는 순간 재귀가 멈추고 순서대로 연산이 진행되어 최종 결과를 도출하게 된다.

Stack의 특성과 같이 후입선출로 계산이 되어 결과적으로 4!는 4 * 6 = 24로 계산이 되는 것이다. 재귀 호출은 함수의 실행 정보를 스택 메모리에 저장하기 때문에 많은 메모리를 사용하게 되고, 이로 인해 프로그램이 느려지거나 메모리 초과(Stack Overflow)가 발생할 수 있다.

 

재귀 함수의 장점은 복잡한 문제를 쉽게 풀어낼 수 있고, 이에 따라 코드도 무척 간결해진다는 점이다. 다만 재귀는 그 사용법을 잘 이해하고 사용해야 한다. 탈출 조건에 오류가 있으면 자칫 무한 재귀에 빠질 수도 있고, 메모리 사용과 성능 문제가 발생할 수도 있기 때문이다.

 

마지막으로 재귀 함수가 아닌 반복문으로 작성한 코드는 아래와 같다.

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result