[Python] 재귀함수(Recursive function) 알아보기

728x90

1. 재귀함수란?

재귀함수(Recursive function)은 다른 함수 호출이 아닌 자기 자신을 다시 호출하는 함수를 의미합니다.

재귀함수를 만드려면 크게 두 부분이 필요합니다.

1)재귀 호출 과 2)재귀 종료 조건 인데요.

1)재귀호출은 말 그대로 함수 안에서 제 자신을 또 불러와서 뭔가를 작업하는 영역인데, 무한정 불러올 순 없겠죠? 그래서 지정해주는 부분이 재귀 종료 조건입니다.

즉, 재귀 종료 조건을 만족할 때까지 재귀적으로 자신을 호출하겠다 라는 의미라고 볼 수 있겠습니다.

2. 재귀함수 예시 1 - 팩토리얼 연산

그럼 예시로 살펴봅시다. 첫 번째 예시는 가장 대표적인 예시인 팩토리얼 연산입니다.

def factorial(n):
	# 재귀 종료 조건
	if n == 0:
		return 1
	# 재귀 호출
	else:
		return n * factorial(n-1)
# 팩토리얼 5 계산
print(factorial(5)) # 결과: 120

조금씩 뜯어서 살펴봅시다.

종료 조건:

n == 0 또는 n == 1일 때 함수는 1을 반환하여 재귀 호출을 종료합니다.
이는 팩토리얼의 정의에 따라 0! = 1, 1! = 1로 처리됩니다.

재귀 호출:

함수는 자기 자신을 호출하면서 n-1 값을 전달합니다.
예: factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ...

실행 과정 :

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 (종료 조건 도달)
계산: 5 * 4 * 3 * 2 * 1 = 120

그런데, 여기서 몇 가지 궁금증이 생길 수 있습니다.

Q1. 종료조건과 재귀호출 모두 return을 쓰는데 종료조건에서는 종료가 되는 이유는 뭘까?

A1. 종료 조건에서 "종료"가 되는 이유는 재귀 호출이 더 이상 발생하지 않기 때문!

Q2. 마지막에 재귀 종료 조건을 만족하면 return 1이 되는건 아닌가?

A2. 재귀 호출에서는 함수가 다시 호출되므로 현재 함수는 멈춘 상태로 대기하며, 재귀 호출이 완료되기를 기다린다. 재귀 호출이 끝나고 반환값을 받으면, 그 값을 이용해 계산을 이어갑니다. 즉, 재귀 함수는 호출될 때마다 호출 스택에 쌓이고, 종료 조건을 만나면 더 이상 스택이 쌓이지 않고, 반환된 값을 이용해 차례대로 스택이 정리되는 구조다.

호출 스택의 동작

factorial(3)을 실행한다고 하면,

factorial(3) → 실행 중 → return 3 * factorial(2)
factorial(2) → 실행 중 → return 2 * factorial(1)
factorial(1) → 종료 조건에 도달 → return 1
이제 factorial(1)의 결과가 1로 반환되어 factorial(2)로 돌아감:
- factorial(2) = 2 * 1 = 2
결과 2가 반환되어 factorial(3)로 돌아감:
- factorial(3) = 3 * 2 = 6

이렇게 해서 최종적으로 계산이 완료되는 구조인 것이다!

종료 조건에서 return한 걸 가지고 이전 스택에서의 값 계산하고, 그 이전 스택에서의 값 계산하고... 반복하는 과정인 것~!

3. 재귀함수 예시 2 - 피보나치 수열

두 번째 예시는 피보나치 수열입니다.

def fibonacci(n):
    if n == 0:  # 종료 조건 1
        return 0
    if n == 1:  # 종료 조건 2
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # 재귀 호출

# 예제
print(fibonacci(5))  # 출력: 5

종료 조건:

fibonacci(0) 또는 fibonacci(1)을 호출하면, 재귀 호출 없이 바로 값을 반환합니다.
이 조건이 없으면 함수는 계속해서 자기 자신을 호출하여 무한 재귀에 빠지게 됩니다.

재귀 호출:

이 부분은 피보나치 정의에 따라 다음 두 값을 재귀적으로 호출하여 계산합니다.
예를 들어, fibonacci(5)는 fibonacci(4)와 fibonacci(3)을 호출하여 각각 값을 계산한 뒤 더합니다.

실행 과정 :

함수 호출의 흐름 (재귀 호출 + 종료 조건):
- fibonacci(5) = fibonacci(4) + fibonacci(3)
  - fibonacci(4) = fibonacci(3) + fibonacci(2)
    - fibonacci(3) = fibonacci(2) + fibonacci(1)
      - fibonacci(2) = fibonacci(1) + fibonacci(0)
        
        fibonacci(1) = 1 (종료 조건 도달)
        
        fibonacci(0) = 0 (종료 조건 도달)
      - 결과: fibonacci(2) = 1 + 0 = 1
      - fibonacci(1) = 1 (종료 조건 도달)
    - 결과: fibonacci(3) = 1 + 1 = 2
    - fibonacci(2) = 1 (이미 계산됨)
  - 결과: fibonacci(4) = 2 + 1 = 3
  - fibonacci(3) = 2 (이미 계산됨)
- 결과: fibonacci(5) = 3 + 2 = 5

호출 스택의 동작

재귀 함수 호출은 호출 스택에 쌓이고, 종료 조건이 도달하면 스택이 차례로 정리되며 계산이 이루어집니다.

호출 스택 예시 (fibonacci(3)):

호출: fibonacci(3) → fibonacci(2) → fibonacci(1) → 종료 조건 도달 (1 반환).
호출: fibonacci(2) → fibonacci(1) → 1 반환.
호출: fibonacci(2) → fibonacci(0) → 0 반환.
스택 정리: 결과 fibonacci(2) = 1 + 0 = 1을 반환.
스택 정리: 결과 fibonacci(3) = 1 + 1 = 2을 반환.

이상입니다. 공부하시는데 참고가 되었으면 좋겠습니다.