트램펄린, Java의 예

n부터 0까지 숫자를 더하는 간단한 프로그램을 작성해 보겠습니다. 하지만 반복적 접근 방식 대신 재귀적 접근 방식을 사용해 보는 것은 어떨까요?

이 프로그램을 sum이라고 부릅니다. 우리는 sum(0) == 0을 알고 있으므로 이것이 기본 사례입니다. 기본 사례에 어떻게 도달합니까? sum(n) == n sum(n-1), 마침내 sum(0)에 도달할 때까지. 자바 코드는 다음과 같습니다.

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

재귀 문제가 있나요?

재귀에는 기본 사례가 입력 값에서 멀리 떨어져 있을 때 고유한 결함이 있습니다... 대부분의 언어에서 함수 호출은 프로그램의 스택을 사용하여 함수 호출 정보를 저장하므로 매우 큰 재귀로 인해 스택 오버플로가 발생할 수 있습니다.

그런데, 이를 피할 수 있는 방법이 있을까요? 실제로 그렇습니다. 이것은 트램폴린이라는 오래된 전략입니다.

스프링보드

스프링보드 전략의 기본 아이디어는 프로그램의 일부가 "값" 또는 "연속"을 반환한다는 것입니다. 계속이란 무엇입니까? 처리를 계속하는 함수입니다.

대략 다음과 같습니다.

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum의 연속은 무엇인가요?

프로그램을 다음과 같이 모델링sum하겠습니다. 단순히 반복하는 대신 연속을 사용합니다. 한 가지 방법은 acc을 연속을 통해 전달되는 객체로 사용하는 것입니다. 따라서 sum_trampoline(0, acc)에 도달하면 acc을 반환합니다. 진행하는 방법?

sum_trampoline(n, acc)에서 sum_trampoline(n-1, acc n)으로 가보겠습니다. 첫 번째 입력은 sum_trampoline(n, 0)입니다.

그래서 코드는 다음과 같습니다.

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

유형을 사용하여 스프링보드 설명

스프링보드는 대략 다음과 같은 형식이어야 합니다.

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

그러나 이는 코딩의 자유를 많이 제공하며 Java 세계에서는 그다지 직관적이지 않습니다. 객체에 물어보면 연속인지 확인할 수 있습니다. "값을 찾았나요?"라고 묻는다면 어떨까요? 또 다른 점은 Java에는 합계 유형이 없기 때문에 return trampolim는 값을 반환하는 대신 실제로 trampolim 유형을 반환한다는 것입니다. trampolim.value()으로 돌아갈 수 있습니다.

마지막으로 포인트는 스프링보드의 부트스트래핑입니다. 이를 위해 함수를 사용하여 입력을 적절한 포고 반환 값으로 변환할 수 있습니다. 더 나은 사용을 위해 입력과 결과를 일반화할 수 있습니다.

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<R>인터페이스는 어떻습니까?

세 가지 방법을 정의합니다.

• gotValue: 값을 찾았는지 묻습니다.
• value: 찾은 값을 반환합니다.
• runNextStep: 값 또는 연속을 반환합니다.

기본적으로 두 가지 상태가 있습니다.

• 찾은 값
• 연속입니다

따라서 정적 메소드를 사용하여 초기화할 수 있습니다. 값이 발견된 경우 값을 전달해야 합니다.

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

연속의 경우 다음 연속 항목을 가져오는 방법을 전달해야 합니다.

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampoline이를 어떻게 달성할 수 있나요?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

테일콜 피보나치

피보나치의 고전적인 구현은 재귀적 정의를 따릅니다.

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

피보나치 정의를 재귀적으로 확장하지 않고 앞으로 확장하는 반복 버전도 있습니다. 0과 1에서 시작하여 해당 값에 도달할 때까지:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

"테일 호출 재귀"를 사용하는 이 구현의 정방향 버전이 있습니다.

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

여기에서는 테일 콜 재귀 피보나치에 사용될 숫자를 준비하는 입력 인터페이스를 분리합니다. 앞으로 나아가면서 fib[0] => 0, fib[1] => 1 매핑으로 시작하여 인덱스 0부터 인덱스 n에 도달할 때까지 탐색합니다.

피보나치: 테일 콜에서 스프링보드까지

fib_tc의 예는 피보나치 스프링보드를 잘 보여줍니다.

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

이것은 단지 뼈대일 뿐이며 컴파일하고 실행하려면 TrampolineStep 인터페이스의 완전한 구현과 trampoline 함수의 완전한 구현이 필요합니다. 또한 IN을 특정 입력 유형으로 바꿔야 합니다.

위 내용은 트램펄린, Java의 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!