재귀 -1

소개 1

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

공개 정적 정수 F(int x){
반환(x * x + 4);
}

이제 다양한 x 값을 이 함수에 전달하고 출력을 받을 수 있습니다
그에 따라.
재귀로 넘어가기 전에 또 다른 수학적 개념을 이해해 봅시다
수학적 귀납법(PMI)

으로 알려진 개념

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

1. 증명 단계: 가정 단계의 결과를 통해 다음을 증명하겠습니다. 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
이로써 입증되었습니다.

재귀 작업

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

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

문제 설명 - 숫자의 계승 찾기

접근 방식: PMI의 3단계를 파악한 후 동일한 내용을 사용하여 연결
재귀

1. 도입 단계: 숫자 n - F(n)의 계승 계산 유도 가설: 우리는 이미 n-1 - F(n-1)의 계승을 얻었습니다
2. F(n-1)로 F(n)을 표현하면: F(n)=n*F(n-1). 따라서 우리는

공개 정적 int 사실(int n){
int ans = 사실(n-1); #가정단계
ans * n을 반환합니다; #가정단계부터 문제해결
}

1. 코드가 아직 완성되지 않았습니다. 누락된 부분은 기본 케이스입니다. 이제 우리는 재귀를 중지해야 하는 경우를 찾기 위해 연습 실행을 수행합니다. n = 5를 고려하세요:

위에서 볼 수 있듯이 우리는 이미 n = 0, 즉 1이라는 답을 알고 있습니다. 따라서 그렇게 하겠습니다
이것을 기본 케이스로 유지하세요. 따라서 코드는 이제 다음과 같습니다.

공용 정적 int 계승(int n){
if (n == 0) // 기본 사례
1을 반환;
그 외
n*factorial(n-1)을 반환합니다. // 재귀적 사례
}

위 내용은 재귀 -1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!