소개 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단계를 파악한 후

를 사용하여 동일한 단계를 연관시킵니다. 재귀

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

공개 정적 int 사실(int n){

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

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

위에서 볼 수 있듯이 우리는 이미 n = 0, 즉 1이라는 답을 알고 있습니다. 따라서 다음과 같이 하겠습니다.

이것을 기본 케이스로 유지하세요. 따라서 코드는 이제 다음과 같습니다:

public static int 계승(int n){

if (n == 0) // 기본 사례
1을 반환;
또 다른
n*factorial(n-1)을 반환합니다. // 재귀적 사례
}