首页 > 编程语言 >算法中递归的执行过程

算法中递归的执行过程

时间:2024-03-14 23:00:43浏览次数:25  
标签:递归 sum 备忘录 算法 执行 root 节点 翻转

原文链接:https://blog.csdn.net/weixin_38754799/article/details/120681819

我们来看一下 函数sum(n=5)的递归执行过程,如下: 

计算sum(5)时,先sum(5)入栈,然后原问题sum(5)拆分为子问题sum(4),再入栈,直到终止条件sum(n=1)=1,就开始出栈。

sum(1)出栈后,sum(2)开始出栈,接着sum(3)。

最后呢,sum(1)就是后进先出,sum(5)是先进后出,因此递归过程可以理解为栈出入过程。

实例分析

我对递归的理解是先往下一层层传递,当碰到终止条件的时候会反弹,最终会反弹到调用处。下面我们就以5个最常见的示例来分析下

1,阶乘

我们先来看一个最简单的递归调用-阶乘,代码如下

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

  这个递归在熟悉不过了,第2-3行是终止条件,第4行是调用自己。我们就用n等于5的时候来画个图看一下递归究竟是怎么调用的:

这种递归还是很简单的,我们求f(5)的时候,只需要求出f(4)即可,如果求f(4)我们要求出f(3)……,一层一层的调用,当n=1的时候,我们直接返回1,然后再一层一层的返回,直到返回f(5)为止。

递归的目的是把一个大的问题细分为更小的子问题,我们只需要知道递归函数的功能即可,不要把递归一层一层的拆开来想,如果同时调用多次的话这样你很可能会陷入循环而出不来。比如上面的题中要求f(5),我们只需要计算f(4)即可,即f(5)=5*f(4);至于f(4)是怎么计算的,我们就不要管了。因为我们知道f(n)中的n可以代表任何正整数,我们只需要传入4就可以计算f(4)。

2、二叉树的遍历

再来看最后一个常见的示例就是二叉树的遍历,分为前序遍历、中序遍历、后序遍历,代码其实都差不多,这里只列出其中一个遍历。

前序遍历:

终止条件是node等于空,逻辑处理这块直接打印当前节点的值即可,递归调用是先打印左子树在打印右子树,我们来看下

public static void preOrder(TreeNode node) {
    if (node == null)
        return;
    System.out.printf(node.val + "");
    preOrder(node.left);
    preOrder(node.right);
}

  3、翻转一棵二叉树

 

[1.定义函数功能]

函数功能(即这个递归原问题是),给出一颗树,然后翻转它。

[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);

  于是,很容易可以得出以下代码:

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;
    }
}

  

递归存在的问题

递归调用层级太多,导致栈溢出问题

递归重复计算,导致效率低下

我们再来看一道经典的青蛙跳阶问题:

一只青蛙一次可以跳上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提交一下,就有问题啦,超出时间限制了

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

 

要计算原问题 f(10),就需要先计算出子问题 f(9) 和 f(8)

然后要计算 f(9),又要先算出子问题 f(8) 和 f(7),以此类推。

一直到 f(2) 和 f(1),递归树才终止。

我们先来看看这个递归的时间复杂度吧,递归时间复杂度 = 解决一个子问题时间*子问题个数

一个子问题时间 =  f(n-1)+f(n-2),也就是一个加法的操作,所以复杂度是 「O(1)」;

问题个数 = 递归树节点的总数,递归树的总结点 = 2^n-1,所以是复杂度「O(2^n)」。

因此,青蛙跳阶,递归解法的时间复杂度 = 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 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);
        }
    }
}

  

 

 

 

 

 

标签:递归,sum,备忘录,算法,执行,root,节点,翻转
From: https://www.cnblogs.com/Dongmy/p/18074232

相关文章

  • 回归预测 | Matlab实现GSWOA-KELM混合策略改进的鲸鱼优化算法优化核极限学习机的数据
    回归预测|Matlab实现GSWOA-KELM混合策略改进的鲸鱼优化算法优化核极限学习机的数据回归预测目录回归预测|Matlab实现GSWOA-KELM混合策略改进的鲸鱼优化算法优化核极限学习机的数据回归预测效果一览基本介绍程序设计参考资料效果一览基本介绍GSWOA-KELM多变......
  • web漏洞:RCE代码及命令执行
    概述:RCE漏洞可以让攻击者直接向后台服务器远程注入操作命令或代码,从而控制后台系统,分为远程系统命令执行和远程代码执行。远程系统命令执行:(危害:执行系统命令)一般出现这种漏洞是因为应用系统从设计上需要给用户提供指定的远程命令操作的接口(比如路由器,防火墙,入侵检测等设......
  • 归并排序、快速排序——左神数据结构与算法Day2学习笔记C++版本(持续更新)
    递归行为        利用递归求整个数组的最大值,代码如下。intfind_Max(inta[],intL,intR){if(L==R){returna[L];}intmid=L+((R-L)>>1);//mid是数组的中点intleftMax=find_Max(a,L,mid);intrightMax......
  • 【智能算法】白鲨算法(AVOA)原理及实现
    目录1.背景2.算法原理2.1算法思想2.2算法过程3.代码实现4.参考文献1.背景2022年,Braik等人受到白鲨捕食行为启发,提出了非洲秃鹫优化算法(WhiteSharkOptimizer,WSO)。2.算法原理2.1算法思想海洋中白鲨拥有敏锐的感知、听觉和嗅觉,WSO模拟了白鲨探索整个搜索......
  • 01-位运算、算法
    题目:打印int类型整数的32位信息1与任何二进制的与运算:同1为1,有0为0;可以让整数每一位和1做与运算,按位输出结果这是循环的操作,并且应该从最高位32位按位输出,也就是最开始1应该左移31位,接下来左移30位publicclassCode01_PrintBinary{ publicstaticvoidprintBinary(intn......
  • Linux下/etc/profile、~/.bash_profile等几个文件的执行过程
    介绍/etc/profile:此文件为系统的每个用户设置环境信息,当用户第一次登录时,该文件被执行.并从/etc/profile.d目录的配置文件中搜集shell的设置。/etc/bashrc:为每一个运行bashshell的用户执行此文件.当bashshell被打开时,该文件被读取(即每次新开一个终端,都会执行bashrc......
  • pycharm找不到conda可执行文件怎么解决
    问题:pycharm配置conda环境找不到conda可执行文件解决办法:总结问题:pycharm配置conda环境找不到conda可执行文件解决办法:1.找到  anaconda安装目录(D:\Users\wl\anaconda3)2.打开pycharm    找到anaconda3\condabin\conda.bat选择你要使用的虚拟环境......
  • 代码随想录算法训练营第四十六天| 139.单词拆分 多重背包 背包问题总结篇!
    单词拆分 题目链接:139.单词拆分-力扣(LeetCode)思路:竟然真能转化为背包问题。classSolution{public:boolwordBreak(strings,vector<string>&wordDict){unordered_set<string>t(wordDict.begin(),wordDict.end());vector<bool>dp(s.size()+......
  • 力扣大厂热门面试算法题 27-29
            27.移除元素,28.找出字符串中第一个匹配项的下标,29.两数相除,每题做详细思路梳理,配套Python&Java双语代码,2024.03.14 可通过leetcode所有测试用例。目录27.移除元素解题思路完整代码PythonJava28.找出字符串中第一个匹配项的下标解题思路暴力匹......
  • 力扣大厂热门面试算法题 24-26
            24.两两交换链表中的节点,25.K个一组翻转链表,26.删除有序数组中的重复项,每题做详细思路梳理,配套Python&Java双语代码,2024.03.14 可通过leetcode所有测试用例。目录24.两两交换链表中的节点解题思路递归思路迭代思路完整代码PythonJava25.K个......