老渔哥网站建设公司,曼联对利物浦新闻,怎么给自己做个网站吗,江苏省建设厅网站怎么登不上这是一个新的专栏#xff0c;主要是一些算法的基础#xff0c;对想要刷leedcode的同学会有一定的帮助#xff0c;如果在算法学习中遇到了问题#xff0c;也可以直接评论或者私信博主#xff0c;一定倾囊相助 进入正题#xff0c;今天咱们要说的是递归#xff0c;递归是是… 这是一个新的专栏主要是一些算法的基础对想要刷leedcode的同学会有一定的帮助如果在算法学习中遇到了问题也可以直接评论或者私信博主一定倾囊相助 进入正题今天咱们要说的是递归递归是是很多初学者比较头疼的问题啊在这篇博客里我会先阐述一下递归的定义然后再举几个例子来证明一下最后咱们练个小题强化一下。 递归算法 递归算法简介递归算法解题思路例题例题1 练习 递归算法简介
首先说一下递归的含义递归的含义就是递归算法recursion algorithm在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。这是百度百科的定义 按照我们平时对递归的用法那就是把一个大的问题一直分解直到分解成一种简单的情况为止这种简单的情况就是我们能直接得到结果的情况。下面先举一个例子我们以阶乘为例我们平时算阶乘是怎么算呢 1的阶乘就是1 2的阶乘就是 2*1 3的阶乘就是 3 * 2 *1 其实这里就是一个简单的递归 我们求3的阶乘的时候要知道2的阶乘用 3×2的阶乘那么这里2的阶乘是哪里来的呢 是用2×1的阶乘 1的阶乘是哪里来的是规定 1的阶乘就是1.所以我们才能算出来3的阶乘。那么在计算机的语言里我们一般是用函数调用自己的方式来实现递归举个例子
int func(int n)
{if (n 1)return 1;else return n * func(n-1);
}这个就是使用C语言写一个简单的递归来解决阶乘问题的方法我们简单分析一下这个函数为什么能算阶乘 当n等于1的时候 就返回1如果n 2呢就调用else中的return 返回 n*func(n-1)即为 2×func’(1)也就是1的阶乘 1的阶乘用函数算出来就是1 这里就是2×1 其实这样还不够直观因为递归的过程分为递推和回归两个过程这里画个图让大家好理解一下
递归算法解题思路
现在我们可以总结一下了递归在计算机语言中解决问题的步骤是什么 递推过程指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题直到达到结束条件时停止此时返回最底层子问题的解。 回归过程指的是从最底层子问题的解开始逆向逐一回归最终达到递推开始时的原问题返回原问题的解。 遇到问题时 我们只需要想好其中一个递推的过程和一个回归过程即可不用全都想透这样容易乱掉其实这也是一个重复的过程套路都是一样的
例题
下面我们练一个递归算法的经典小题
例题1
斐波那契数列 先说一下斐波那契数列是啥 他是 第0项为0 第1项为1规定从第三项开始 每一项都是前两项的和 这么一个数列 比如f(2) f(0)f(1) 这时候我们就想一下他的递推过程是啥回归过程是啥递归过程就是比如我们要求 f (6) 的值 f那么就要知道 f(4)和f(5)的值f (4) 又要知道f (3) 和f2的值一次类推 知道递推到 f(0)和f(1)的值 我们就可以return了这里建议大家画图不清晰一定画个图。 那么代码如何写呢 可以看到这里时间耗时比较长哈这是因为在求斐波那契数列的时候有重复就像我们求f(6),要求f(5)和f(4) f5要求f(4)和f(3)这里两个f(4)就重复了这时我们可以使用记忆化的方式去简化具体就是算完一个f 就存在数组里一个值下次遇到已经存进去的值就可以直接调用了这里不提供代码大家可以回去查阅一下。
练习
二叉树最大深度 这里没有学过二叉树的可以去看我的另一篇博客可以简单了解一下二叉树简单介绍 这里简单给个思路 就是二叉树有左子树和右子树 其中更深的就是我们要的答案 代码如下做完再看嗷
class Solution {
public:int maxDepth(TreeNode* root) {if(root nullptr)return 0;int hleft 0;int hright 0;hleft maxDepth(root-left);hright maxDepth(root-right);return hleft hright? hleft1: hright1;}
};有啥问题都可以提出来 博主有啥问题也恳请斧正谢谢。
