파이썬 - 재귀: 초보자 가이드

안녕하세요, 미래의 파이썬 마법사 여러분! 오늘은 재귀의 세계로 흥미진진한 여정을 떠날 거예요. 조금 두려울 수도 있지만, 재미있고 쉽게 이해할 수 있도록 만들어드리겠습니다. 그럼, 좋아하는 음료수를 들고 편하게 앉아서 함께 탐험해보세요!

Python - Recursion

재귀는 무엇인가요?

양쪽에 걸려 있는 거울 앞에 서 있는 것을 상상해보세요. 무한한 반사가 보이지 않나요? 이 것은 프로그래밍에서 재귀와는 약간 비슷해요! 간단히 말하면, 재귀는 문제를 해결하기 위해 함수가 자신을 호출하는 것입니다.

간단한 예제로 시작해보죠:

def countdown(n):
if n <= 0:
print("발사!")
else:
print(n)
countdown(n - 1)

countdown(5)

이 코드를 실행하면 다음과 같이 보입니다:

5
4
3
2
1
발사!

이제 이를 분석해보죠:

countdown라는 함수를 정의하고, 숫자 n을 인수로 받습니다.
n이 0이거나 더 작으면 "발사!"를 인쇄합니다.
그렇지 않으면 n을 인쇄하고 다시 countdown를 n - 1로 호출합니다.

이것이 재귀의 작동입니다! 함수는 0에 도달할 때까지 작은 숫자로 계속 자신을 호출합니다.

재귀의 구성 요소

모든 재귀 함수는 두 가지 주요 구성 요소를 가집니다:

기저 사례: 재귀를 중단하는 조건.
재귀 사례: 함수가 자신을 호출하는 부분.

우리의 countdown 예제에서:

기저 사례는 if n <= 0
재귀 사례는 countdown(n - 1)

다른 전통적인 예제를 살펴보죠: 팩토리얼을 계산하는 것.

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

print(factorial(5))  # 출력: 120

이렇게 일어나고 있습니다:

n이 0이나 1이면 1을 반환합니다 (이것이 우리의 기저 사례입니다).
그렇지 않으면 n을 n - 1의 팩토리얼과 곱합니다 (이것이 우리의 재귀 사례입니다).

따라서, factorial(5)는 다음과 같이 됩니다: 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

재귀의 힘

재귀는 일부 복잡한 문제를 훨씬 쉽게 해결할 수 있게 합니다. 약간 더 고급한 예제를 살펴보죠: 피보나치 수열.

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
print(fibonacci(i), end=" ")
# 출력: 0 1 1 2 3 5 8 13 21 34

이 함수는 nth 피보나치 수를 계산합니다. 피보나치 수열은 0과 1로 시작하며, 각 후속 숫자는 두 개의 이전 숫자의 합입니다.

재귀를 사용한 이진 탐색

이제 더 practical한 예제를 다루어보죠: 이진 탐색. 정렬된 리스트에서 항목을 찾는 효율적인 방법입니다.

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"요소는 인덱스 {result}에 존재합니다")
else:
print("요소는 배열에 존재하지 않습니다")

이 함수는 검색 구간을 반복적으로 절반으로 나누어 작동합니다. 검색 키의 값이 중간 항목보다 작으면 구간을 하위 절반으로 좁히고, 그렇지 않으면 상위 절반으로 좁힙니다. 값이 발견될 때까지 반복적으로 확인하거나 구간이 빈 상태가 될 때까지입니다.

언제 재귀를 사용해야 하나요

재귀는 특히 다음과 같은 경우에 유용합니다:

비슷한 서브 문제로 나눌 수 있는 문제
트리 구조의 데이터 구조 (예: 파일 시스템, HTML DOM)
QuickSort, MergeSort 등의 알고리즘

그러나 재귀가 항상 최선의 해결책은 아닙니다. 매우 깊은 재귀가 메모리를 많이 소비하고, 때로는 간단한 루프가 더 효율적이고 이해하기 쉬운 수단이 될 수 있습니다.

재귀 방법 표

방법	설명	예제
직접 재귀	함수가 직접 자신을 호출	우리의 `countdown`과 `factorial` 예제
간접 재귀	함수 A가 함수 B를 호출하고, 함수 B는 함수 A를 호출	아래 예제를 참조
꼬리 재귀	재귀 호출이 함수의 마지막 작업	우리의 `countdown` 예제
비꼬리 재귀	재귀 호출이 함수의 마지막 작업이 아님	우리의 `factorial` 예제

간접 재귀의 예제를 살펴보죠:

def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)

def is_odd(n):
return not is_even(n)

print(is_even(4))  # 출력: True
print(is_odd(4))   # 출력: False

이 예제에서, is_even는 is_odd를 호출하고, is_odd는 is_even를 호출합니다.

결론

축하합니다! 여러분은 재귀의 fas cinating 세계로 첫 걸음을 내딛었습니다. 기억해주세요, 강력한 도구처럼 재귀는 지혜롭게 사용되어야 합니다. 코드를 더 우아하게 만들고 복잡한 문제를 쉽게 해결할 수 있지만, 간단한 문제를 불필요하게 복잡하게 만들 수도 있습니다.

파이썬 여정을 계속하면서 재귀를 적용할 수 있는 많은 상황을 마주칠 거예요. 계속 연습하면서, 곧 재귀를 전문가처럼 사용할 수 있을 거예요!

Credits: Image by storyset