재귀적 기본 요소를 넘어서는 기능을 위한 스프링보드? Ackermann Peter 기능 구현

스프링보드 기술을 탐색할 때 처음에는 단 하나의 재귀가 있는 더 간단한 상황에서 사용했습니다. 아마도 원시 재귀 함수의 적절한 하위 집합일 것입니다. 그러나 직장에서 매우 긴 계산을 수행해야 할 필요성이 생겼습니다. 첫 번째 아이디어는 busy beaver 함수였지만, 계산 복잡도가 높고 익숙하지도 않았습니다. 그런 다음 더 잘 알려진 함수인 Ackermann-Peter 함수를 선택했습니다.

아커만-피터 함수

이것은 두 개의 정수 인수를 입력으로 사용하는 이해하기 쉬운 함수입니다.

int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}

자세한 내용은 Wikipedia 페이지 또는 WolframAlpha를 참조하세요.

기능 사용하기

테스트ackermannPeter(3, 3) 결과가 정확하게 계산되었습니다. 그런데 ackermannPeter(4, 3) 실행시 스택 폭발이 발생했습니다. Ackermann-Peter 함수에 대한 재귀 호출의 깊이는 매우 큽니다. 단순히 첫 번째 인수를 3에서 4로 변경하면 61이었던 출력이 $2^{2^{65536}} - 3$.

스택 제한 극복

문제는 스택을 빠르게 소진시키는 Ackermann-Peter 함수의 강렬한 재귀에 있습니다. 해결책은 연속 작업을 사용하여 스택 과부하를 방지하고 스프링보드 아이디어를 구현하는 것입니다.

트램폴린을 밟을 때 세 가지 행동이 필요합니다.

• 계산이 끝났는지 표시합니다.
• 계산된 값을 반환합니다.
• 한 단계를 실행하고 다음 연속을 얻습니다.

우리의 경우(정수 반환):

interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}

트램폴린 그 자체:

static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}

Ackermann-Peter 함수에 적용: 함수는 기본 사례, 단순 재귀, 이중 재귀의 세 가지 경우로 나뉩니다. 스프링보드는 두 번째 재귀의 결과를 제어해야 합니다. 이를 위해 두 번째 인수는 Continuation이 됩니다. n이 이미 완료된 경우 프로세스는 정상적으로 계속됩니다. 그렇지 않으면 계속되는 단계에서 새 단계가 생성됩니다.

private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}

메모 추가

메모하면 성능이 향상됩니다. 두 가지 상황: 1) 결과가 이미 메모리에 있습니다. 2) 다음 단계에서는 현재 결과를 추론할 수 있습니다. 메모이제이션은 두 번째 인수의 연속을 해결한 후 적용됩니다. HashMap 및 long 키(m 및 n 결합)를 사용한 메모이제이션 구현이 제시되어 재귀 호출 수가 크게 감소한 것으로 나타났습니다. 최종 버전에서는 HashMap를 인수로 전달하여 전역 메모리 종속성을 제거합니다.

위 내용은 재귀적 기본 요소를 넘어서는 기능을 위한 스프링보드? Ackermann Peter 기능 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!