Python의 재귀 소개

프로그래밍의 재귀에 대해 모두 배우고 싶으십니까? Python의 재귀에 대한 이 튜토리얼은 시작하는 데 도움이 될 것입니다.

재귀는 프로그래머의 도구 상자에 추가할 수 있는 매우 유용한 문제 해결 기술입니다. 처음에는 이해하기 어려운 경우가 많지만 재귀를 사용하면 복잡한 문제에 대한 보다 우아한 솔루션을 찾는 데 도움이 될 수 있습니다.

이 튜토리얼에서는 Python을 사용하여 재귀를 학습하기 위한 코드 우선 접근 방식을 취하겠습니다. 특히 다음 내용을 다룹니다.

• 재귀의 기본
• 재귀 함수 및 작동 방식
• 재귀 함수의 Python 구현
• 문제 해결에 대한 반복적 접근 방식과 재귀적 접근 방식의 차이점

시작하자!

재귀란 무엇인가?

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

본질적으로 재귀는 복잡한 문제를 더 작고 동일한 하위 문제로 분해하는 문제 해결 접근 방식입니다. 본질적으로 이를 통해 문제 자체를 더 간단한 버전으로 해결할 수 있습니다.

그렇다면 코드에서 재귀를 어떻게 구현합니까? 그러기 위해 재귀 함수가 어떻게 작동하는지 이해해 봅시다.

재귀 함수 이해

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

재귀가 결국 종료되도록 하려면 재귀 함수에 하나 이상의 기본 사례(함수가 자체 호출을 중지하고 결과를 반환하는 조건)를 포함해야 합니다.

이것을 더 자세히 분석해 보겠습니다. 재귀 함수는 다음으로 구성됩니다.

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

다음으로, 재귀 함수를 호출할 때 어떤 일이 일어나는지 논의해 보겠습니다.

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

함수가 호출되면 해당 실행 컨텍스트의 기록이 호출 스택에 배치됩니다. 이 레코드에는 함수의 인수, 지역 변수 및 함수 실행이 완료되면 반환할 위치에 대한 정보가 포함됩니다.

재귀 함수의 경우 함수가 자신을 호출하면 새 레코드가 호출 스택에 푸시되어 현재 함수의 실행이 효과적으로 일시 중단됩니다. 스택을 사용하면 Python은 재귀 호출을 포함하여 보류 중인 모든 함수 호출을 추적할 수 있습니다.

기본 사례에 도달할 때까지 재귀는 계속됩니다. 기본 사례가 결과를 반환하면 함수 호출은 하나씩 해결되며 각 함수는 결과를 호출 스택의 이전 수준으로 반환합니다. 이 프로세스는 초기 함수 호출이 완료될 때까지 계속됩니다.

Python에서 재귀 구현

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

숫자의 계승 계산하기

피보나치 수 계산

재귀를 사용하여 이진 검색을 구현합니다.

각 예에 대해 문제를 설명하고 Python 재귀 구현을 제공한 다음 재귀 구현이 어떻게 작동하는지 설명합니다.

#1. 재귀를 사용한 계승 계산

문제: n!으로 표시되는 음이 아닌 정수 n의 계승을 계산하세요. 수학적으로 숫자 n의 계승은 1부터 n까지의 모든 양의 정수의 곱입니다.

다음과 같이 계승 계산은 재귀에 적합합니다.

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

def factorial(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

5를 계산해 봅시다! 계승() 함수를 사용하여:

factorial_5 = factorial(5)
print(factorial(5))
# Output: 120

이제 함수가 어떻게 작동하는지 살펴보겠습니다.

• n이 0 또는 1인지 확인하는 기본 사례가 있습니다. 조건이 충족되면 함수는 1을 반환합니다. 0을 기억하세요! 은 1이고, 1도 마찬가지입니다!.
• n이 1보다 크면 n을 계산합니다! n에 n-1의 계승을 곱하면 됩니다. 이는 n * 계승(n – 1)으로 표현됩니다.
• 이 함수는 기본 사례에 도달할 때까지 n 값을 감소시키면서 계속 재귀 호출을 수행합니다.

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

문제: n번째 색인에서 용어를 찾으세요. 피보나치 수열. 피보나치 수열은 다음과 같이 정의됩니다: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)(n >= 2).

def fibonacciSeq(n):
	# Base cases
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Recursion: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

함수를 실행해 봅시다:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Output: 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 값을 감소시키면서 계속 재귀 호출을 수행합니다.

#삼. 이진 검색의 재귀적 구현

문제: 정렬된 목록에서 대상 요소의 위치를 ​​찾기 위해 재귀를 사용하는 이진 검색 알고리즘을 구현하십시오.

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

def binarySearch(arr, target, low, high):
	# Base case: target not found
    if low > high:
        return -1

    mid = (low + high) // 2

	# Base case: target found
    if arr[mid] == target:
        return mid
	# Recursive case: search left or right half of the array
    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)
# Output: 4

함수가 수행하는 작업을 분석해 보겠습니다.

• 이진 검색 재귀 구현에는 두 가지 기본 사례가 있습니다. 첫째, low가 high보다 커지면 대상 요소가 목록에 없다는 의미입니다. 따라서 -1을 반환하여 대상을 찾을 수 없음을 나타냅니다.
• 다른 기본 사례는 현재 검색 간격의 중간 인덱스 mid에 있는 요소가 대상과 동일한지 확인합니다. 일치하는 경우 인덱스 mid를 반환하여 대상을 찾았음을 나타냅니다.
• 재귀적인 경우, 중간 요소가 대상보다 크면 BinarySearch(arr, target, low, mid – 1)를 호출하여 배열의 왼쪽 절반을 재귀적으로 검색합니다. 중간 요소가 대상보다 작으면 BinarySearch(arr, target, mid + 1, high)를 호출하여 오른쪽 절반을 검색합니다.

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

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

먼저, 일반적인 문제인 숫자의 계승 계산에 대한 재귀 및 반복 솔루션을 비교합니다.

계승 계산의 재귀적 구현은 다음과 같습니다.

def factorialRec(n):
	# Base case
    if n == 0 or n == 1:
        return 1
	# Recursive case: 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)
# Output: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120

그러나 반복적 접근 방식이 재귀보다 선호됩니까? 너무 많은 함수 호출로 인해 깊은 재귀가 발생하는 경우 재귀 깊이를 초과하여 오류가 발생할 수 있습니다. 반복 구현은 기본 사례에 도달하기 위해 너무 많은 함수 호출이 필요한 문제에 대해 더 나은 옵션입니다.

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

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

결론

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

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

다음으로 Python 인터뷰 질문 목록을 확인하세요.