Python에서 효율적인 합계를 위해 테일 호출 재귀를 구현하는 방법은 무엇입니까?

Python의 재귀: 이해를 위한 가이드

정수 목록을 합산하는 재귀 함수

라는 재귀 함수를 만들어야 한다고 가정해 보겠습니다. 목록에 있는 모든 정수의 합계를 계산하는 "listSum"입니다. 목표는 내장된 기능을 사용하지 않고 이를 수행하는 것입니다. 먼저, 함수의 결과를 그 자체로 어떻게 표현할 수 있을지 고민해야 합니다.

이 경우, 동일한 함수를 호출한 결과에 첫 번째 숫자를 더하면 결과를 얻을 수 있습니다. 목록의 나머지 요소. 재귀적으로 이는 다음과 같이 표현될 수 있습니다.

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

재귀의 기본 사례는 목록이 비어 있고 결과가 0이 필요한 이벤트입니다. Python 코드에서 이 접근 방식을 구현하는 경우:

<code class="python">def listSum(ls):
    if not ls:
        return 0
    return ls[0] + listSum(ls[1:])</code>

테일 호출 재귀

이전 구현은 이전 함수 호출의 값에 따라 실제 결과를 계산합니다. 이는 Tail Call Recursion을 사용하여 개선할 수 있습니다.

<code class="python">def listSum(ls, result):
    if not ls:
        return result
    return listSum(ls[1:], result + ls[0])</code>

추가 매개변수 결과를 도입하여 그 안에 합계를 누적하고 기본 조건이 충족되면 반환합니다.

Passing Around Index

중간 목록이 여러 개 생성되는 것을 방지하기 위해 처리할 항목의 색인을 전달할 수 있습니다.

<code class="python">def listSum(ls, index, result):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

기본 조건은 색인이 목록의 길이에 도달했는지 확인합니다.

내부 함수 버전

매개변수 전달을 단순화하기 위해 내부 함수를 사용할 수 있습니다.

<code class="python">def listSum(ls):
    def recursion(index, result):
        if index == len(ls):
            return result
        return recursion(index + 1, result + ls[index])
    return recursion(0, 0)</code>

내부 함수 재귀는 인덱스 및 결과 매개변수를 허용하고 listSum은 반환합니다. 초기값으로 내부 함수를 호출한 결과.

기본 매개변수 버전

기본 매개변수를 사용하면 더욱 단순화됩니다.

<code class="python">def listSum(ls, index=0, result=0):
    if index == len(ls):
        return result
    return listSum(ls, index + 1, result + ls[index])</code>

기본값은 인덱스 및 호출자가 명시적으로 지정하지 않은 경우 발생합니다.

재귀 거듭제곱 문제

밑의 값을 지수의 거듭제곱으로 반환하는 거듭제곱(밑, 지수) 계산 문제를 생각해 보세요. 재귀적으로 해를 정의할 수 있습니다.

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

기본 조건은 지수가 1 이하가 되는 경우이며, 이 경우 결과는 기본 자체입니다.

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

Python의 구현 :

<code class="python">def power(base, exponent):
    if exponent <= 1:
        return base
    return base * power(base, exponent - 1)</code>

Tail Call 최적화 버전의 기본 매개변수 사용:

<code class="python">def power(base, exponent, result=1):
    if exponent <= 0:
        return result
    return power(base, exponent - 1, result * base)</code>

위 내용은 Python에서 효율적인 합계를 위해 테일 호출 재귀를 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!