재귀 함수란?

재귀 함수란 자기 자신을 호출하는 함수다.
즉, 함수 내부에서 자기 자신을 다시 실행하는 구조를 가진 함수로 특정 조건이 만족될 때 까지 반복 호출된다.

재귀 함수는 크게 두 가지 요소로 구성된다.

• 기저 조건(Base case): 재귀 호출을 멈추는 조건.
• 재귀 호출(Recursive case): 함수가 자기 자신을 호출하는 부분.

재귀 함수로 해결할 수 있는 대표적인 예시인 팩토리얼을 통해 간단하게 알아보자.

팩토리얼은 다음과 같이 정의된다.
$n! = n*(n-1)*(n-2)*...*1$

이를 코드로 구현해보면 다음과 같다.

def factorial(n):
    if n == 0:  # 기저 조건
        return 1
    return n * factorial(n - 1)  # 재귀 호출

팩토리얼 문제는 반복문으로도 풀 수 있다.

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

팩토리얼 계산 문제는 반복문이 하나만 사용되는 간단한 문제라 별 차이가 없지만, 다중 반복문과 같이 복잡한 반복문을 사용해야 할 때 재귀 함수를 사용하면 코드가 간결해진다.

하지만 일반적으로 반복문이 메모리 사용 측면에서 더 효율적이다.
따라서 상황마다 적절한 방법을 고려하며 사용하는 것이 중요하다.

그렇다면 언제 재귀 함수를 사용하면 좋을까?
문제를 더 작은 문제로 분해할 수 있는 경우나, 반복분의 중첩이 많아서 결과를 예측하기 힘든 경우 유용하다.
또, 복잡한 반복문으로 표현된 함수가 코드의 가독성을 해칠 때 가독성과 유시보수성을 향상시키기 위해 사용된다.

스택 오버플로우

재귀 함수를 사용할 때 주의할 점이 있다.
바로 스택 오버플로우다.

재귀 함수를 호출할 때마다 새로운 스택 프레임이 생성되는데, 이 프레임들이 계속 쌓이면 스택 메모리가 과부하를 겪게 되고, 스택 오버플로우가 발생하게 된다.

/ TCP School

스택 오버플로우가 발생하면 프로그램이 강제 종료되므로 이를 방지하는 것이 중요하다.

스택 오버플로우를 방지하기 위해선
기저 조건을 정확하게 설정해야 하고,
꼬리 재귀 최적화를 활용해야 한다.

꼬리 재귀란 함수 안에서 함수 호출이 발생할 때 이 호출이 함수의 가장 마지막 순서에 위치하는 것을 말한다.
이를 통해 스택 프레임을 재사용할 수 있어 스택 공간을 절약할 수 있게 된다.

앞서 코드로 나타낸 팩토리얼 함수를 최적화하면 다음과 같다.

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

함수의 호출이 스택에 쌓이지 않고 결과가 바로 반환된다

하지만 컴파일러가 꼬리 재귀 최적화를 지원하지 않는다면 일반 재귀처럼 동작하게 된다.
(C++, C#, Swift, 코틀린 등이 지원하고 Java, Python, Go등은 지원하지 않는다.)