[python] 재귀함수 이해하기 / 두 개의 재귀 호출을 포함하는 경우

1. 재귀함수란

재귀함수(Recursive Function): 함수가 자기 자신을 호출하는 함수

재귀호출(Recursive Call): 함수 안에서 함수 자기자신을 호출하는 방식

 

재귀는 문제를 더 작은 하위 문제로 분해하고, 그 하위 문제를 해결하는 방식으로 원래 문제를 해결하는 방식이다. 재귀는 효율적이고 직관적인 문제 해결 방법을 제공하지만, 성능과 메모리 사용을 고려해야 한다. 재귀적으로 해결할 수 있는 문제는 종종 반복문으로도 해결할 수 있다.

 

재귀함수는 무한히 자신을 호출하게 되어 무한 루프에 빠지는 오류를 막기 위해 재귀 호출을 중지하는 조건을 코드에 반드시 포함시켜야 한다!

 

2. 재귀함수 기본 구조

def recursive_function(parameters):
    if base_case_condition:   # 재귀호출 중지 조건
        return result  
    else:
        # 재귀 단계: 문제를 더 작은 문제로 쪼개서 재귀 호출
        return recursive_function(modified_parameters)

 

팩토리얼(Factorial) 예시

재귀함수의 가장 대표적인 사용 예시는 팩토리얼(n!)이다.

팩토리얼 또는 계승은 1부터 n까지의 모든 정수를 곱한 값이다. ex) 5! = 5 × 4 × 3 × 2 × 1
이를 재귀함수를 사용해 간단하게 계산할 수 있다. 

def factorial(n):
    if n == 1:  # 중지 조건: n이 1이면 1을 반환
        return 1
    else:
        return n * factorial(n - 1)  # 재귀 단계: n * (n-1)!

 

함수 작동 순서:

1) factorial(5)는 5 * factorial(4)를 호출
2) factorial(4)는 4 * factorial(3)을 호출
3) factorial(1)에 도달할 때까지 해당 과정 반복
4) factorial(1)은 1을 반환
5) 그 후 호출 스택에서 계산된 값들이 차례대로 반환

 

재귀 함수가 두 개의 재귀 호출을 포함하는 경우

재귀 함수가 두 개의 재귀 호출을 포함하는 경우, 한 개의 재귀 호출을 포함하는 경우보다 함수의 실행 흐름이 조금 더 복잡하다. 재귀 함수가 호출되면, 첫 번째 재귀 호출이 실행된 후 두 번째 재귀 호출이 실행된다. 각 재귀 호출은 호출 스택에 쌓이고, 재귀 호출이 완료되면 스택에서 제거된다. 두 번째 호출이 먼저 완료되고, 그 후 첫 번째 호출이 완료된다. 글로만 읽을 때는 무슨 말인지 잘 모르겠다. 첫 번째 재귀 호출이 먼저 실행되는데 완료되는 건 두 번째가 먼저라고? 뭔 소리인지...

 

조금 더 쉽게 이해하기 위해 예시를 살펴보자.

# 재귀 함수가 두 개의 재귀 호출을 포함하는 예시
def example(n):    # 재귀 호출 중지 조건
    if n <= 0:
        return
    print("Before first call: ", n)
    example(n - 1)  # 첫 번째 재귀 호출
    print("Before second call: ", n)
    example(n - 2)  # 두 번째 재귀 호출
    print("After both calls: ", n)

 

해당 함수에서 example(3)이 실행되는 과정을 살펴보자.

1. example(3) 호출

i. 출력: "Before first call: 3"

ii. 첫 번째 재귀 호출: example(2)

iii. example(3)의 이후 코드 실행은 대기.

 

2. example(2)

i. 출력: "Before first call: 2"

ii. 첫 번째 재귀 호출: example(1)

iii. example(2)의 이후 코드 실행은 대기.

 

3. example(1)

i. 출력: "Before first call: 1"

ii. 첫 번째 재귀 호출: example(0)

iii. example(1)의 이후 코드 실행은 대기.

 

4. example(0)

i. 재귀 호출 중지 조건 충족: n<=0이므로 호출 종료.

 

5. 3-iii의 example(1) 코드 이어서 실행

i. 출력: "Before second call: 1"

ii. 두 번째 재귀 호출: example(-1)

iii. example(1)의 이후 코드 실행은 대기.

 

6. example(-1)

i. 재귀 호출 중지 조건 충족: n<=0이므로 호출 종료.

 

7. 5-iii의 example(1) 코드 이어서 실행

i. 출력: "After both calls: 1". 호출 종료.

 

8. 2-iii의 example(2) 코드 이어서 실행

i. 출력: "Before second call: 2"

ii. 두 번째 재귀 호출: example(0)

iii. example(2)의 이후 코드 실행은 대기.

 

9. example(0)

i. 재귀 호출 중지 조건 충족: n<=0이므로 호출 종료.

 

10. 8-iii의 example(2) 코드 이어서 실행

i. 출력: "After both calls: 2". 호출 종료.

 

11. 1-iii의 example(3) 코드 이어서 실행

i. 출력: "Before second call: 3"

ii. 두 번째 재귀 호출: example(2)

iii. example(2)의 동일한 과정 반복

... ...

출력: "After both calls: 3". 호출 종료.

이 과정을 차근차근 따라가보면 가장 마지막에 호출된 가장 하위 호출부터 호출이 종료되는 것을 볼 수 있다. 이것은 각 호출이 후입선출(LIFO, Last-In-First-Out) 방식을 따르는 스택에 쌓여서 스택의 데이터 처리 방식에 맞게 순차적으로 처리되기 때문이다.

 

 

3. 재귀 함수의 장단점

1. 장점:

• for, while과 같은 반복문을 사용하지 않아도 되기에 복잡한 문제를 간결하게 표현할 수 있다.
• 자기 자신을 반복적으로 호출하기 때문에 변수가 많이 필요하지 않다.

2. 단점:

• 성능: 재귀는 함수 호출마다 메모리 스택을 사용하므로 반복문을 사용한 구현보다 메모리 사용량이 많아질 수 있으며, 이는 속도 저하로도 이어진다.
• 스택 오버플로우: 너무 깊은 재귀 호출이 발생하면 스택 오버플로우(Stack Overflow) 오류가 발생할 수 있다.

스택 오버플로우(Stack Overflow)
: 프로그램이 실행될 때 사용되는 메모리 스택 영역이 가득 차서 더 이상 데이터를 저장할 수 없는 상황