1. 일반인의 관점에서 재귀 함수는 함수 자체가 자신을 호출한다는 의미입니다.
예: n!=n(n-1)!
f(n)=nf(n-1) 함수를 정의합니다.
그리고 f(n-1)은 이 정의의 함수입니다. . 이것이 재귀이다
2. 재귀를 사용하는 이유: 재귀의 목적은 프로그램 설계를 단순화하고 프로그램을 더 읽기 쉽게 만드는 것입니다.
3. 재귀의 단점: 비재귀 함수는 효율성은 높지만 프로그래밍이 어렵고 가독성이 좋지 않습니다. 재귀 함수의 단점은 시스템 오버헤드가 증가한다는 것입니다. 즉, 재귀될 때마다 스택 메모리가 더 많은 공간을 차지합니다.
4. 재귀 조건: 작업을 완료하기 위한 명령문이 있어야 하며, 재귀 요구 사항이 충족되어야 합니다(발산보다는 감소).
5. 재귀적 발전:
1. 재귀를 사용하여 n의 계승을 계산합니다.
분석: n!=n*(n-1)*(n-2)...*1
공개 int dReturn(int n){ if(n==1){ return 1; }else{ return n*dReturn(n-1) } }2. 재귀 함수를 사용하여 1에서 n까지의 누적을 계산합니다. 1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1; }else{ return n+dReturn(n-1) } } 3. 1,1,2,3,5,8,11...의 시퀀스를 출력해야 합니다. (각 숫자는 이전 두 숫자의 합이며 재귀 함수가 필요합니다.)
함수를 표현하기 위해 자바 재귀를 사용하세요: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
분석: X1=1; X2=1; X3=X1+X2;
공개 int F(int n){ if(n==1){ 반환 1; }else if(n==2){ 반환 1 }else{ 반환 F(n-1)+F(n-2); } }4.Java는 재귀적 방법을 사용하여 정수 배열의 각 요소를 역방향으로 인쇄합니다.
public static void printAll(int index,int[] arr){ System.out.println(arr[index]); if(index > 0){ printAll(--index,arr) } } public static void main(String [] args){ int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr) }5. 프로그래밍 솔루션: 암소가 태어난 지 4년차부터 매년 소 한 마리를 낳는다면, n년차에는 몇 마리의 소가 있습니까?
public static int sheep(int n){ if(n<=0){ return 0; else if(n<=3){ return 1 }else{ return sheep(n-1)+cattle(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"연도 이후에는 총 "+cattle(n)+"소"가 있을 것입니다) }재귀, 선형 재귀, 꼬리 재귀의 개념은 무엇입니까?
Java에서 재귀 함수 호출 - 숫자의 계승 찾기
오버플로는 고려되지 않습니다. 일반적으로 69의 계승만 계산할 수 있습니다.
참고: 0의 계승은 0입니다! =1
1보다 큰 자연수 n의 계승 표현:
n!=1×2×3×……×n
아니면 n!=n×(n-1)!
0의 계승을 검색하면 매우 유용한 온라인 계산기가 나타납니다! !
package test;import java.util.Scanner;public class DiGui {public static void main(String[] args) {// TODO 자동 생성 메소드 stubSystem.out.println("정수 입력:");Scanner scan = new Scanner(System.in);int x = scan.nextInt();int result = digui(x);System.out.println(result);}//재귀 함수 public static int digui(int x){if(x <=0){return 1;}else{return x*digui(x-1);}}}재귀: 프로세스나 함수에는 정의나 설명에서 자신을 직접 또는 간접적으로 호출하는 방법이 있습니다. 일반적으로 크고 복잡한 문제를 해결하려는 원래 문제와 유사한 작은 문제로 변환합니다. 이 사례는 재귀가 복잡한 문제를 더 작은 문제로 변환하여 해결하는 방법을 명확하게 보여줍니다. 다음은 재귀의 원리를 설명하는 작은 예입니다.
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/public class Test { static int곱하기( int n) { int 계승; // ?? if ((n == 1) || (n == 0)) { 계승 = n; } else { 계승 = n * 곱셈(n - 1); ; } 공개 정적 void main(String[] args) { System.out.println(multiply(5)); 함수가 호출되면 해당 변수를 위한 공간이 런타임 스택에 생성됩니다. 이전에 호출된 함수의 변수는 스택에 남아 있지만 새 함수의 변수에 의해 가려져 액세스할 수 없습니다.
프로그램의 함수에는 매개변수 n과 지역 변수 계승이라는 두 가지 변수가 있습니다. 다음 다이어그램은 현재 액세스 가능한 변수가 맨 위에 있는 스택의 상태를 보여줍니다. 다른 모든 호출된 변수는 회색으로 표시되어 현재 실행 중인 함수에서 액세스할 수 없음을 나타냅니다.
값 5를 사용하여 재귀 함수를 호출한다고 가정합니다. 스택의 내용은 다음과 같습니다. 스택의 맨 위가 맨 아래에 있습니다.
n 곱하기(n) 계승 5 곱하기(5) 5*multiply(4) //첫 번째 호출 4 곱하기(4) 4*multiply(3) //두 번째 호출 3 곱하기(3) 3*multiply(2 ) // 세 번째 호출 2 곱하기(2) 2*multiply(1) //네 번째 호출 1 곱하기(1) 1 //다섯 번째 호출
위의 정보를 통해 재귀가 점차적으로 문제를 최소화하여 문제를 해결하는 방법을 쉽게 알 수 있습니다. 메소드 호출부터 시작하여 메소드 호출이 끝날 때까지 계승 결과가 스택에 푸시되고 최종적으로 결과가 하나씩 반환됩니다. 스택의 상단에서. 하나씩 대체한 후 결과는 다음과 같습니다.
n=1 1은 위쪽으로 1을 반환합니다.
n=2 2*multiply(1)은 2*1=2 위쪽을 반환합니다.
n=3 3*multiply(2)는 3*(2*1)=6 위쪽을 반환합니다.
n=4 4*multiply(3)은 4*(3*(2*1))=24를 위쪽으로 반환합니다.
n=5 5*multiply(4)는 위쪽으로 5*(4*(3*(2*1)))=120을 반환합니다.
참고: 곱하기(1) 또는 곱하기(0)는 1의 값을 반환하기 때문에
따라서 2*곱하기(1)=2*1=2가 됩니다.
그리고 Multiply(2)는 재귀 조건을 만족하므로 재귀 이후에는 2*multiply(1)로 변환될 수 있습니다.
따라서 3*곱하기(2)=3*(2*곱하기(1))=3*(2*1)=6이 됩니다.
재귀 이후에 곱하기(3)는 3*곱하기(2)로 줄어들 수 있기 때문입니다.
따라서 곱하기(4)=4*곱하기(3)=4*(3*곱하기(2))=4*(3*(2*1))=24
비유하자면 곱하기(5)=5*곱하기(4)
5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120으로 줄일 수 있습니다.
바이트코드 정보를 살펴보겠습니다.
공용 클래스 테스트 확장 java.lang.Object{ 공용 테스트(); 코드: 0: aload_0 1: 호출특수 #1; //메소드 java/lang/Object."<init>":()V 4: 정적 int 곱셈 반환 (int); 코드: 0: iload_0 1: Iconst_1 //int 유형 상수 1을 스택 2에 푸시: if_icmpeq 9 //두 int 유형 값을 비교하여 동일하면 위치 9로 점프합니다. 이는 || function 5: iload_0 //첫 번째 조건이 성립하지 않을 때 실행되며, 지역 변수 0에서 int 유형 값을 로드합니다(n 값을 스택에 푸시) 6: ifne 14 //비교, 그렇지 않은 경우 0과 같음 , 위치 14로 점프합니다. 참고: 여기서 기본 비교는 0이므로 상수 0을 스택에 푸시할 필요가 없습니다. 9: iload_0 //ifne에서 점프가 없으면 로컬 변수 0에서 int를 로드합니다. 값 입력 (n의 값을 스택에 push) 10: istore_1 //int형 값을 로컬 변수 1에 저장 (스택의 맨 위에서 튀어나온 값은 로컬 변수 0에 의해 스택에 푸시된 값이고, 이후 저장됨) in 지역 변수 1) 11: goto 23 //위치 23으로 무조건 점프 14: iload_0 //위치 6에서 비교, 0이 아닌 경우 이 명령을 실행하고 지역 변수 0에서 int 유형 값을 로드합니다(n 값을 푸시합니다) 15 : iload_0 //지역 변수 0에서 int 유형 값을 로드합니다(n 값을 스택에 푸시) 16: Iconst_1 //int 유형 상수 1을 스택에 푸시합니다. 상수 1은 n의 1입니다. -1 코드에서 17: isub / /뺄셈 연산 수행, n-1 18: callstatic #2; //곱셈 메소드:(I)I, 메소드 곱셈 호출 21: imul //곱셈 연산 수행, n * Multiply(n - 1) 22: istore_1 //int 유형의 값이 지역 변수 1에 저장됩니다, 계승=... 23: iload_1 //지역 변수 1에서 int 유형 값을 로드합니다(factorial의 결과를 스택에 푸시합니다) 24 : ireturn //메소드는 public static void main( java.lang.String[]); 코드: 0: getstatic #3 //Field java/lang/System.out:Ljava/io/PrintStream 3: icont_5; : 호출정적 #2; //메소드 곱하기:(I )I 7: 호출가상 #4; //메소드 java/io/PrintStream.println:(I)V 10: return }