Python의 재귀 소개

프로그래밍에서 재귀라는 개념에 대해 깊이 있게 알아보고 싶으신가요? 파이썬을 이용한 재귀 학습 가이드가 여러분의 여정을 시작하는 데 도움을 드릴 것입니다.

재귀는 프로그래머가 문제 해결 도구 상자에 추가할 수 있는 매우 강력한 기술입니다. 처음에는 다소 어렵게 느껴질 수 있지만, 재귀를 통해 복잡한 문제를 더욱 우아하고 효과적으로 해결할 수 있는 방법을 찾을 수 있습니다.

이 튜토리얼에서는 파이썬을 사용하여 재귀를 배우는 데 있어 코드를 중심으로 접근할 것입니다. 구체적으로 다음 내용들을 다룰 예정입니다.

  • 재귀의 기본 원리
  • 재귀 함수와 그 작동 방식
  • 파이썬에서의 재귀 함수 구현
  • 반복적 접근 방식과 재귀적 접근 방식의 차이점

자, 함께 시작해 볼까요!

재귀란 무엇인가?

재귀란 함수가 문제 해결을 위해 자기 자신을 반복적으로 호출하는 프로그래밍 기법입니다.

핵심적으로, 재귀는 복잡한 문제를 더 작고, 원래 문제와 동일한 형태의 하위 문제들로 분할하는 문제 해결 방식입니다. 이를 통해 문제 자체를 더 단순화된 형태로 해결해 나갈 수 있습니다.

그렇다면 코드에서 재귀를 어떻게 적용할 수 있을까요? 재귀 함수가 어떻게 동작하는지 먼저 이해해 봅시다.

재귀 함수 이해

재귀 함수는 자신의 정의 내에서 자신을 호출하는 함수입니다. 각 재귀 호출은 원래 문제보다 더 작거나 단순한 하위 문제를 나타냅니다.

재귀가 무한히 반복되지 않고 종료되도록 하려면 재귀 함수에는 하나 이상의 ‘기본 경우'(함수가 자체 호출을 멈추고 결과를 반환하는 조건)가 반드시 포함되어야 합니다.

좀 더 자세히 살펴보겠습니다. 재귀 함수는 다음 두 가지 주요 부분으로 구성됩니다.

  • 기본 경우: 기본 경우는 재귀를 멈춰야 할 시점을 결정하는 조건입니다. 이 조건이 충족되면 함수는 더 이상 자기 자신을 호출하지 않고 결과를 반환합니다. 무한 재귀를 방지하기 위해서는 기본 경우가 필수적입니다.
  • 재귀 경우: 재귀 경우는 문제를 더 작은 하위 문제로 분해하는 방법을 정의합니다. 함수의 이 부분에서 함수는 수정된 입력을 사용하여 자기 자신을 다시 호출합니다. 따라서 각 재귀 호출은 기본 경우에 도달하기 위한 하나의 단계입니다.

다음으로, 재귀 함수가 호출될 때 실제로 어떤 일이 일어나는지 살펴보겠습니다.

내부적으로 재귀가 작동하는 방식

함수가 호출되면 해당 함수의 실행 컨텍스트에 대한 기록이 호출 스택에 저장됩니다. 이 기록에는 함수의 인자, 지역 변수 및 함수 실행이 완료된 후 돌아갈 위치와 관련된 정보가 포함됩니다.

재귀 함수의 경우, 함수가 자기 자신을 호출할 때마다 새로운 기록이 호출 스택에 추가되고 현재 함수의 실행은 일시 중단됩니다. 스택을 사용함으로써 파이썬은 재귀 호출을 포함하여 보류 중인 모든 함수 호출을 추적할 수 있습니다.

재귀는 기본 경우에 도달할 때까지 계속됩니다. 기본 경우가 결과를 반환하면 함수 호출은 역순으로 하나씩 해결되며, 각 함수는 자신의 결과를 호출 스택의 이전 단계로 반환합니다. 이 과정은 최초의 함수 호출이 완료될 때까지 지속됩니다.

파이썬에서 재귀 구현

이 섹션에서는 재귀를 사용한 세 가지 간단한 예시를 살펴보겠습니다.

  • 숫자의 팩토리얼 계산
  • 피보나치 수열의 수 계산
  • 재귀를 이용한 이진 탐색 구현

각 예시에 대해 문제 설명, 파이썬 재귀 구현 코드, 그리고 해당 구현이 어떻게 작동하는지에 대한 설명을 제공할 것입니다.

#1. 재귀를 사용한 팩토리얼 계산

문제: 음이 아닌 정수 n의 팩토리얼(n!)을 계산합니다. 수학적으로 숫자 n의 팩토리얼은 1부터 n까지의 모든 양의 정수의 곱으로 정의됩니다.

팩토리얼 계산은 재귀를 적용하기에 매우 적합한 문제입니다.

다음은 주어진 숫자 n의 팩토리얼을 계산하는 재귀 함수입니다.

def factorial(n):
    # 기본 경우
    if n == 0 or n == 1:
        return 1
    # 재귀 경우: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

5!를 계산해 봅시다. factorial() 함수를 사용합니다:

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

이제 함수가 어떻게 작동하는지 분석해 보겠습니다.

  • n이 0 또는 1인지 확인하는 기본 경우가 있습니다. 이 조건이 만족되면 함수는 1을 반환합니다. 0!은 1이고 1!도 마찬가지입니다.
  • n이 1보다 크면 n!을 계산합니다. 이는 n에 n-1의 팩토리얼을 곱하여 얻을 수 있습니다. 이를 표현하면 n * factorial(n – 1)입니다.
  • 이 함수는 기본 경우에 도달할 때까지 n 값을 줄여가며 재귀 호출을 반복합니다.

#2. 재귀를 이용한 피보나치 수열

문제: n번째 인덱스의 피보나치 수열 값을 구합니다. 피보나치 수열은 다음과 같이 정의됩니다. F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2).

def fibonacciSeq(n):
    # 기본 경우
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 재귀: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

이제 함수를 실행해 봅시다:

fib_5 = fibonacciSeq(5)
print(fib_5)
# 출력: 5

함수의 작동 방식은 다음과 같습니다.

  • 기본 경우부터 살펴보겠습니다. n이 0이면 0을 반환하고 n이 1이면 1을 반환합니다. F(0) = 0과 F(1) = 1을 기억해 주세요.
  • 재귀 경우에서 n이 1보다 크면 함수는 F(n-1)과 F(n-2)를 더하여 F(n)을 계산합니다. 이는 fibonacciSeq(n – 1) + fibonacciSeq(n – 2)로 표현됩니다.
  • 이 함수는 기본 경우에 도달할 때까지 n 값을 줄여가며 재귀 호출을 반복합니다.

#3. 이진 탐색의 재귀적 구현

문제: 정렬된 리스트에서 재귀를 사용하여 대상 요소의 위치를 찾는 이진 탐색 알고리즘을 구현합니다.

이진 탐색의 재귀 구현은 다음과 같습니다.

def binarySearch(arr, target, low, high):
    # 기본 경우: 대상을 찾지 못함
    if low > high:
        return -1

    mid = (low + high) // 2

    # 기본 경우: 대상을 찾음
    if arr[mid] == target:
        return mid
    # 재귀 경우: 배열의 왼쪽 또는 오른쪽 절반을 탐색
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

binarySearch 함수는 대상을 찾거나 대상이 리스트에 없다고 판단할 때까지 각 재귀 호출에서 검색 범위를 반으로 줄여나갑니다.

다음은 함수 실행의 예시입니다:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# 출력: 4

함수가 어떻게 동작하는지 분석해 보겠습니다.

  • 이진 탐색의 재귀 구현에는 두 가지 기본 경우가 있습니다. 첫째, low가 high보다 커지면 대상 요소가 리스트에 없음을 의미합니다. 따라서 -1을 반환하여 대상을 찾을 수 없음을 알립니다.
  • 다른 기본 경우는 현재 검색 범위의 중간 인덱스 mid에 있는 요소가 대상과 같은지 확인하는 것입니다. 일치하는 경우 인덱스 mid를 반환하여 대상을 찾았음을 알립니다.
  • 재귀적인 경우, 중간 요소가 대상보다 크면 binarySearch(arr, target, low, mid – 1)를 호출하여 배열의 왼쪽 절반을 재귀적으로 탐색합니다. 중간 요소가 대상보다 작으면 binarySearch(arr, target, mid + 1, high)를 호출하여 오른쪽 절반을 탐색합니다.

재귀적 접근 방식과 반복적 접근 방식

루프를 사용하는 반복적 접근 방식은 문제 해결을 위한 또 다른 일반적인 방법입니다. 그렇다면 재귀와 어떻게 다를까요? 한번 알아보도록 하겠습니다.

먼저, 흔한 문제인 숫자의 팩토리얼 계산에 대한 재귀적 해법과 반복적 해법을 비교해 보겠습니다.

팩토리얼 계산의 재귀적 구현은 다음과 같습니다.

def factorialRec(n):
    # 기본 경우
    if n == 0 or n == 1:
        return 1
    # 재귀 경우: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

음이 아닌 숫자의 팩토리얼은 1부터 n까지 모든 수의 곱이라는 것을 알고 있으므로, 반복 구현도 루프를 사용하여 작성할 수 있습니다.

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

두 가지 구현 모두 동일한 결과를 제공합니다.

factorial_5 = factorialRec(5)
print(factorial_5)
# 출력: 120

factorial_5 = factorialIter(5)
print(factorial_5)
# 출력: 120

하지만 반복적 접근 방식이 재귀보다 선호될까요? 너무 많은 함수 호출로 인해 재귀 깊이가 너무 깊어지면 오류가 발생할 수 있습니다. 반복 구현은 기본 경우에 도달하기 위해 너무 많은 함수 호출이 필요한 문제에 더 좋은 선택입니다.

반복적 구현과 재귀적 구현의 차이점을 요약해 보겠습니다.

기능 재귀적 접근 방식 반복적 접근 방식
구조 재귀 함수 호출을 사용하고 호출 스택에 의존 추가 함수 호출 없이 반복을 위해 루프를 사용
기본 경우 재귀를 중지하려면 명시적인 기본 경우가 필요함 일반적으로 종료를 위해 루프 조건을 사용함
성능 호출 스택으로 인해 메모리 효율성이 떨어질 수 있음. 깊은 재귀는 스택 오버플로 오류를 유발할 수 있음 일반적으로 메모리 효율성이 더 높고, 스택 오버플로 오류 발생 가능성이 더 낮음
디버깅 여러 함수 호출과 중첩된 실행 컨텍스트 때문에 디버그하기 어려울 수 있음 일반적으로 간단한 선형 실행 흐름으로 인해 디버그하기 쉬움

결론

이 글에서는 재귀가 무엇인지, 기본 경우와 재귀 관계를 사용하여 재귀 함수를 정의하는 방법을 배우는 것부터 시작했습니다.

그런 다음 일반적인 프로그래밍 문제를 재귀적으로 구현하는 파이썬 코드를 작성했습니다. 마지막으로, 반복적 접근 방식과 재귀적 접근 방식의 차이점과 각 접근 방식의 장단점에 대해 학습했습니다.

다음으로 파이썬 인터뷰 질문 목록을 확인해 보세요.