【JavaSE】递归_Java SE

seven_ • 2023年2月28日上午10:52 • 后端笔记 • 阅读 62

目录

1.递归的思想

1.1 递归的两个条件

1.2递归的三要素

1.3 递归:自已（方法）调用自已

1.4 递归算法的一般形式：

1.5 例子

2.递归的过程

3.递归的理解

愿路途漫长，以后莫失莫忘。愿你不骄不躁，安稳顺心。

1.递归的思想

具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

1.1 递归的两个条件

可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。（自身调用）

存在一种简单情境，可以使递归在简单情境下退出。（递归出口）

1.2递归的三要素

一定有一种可以退出程序的情况；

总是在尝试将一个问题化简到更小的规模

父问题与子问题不能有重叠的部分

1.3 递归:自已（方法）调用自已

//求n的阶乘
public static int fac(int n){
        if(n==1){
            return 1;
        }
        int tmp=n*fac(n-1);
        return tmp;
    }

1.4 递归算法的一般形式：

//求某个整数各个位的和 例如 123=1+2+3
public static void print(int n){
        if(n<10){
            System.out.println(n);
        }else{
            print(n/10);
            System.out.println(n%10);
        }
    }

1.5 例子

//斐波那契
    public static int fib(int n){
        if (n == 1 ||n==2) {
            return 1;
        }else {
            int tmp=fib(n-1)+fib(n-2);
            return tmp;
        }
    }

2.递归的过程

我们会惊奇的发现这个过程和栈的工作原理一致对，递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现，这个过程是由系统来完成的。

那么递归中的“递”就是入栈，递进；“归”就是出栈，回归。

3.递归的理解

/*
 关于 递归中 递进和回归的理解*/
public static void recursion_display(int n) {
    int temp=n;//保证前后打印的值一样
     System.out.println("递进:" + temp);
    if (n > 0) {
        recursion_display(--n);
    }
    System.out.println("回归:" + temp);
}