재귀(Recursion) 함수

Recursion's Structure

1. 재귀(Recursion)의 의미

사전적 의미의 재귀(Recursion)는 '되풀이되는 것' 이라는 의미를 갖고 있다.

프로그래밍에서의 재귀 함수는 함수가 자기 자신을 다시 호출하는 구조를 말한다.

쉽게 말해, 큰 문제를 해결하기 위해 스스로를 호출하여 더 작은 단위로 쪼개고, 그 작은 문제들이 해결될 때까지 반복하는 방식이다.

2. 재귀(Recursion) 함수의 핵심 요소

재귀 함수를 작성할 때 가장 중요한 것은 '언제 멈출 것인가?'를 결정하는 것이다.

종료 조건(Base Case)이 없으면 함수는 자기 자신을 무한히 호출하다가 결국 RecursionError 를 발생하게 된다.

3. 실전 예시 : 팩토리얼(Factorial) 계산

가장 대표적인 재귀 예시인 팩토리얼을 통해 확인할 수 있다.

5! = 5 x 4 x 3 x 2 x 1

def factorial(n):
    # 1. 종료 조건: n이 1이면 1을 반환
    if n == 1:
        return 1
    # 2. 재귀 호출: n * (n - 1)의 팩토리얼 계산
    return n * factorial(n - 1)
print(factorial(5)) # 결과는 120

<코드 설명>

-  if n == 1  : 재귀를 멈추는 조건

-  return n * factorial(n - 1)  : 문제의 크기를 1씩 줄여가며 자기 자신을 다시 호출

4. 재귀가 동작하는 구조 : 스택(Stack)

재귀는 호출될 때마다 메모리의 스택(Stack)영역에 차곡차곡 쌓인다. 5에서 시작해 1까지 내려갔다가, 다시 1부터 계산 결과를 가지고 올라온다.

{ 함수 호출이 빈번할 경우, for, while 같은 반복문을 사용하는 것이 메모리 사용 등 성능 측면에서 유리하다. }

5. 효과적인 재귀 함수 사용 예시

재귀는 단순 반복보다는 복잡한 구조를 다룰 때 강점을 갖는다.

(1) 트리(Tree) 및 그래프 탐색 : 폴더 구조 탐색이나 경로 찾기

(2) 분할 정복 알고리즘 : 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort) 등

(3) 수학적 점화식 풀이 : 피보나치 수열 등

재귀 함수는 복잡한 문제를 직관적이고 효과적으로 해결할 수 있다. 

하지만, '종료 조건'을 갖춰야 하고, 너무 복합된 재귀는 피하는 것이 좋다.

개인적으로는 반복이 필요하다면, 재귀보다는 단순 반복문(for or while)을 사용 할 것 같다.

#python #recursion #for문 #while문 #stack #factorial #RecursionError #피보나치 #Tree