好好理解 Java 中的递归

朴灿烈づ我的快乐病毒、 2022-12-23 07:25 129阅读 0赞

# 递归的思想 #

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

**一句话总结：递归就是自己调用自己。**

# 递归的条件要素 #

1、递归有两个重要条件，

*  可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。**（自身调用）**
 *  存在一种简单情境，可以使递归在简单情境下退出。**（递归出口）**

2、递归的三要素，

*  尝试将一个问题化简到更小的规模
 *  父问题与子问题不能有重叠的部分
 *  一定有一种可以退出程序的情况

# 递归的算法结构 #

递归的常用算法伪代码如下：

func( mode){
        if(endCondition){      //递归出口
              end;
        }else{
             func(mode_small)  //调用本身，递归
        }
    }

# 递归实战举例 #

递归讲起来还是有点小抽象，我们直接来看代码，

**1、斐波那契数的递归实现**

斐波那契数列的递推公式：Fib(n)=Fib(n-1)+Fib(n-2)，生成数列（1、1、2、3、5、8...）。

public static int fib(int n) throws Exception {
        if (n < 0){
            throw new Exception("请输入正确的参数");
    	  } else if (n == 0 || n == 1){
            return n;
    	  } else {
            return fib(n - 1) + fib(n - 2); // 调用自己
    	  }
    }

**2、99乘法表的递归实现**

public static void mul(int n){
            if(n==1){
                System.out.println("1*1=1");
            }else {
                mul(n -1);
                for(int i=1;i<=n;i++){
                    System.out.println(i + "*" + n + "=" + i*n + " ");
                }
            }
        }

# 总结 #

递归算法是一种直接或间接地调用自身的算法。如果一个问题可以解可以分解为几个子问题的解； 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样；并且存在明显的递归终止条件；那么递归将是一种不错的选择。