递归的思路

傷城~ 2023-09-29 09:09 33阅读 0赞

#### 文章目录 ####

*  前言
 *  一、什么是方法递归？
 *  二、什么场景下能用递归？
 *  三、如何写出递归代码（\*\*重点\*\*）？
 *   *  1.先考虑这个函数的==终止条件==
     *  2.假设这个函数已经写好了（==注意这个方法的语义==）
 *  总结

--------------------

## 前言 ##

今天给老铁们回顾一下递归的思路以及方法，也是给自己的一个归纳总结。

## 一、什么是方法递归？ ##

> 所谓的方法递归，就是在一个方法（函数）执行的**内部**，**自己调用了自己**的过程，称之为 “递归” 。

递归分为两个子过程：  
递过程：函数不断地**调用自身**，直到走到函数的终止条件，第一阶段结束。  
归过程：函数不断地**返回**的过程。

> 例如, 我们求 N! 起始条件: N = 1 的时候, N! 为 1. 这个起始条件相当于递归的结束条件. 递归公式: 求 N! ,  
> 直接不好求, 可以把问题转换成 N! => N \* (N-1)!

示例：递归求N的阶乘

public static void main(String[] args) {
        
        int n = 5;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
    public static int factor(int n) {
        
        if (n == 1) {
        
            return 1;
       }
        return n * factor(n - 1); // factor 调用函数自身
    }
    // 执行结果
    ret = 120

## 二、什么场景下能用递归？ ##

a.一个**大问题**（这个方法的功能）可以拆分成若干个**子问题**的解.

b.拆分后的子问题和原问题除了数据规模不同，**解决思路完全相同**.

c.必须存在递归的**终止条件**（不会无限拆分下去，一定能走到底~）.

（看不懂先看下面(●ˇ∀ˇ●)）

## 三、如何写出递归代码（**重点**）？ ##

### 1.先考虑这个函数的终止条件 ###

比如上面的栗子：求N的阶乘。  
拿求5的阶乘做例子：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAS2lsbGluZyBWaWJl_size_20_color_FFFFFF_t_70_g_se_x_16]  
我们把大问题（5的阶乘）一直拆分到1的时候，问题无法继续拆分下去了，这个子问题就是这个递归的最终条件。  
所以我们写代码的时候，可以先把最终条件写上：

if (n == 1) {
        
            return 1;
       }

### 2.假设这个函数已经写好了（注意这个方法的语义） ###

在写递归函数的时候，千万不要纠结这个函数内部是如何实现的，而是要注意这个函数有什么功能（假设这个函数别人已经写好了），我们把它当作一个**黑盒子**，你只是去调用这个函数罢了。

public static int factor(int n)

比如这个函数只能传入一个**n**，目前我们只能知道这个n是多少，而n的阶乘等于**n\* \[(n-1)!\]**，但是我们并不知道**n-1的阶乘**是多少，那么就调用这个别人写好的“黑盒子”。这个黑盒子的功能可以**实现某个数的阶乘**。

n * factor(n - 1) // n*黑盒子

说白了就是，把这个factor函数当作别人已经写好了，你只需要关注如何去调用这个方法去辅助你解决问题就可以了！

## 总结 ##

写出递归其实=终止条件+利用黑盒子去解决剩下的问题，注意传入的参数就可以很快把递归代码写出来(●ˇ∀ˇ●)。老铁们如果有帮助的话记得三连哟~

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAS2lsbGluZyBWaWJl_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/be65771c20c44f86b6277ab638a921f0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS2lsbGluZyBWaWJl,size_20,color_FFFFFF,t_70,g_se,x_16