递归算法流程图（递归详解）

/ 0评 / 0赞

递归算法流程图（递归详解）

前言

递归是一种非常主要的算法思想，无论你是前端开发，还是后端开发，都须要控制它。在日常工作中，统计文件夹大小，解析xml文件等等，都须要用到递归算法。它太基本太主要了，这也是为什么面试的时候，面试官经常让我们手写递归算法。本文呢，将跟大家一起学习递归算法~

什么是递归？

递归，在盘算机科学中是指一种通过反复将问题分解为同类的子问题而解决问题的办法。简略来说，递归表示为函数调用函数本身。在知乎看到一个比方递归的例子，个人认为非常形象，大家看一下：

❝

递归最适当的比方，就是查词典。我们应用的词典，本身就是递归，为懂得释一个词，须要应用更多的词。当你查一个词，发明这个词的说明中某个词仍然不懂，于是你开端查这第二个词，惋惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的说明是你完整能看懂的，那么递归走到了止境，然后你开端后退，逐个明确之前查过的每一个词，最终，你明确了最开端那个词的意思。

❞

来试试水，看一个递归的代码例子吧，如下：

public int sum(int n) {    if (n <= 1) {        return 1;    }     return sum(n - 1) + n; }

递归的特色

实际上，递归有两个明显的特点,终止条件和自身调用:

联合以上demo代码例子，看下递归的特色：

递归与栈的关系

其实，递归的进程，可以懂得为出入栈的进程的，这个比方呢，只是为了便利读者朋友更好懂得递归哈。以上代码例子盘算sum（n=3）的出入栈图如下：

为了更容易懂得一些，我们来看一下 函数sum（n=5）的递归履行进程，如下：

递归的经典运用场景

哪些问题我们可以斟酌应用递归来解决呢？即递归的运用场景一般有哪些呢？

递归解题思路

解决递归问题一般就三步曲，分离是：

这个递归解题三板斧懂得起来有点抽象，我们拿阶乘递归例子来喵喵吧~

1.定义函数功效

定义函数功效，就是说，你这个函数是干嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？比如你须要解决阶乘问题，定义的函数功效就是n的阶乘，如下：

//n的阶乘（n为大于0的自然数）int factorial (int n){}

2.寻找递归终止条件

递归的一个典范特点就是必需有一个终止的条件，即不能无穷循环地调用本身。所以，用递归思路去解决问题的时候，就须要寻找递归终止条件是什么。比如阶乘问题，当n=1的时候，不用再往下递归了，可以跳出循环啦，n=1就可以作为递归的终止条件，如下：

//n的阶乘（n为大于0的自然数）int factorial (int n){    if(n==1){      return 1;    }}

3.递推函数的等价关系式

递归的「本义」，就是原问题可以拆为同类且更容易解决的子问题，即「原问题和子问题都可以用同一个函数关系表现。递推函数的等价关系式，这个步骤就等价于寻找原问题与子问题的关系，如何用一个公式把这个函数表达清晰」。阶乘的公式就可以表现为 f(n) = n * f(n-1), 因此，阶乘的递归程序代码就可以写成这样，如下：

int factorial (int n){    if(n==1){      return 1;    }    return n * factorial(n-1);}

「注意啦」，不是所有递推函数的等价关系都像阶乘这么简略，一下子就能推导出来。须要我们多接触，多积聚，多思考，多练习递归标题滴~

leetcode案例剖析

来剖析一道leetcode递归的经典标题吧~

❝

原题链接在这里哈：https://leetcode-百思特网cn.com/problems/invert-binary-tree/

❞

「标题：」 翻转一棵二叉树。

输入：

     4   /     2     7 /    / 1   3 6   9

输出：

     4   /     7     2 /    / 9   6 3   1

我们依照以上递归解题的三板斧来：

「1. 定义函数功效」

函数功效（即这个递归原问题是），给出一颗树，然后翻转它，所以，函数可以定义为：

//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {}/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */

「2.寻找递归终止条件」

这棵树什么时候不用翻转呢？当然是当前节点为null或者当前节点为叶子节点的时候啦。因此，加上终止条件就是：

//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {    if(root==null || (root.left ==null && root.right ==null)){       return root;    }}

「3. 递推函数的等价关系式」

原问题之你要翻转一颗树，是不是可以拆分为子问题，分离翻转它的左子树和右子树？子问题之翻转它的左子树，是不是又可以拆分为，翻转它左子树的左子树以及它左子树的右子树？然后一直翻转到叶子节点为止。嗯，看图懂得一下咯~

首先，你要翻转根节点为4的树，就须要「翻转它的左子树（根节点为2）和右子树(根节点为7）」。这就是递归的「递」的进程啦

然后呢，根节点为2的树，不是叶子节点，你须要持续「翻转它的左子树（根节点为1）和右子树（根节点为3）」。因为节点1和3都是「叶子节点」了，所以就返回啦。这也是递归的「递」的进程~

同理，根节点为7的树，也不是叶子节点，你须要翻转「它的左子树（根节点为6）和右子树（根节点为9）」。因为节点6和9都是叶子节点了，所以也返回啦。

左子树（根节点为2）和右子树(根节点为7）都被翻转完后，这几个步骤就「归来」，即递归的归进程，翻转树的义务就完成了~

显然，「递推关系式」就是：

invertTree（root）= invertTree（root.left） + invertTree（root.right）;

于是，很容易可以得出以下代码：

//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {    if(root==null || (root.left ==null && root.right ==null){       return root;    }    //翻转左子树    TreeNode left = invertTree(root.left);    //翻转右子树    TreeNode right= invertTree(root.right);}

这里代码有个处所须要注意，翻转完一棵树的左右子树，还要交流它左右子树的引用地位。

 root.left = right; root.right = left;

因此，leetcode这个递归经典标题的「终极解决代码」如下：

class Solution {    public TreeNode invertTree(TreeNode root) {         if(root==null || (root.left ==null && root.right ==null)){           return root;         }         //翻转左子树         TreeNode left = invertTree(root.left);         //翻转右子树         TreeNode right= invertTree(root.right);百思特网         //左右子树交流地位~         root.left = right;         root.right = left;         return root;    }}

拿终极解决代码去leetcode提交一下，通过啦~

递归存在的问题

栈溢出问题

「代码例子如下：」

/** * 递归栈溢出测试 */public class RecursionTest {    public static void main(String[] args) {        sum(50000);    }    private static int sum(int n) {        if (n <= 1) {            return 1;        }        return sum(n - 1) + n;    }}

「运行成果:」

Exception in thread "main" java.lang.StackOverflowError at recursion.RecursionTest.sum(RecursionTest.java:13)

怎么解决这个栈溢出问题？首先须要「优化一下你的递归」，真的须要递归调用这么多次嘛？如果真的须要，先稍微「调大JVM的栈空间内存」，如果还是不行，那就须要弃用递归，「优化为其他计划」咯~

反复盘算，导致程序效力低下

我们再来看一道经典的青蛙跳阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

绝大多数读者朋友，很容易就想到以下递归代码去解决：

class Solution {    public int numWays(int n) {    if (n == 0){       return 1;     }    if(n <= 2){        return n;    }    return numWays(n-1) + numWays(n-2);    }}

但是呢，去leetcode提交一下，就有问题啦，超越时光限制了

为什么超时了呢？递归耗时在哪里呢？先画出「递归树」看看：

我们先来看看这个递归的时光庞杂度吧，「递归时光庞杂度 = 解决一个子问题时光*子问题个数」

因此，青蛙跳阶，递归解法的时光庞杂度 = O(1) * O(2^n) = O(2^n)，就是指数级别的，爆炸增加的，「如果n比拟大的话，超时很正常的了」。

回过火来，你细心视察这颗递归树，你会发明存在「大批反复盘算」，比如f（8）被盘算了两次，f（7）被反复盘算了3次...所以这个递归算法低效的原因，就是存在大批的反复盘算！

「那么，怎么解决这个问题呢？」

既然存在大批反复盘算，那么我们可以先把盘算好的答案存下来，即造一个备忘录，等到下次须要的话，先去「备忘录」查一下，如果有，就直接取就好了，备忘录没有才再盘算，那就可以省去重新反复盘算的耗时啦！这就是「带备忘录的解法」

我们来看一下「带备忘录的递归解法」吧~

一般应用一个数组或者一个哈希map充任这个「备忘录」。

假设f(10)求解加上「备忘录」，我们再来画一下递归树：

「第一步」，f（10）= f(9) + f(8)，f(9) 和f（8）都须要盘算出来，然后再加到备忘录中，如下：

「第二步，」 f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因为 f(8) 已经在备忘录中啦，所以可以省掉，f(7),f（6）都须要盘算出来，加到备忘录中~

「第三步，」 f(8) = f（7）+ f(6),发明f(8)，f(7),f（6）全体都在备忘录上了，所以都可以剪掉。

所以呢，用了备忘录递归算法，递归树变成光秃秃的树干咯，如下：

带「备忘录」的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以「带「备忘录」的递归算法的时光庞杂度是O(n)」。接下来呢，我们用带「备忘录」的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题咯~，代码如下：

public&n百思特网bsp;class Solution {    //应用哈希map，充任备忘录的作用    Map<Integer, Integer> tempMap = new HashMap();    public int numWays(int n) {        // n = 0 也算1种        if (n == 0) {            return 1;        }        if (n <= 2) {            return n;        }        //先断定有没盘算过，即看看备忘录有没有        if (tempMap.containsKey(n)) {            //备忘录有，即盘算过，直接返回            return tempMap.get(n);        } else {            // 备忘录没有，即没有盘算过，履行递归盘算,并且把成果保留到备忘录map中，对1000000007取余（这个是leetcode标题规定的）            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);            return tempMap.get(n);        }    }}

去leetcode提交一下，如图，稳了：