재귀 -1-java지도 시간-php.cn

소개 1

함수가 자신을 호출하는 과정을 재귀라고 하며
해당 함수를재귀함수라고 합니다.
컴퓨터 프로그래밍은 수학의 기본 응용이므로, 먼저 재귀 뒤에 숨어 있는 수학적 추론을 이해하려고 노력하세요.
일반적으로 우리 모두는 함수의 개념을 알고 있습니다. 간단히 말해서 함수는
입력을 제공할 때 출력을 생성하는 수학 방정식. 예를 들면:
함수 F(x)가 다음과 같이 정의된 함수라고 가정합니다. F(x) = x^2 + 4
이 함수에 대한 Java 코드를 다음과 같이 작성할 수 있습니다.

public static int F(int x){

반환(x * x + 4);
}

이제 다양한 x 값을 이 함수에 전달하고 출력을 받을 수 있습니다

따라서.
재귀로 넘어가기 전에, 또 다른 수학적 개념을 이해해 봅시다

수학적 귀납법(PMI)의 원리.로 알려진 개념

수학적 귀납법(PMI)의 원리는 다음과 같은 명제를 증명하는 기법입니다.

공식, 또는 일련의 자연수에 대해 주장되는 정리. 그것은
다음 세 단계를 따르세요:
1.** 사소한 사례의 단계*
: 이 단계에서는에 대해 원하는 진술을 증명할 것입니다. n = 0 또는 n = 1과 같은 기본 사례입니다.
2.
* 가정 단계**: 이 단계에서는 원하는 진술이n = k에 유효합니다.

증명 단계: 가정 단계의 결과를 통해 다음을 증명하겠습니다. n = k + 1은 n = k가 참일 때마다 원하는 방정식에 대해서도 참입니다.

예: 수학적 귀납법을 사용하여 증명해 보겠습니다.

S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(처음 N개의 자연수의 합)
증거:
1단계: N = 1인 경우 S(1) = 1이 참입니다.
2단계: 주어진 진술이 N = k에 대해 참이라고 가정합니다. 즉,
1 + 2 + 3 + .... + k = (k * (k + 1))/2
3단계: 2단계를 사용하여 N = k + 1에 대한 명제를 증명해 보겠습니다.

증명: 1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2

증거:

2단계에서 얻은 결과의 LHS와 RHS 모두에 (k+1)을 추가합니다.

1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

이제 RHS 측에서 (k+1) 공통을 취합니다:

1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

우리가 증명하려고 하는 진술에 따르면:

1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
따라서 증명되었습니다.

재귀 작업

위의 세 가지를 요약하여 재귀적 접근 방식의 단계를 정의할 수 있습니다

단계:
● 기본 사례: 재귀 함수에는 다음과 같은 종료 조건이 있어야 합니다.
프로세스 자체 호출이 중지됩니다. 이러한 경우를 기본 사례라고 합니다. 기본 사례가 없으면 계속해서 자신을 호출하고
에 갇히게 됩니다. 무한 루프. 곧 재귀 깊이*를 초과하여 오류가 발생합니다
오류가 발생했습니다.
● 재귀 호출: 재귀 함수는 더 작은 버전에서 자체적으로 호출됩니다
주요 문제의. 이 단계는 그대로 쓸 때 주의가 필요해요
작은 문제가 무엇인지 정확하게 파악하는 것이 중요합니다.
● 소규모 계산: 일반적으로 각 재귀에서 계산 단계를 수행합니다
부르다. 재귀 호출 전후에 이 계산 단계를 수행할 수 있습니다
문제의 성격에 따라 다릅니다.

Note: 재귀는 재귀 호출을 저장하는 내장 스택을 사용합니다. 따라서메모리 오버플로를 방지하려면 재귀 호출 수를 가능한 한 줄여야 합니다. 만약
재귀 호출 횟수가 최대 허용량을 초과했습니다. **재귀 깊이
**가 초과됩니다.
이제 재귀를 사용하여 몇 가지 일반적인 문제를 해결하는 방법을 살펴보겠습니다
문제 설명 - 숫자의 계승값 찾기

접근 방식: PMI의 3단계를 파악한 후 이를 사용하여 연관시키기

재귀

귀납 단계: 숫자 n - F(n)의 계승 계산 유도 가설: 우리는 이미 n-1 - F(n-1)