国内视频网站域名,知乎网站建设入门书,wordpress android 源码,泉州网站建设网站制作文章目录1 难题2 递归2.1 n的阶层2.2 斐波那契数列的第n项2.3 逆序打印数组3 反转链表4 回顾递归1 难题 如果不想听我谈学习的过程而注重怎么学习#xff0c;可以直接跳到第二小节 这个递归的问题是在我刷题的时候遇到的。事实上#xff0c;我对递归是一窍不通的#xff0c;…
文章目录1 难题2 递归2.1 n的阶层2.2 斐波那契数列的第n项2.3 逆序打印数组3 反转链表4 回顾递归1 难题 如果不想听我谈学习的过程而注重怎么学习可以直接跳到第二小节 这个递归的问题是在我刷题的时候遇到的。事实上我对递归是一窍不通的第一次学递归是在大二上学期学的数据分析和可视化中遇到了但是那时候老师叫我们背所以没怎么注意这个问题。
没注意的问题在后面就开始暴露出来了。在Leetcode刷题的时候第一次遇见递归是在反转单链表的时候。反转单链表一文可以在每日一题——剑指 Offer24反转链表_尘鱼好美的小屋-CSDN博客中查看。在当时我用的仅仅是新手都能接受的迭代法。而无法接受思维混乱的递归但是在解决Leetcode上的另外一道题的时候就开始出问题了这道题必须用到递归或者栈。
我们学过栈的都知道栈的本质是递归这就意味着这个知识点是一个跨不过的坎我知道我必须面对了。
对于解决这个问题我首先是看了一下大佬的递归解法剑指 Offer 24. 反转链表迭代 / 递归清晰图解 - 反转链表 - 力扣LeetCode (leetcode-cn.com)。但是我发现其对于递归的本质没有详细的阐述反而是只提解法这对于新手显然十分不友好。我又在看不懂递归的看过来希望能帮到你 - 反转链表 - 力扣LeetCode (leetcode-cn.com)上面看到了另外一个大佬的解法虽然讲的挺好但是在单链表反转中又是让人无法接受了但是至此我突然脑路一开发现了一种新思路我十分愿意和你分享我思考的思路希望你耐心看完我的文章。
2 递归
大多数讲述递归都是先引出斐波那契数列。实际上我们无需畏惧递归这个名词我们先用另外一个词来体会递归即递推公式这在我们高中数学中几乎人人学过。在讲述斐波那契数列前我们来解决一个问题。如何解决用递归实现n的阶层计算
2.1 n的阶层
完成递归实际上就是三部曲
明确函数目的寻找递归结束条件找出函数的等价关系式
这么说好像太空了我们来给出一个图实际上这个图就是递归。 没错我们可以把俄罗斯套娃看成是递归也就是说每一层的娃都是在解决问题递归的过程是把解决的问题都留在最后先从外到里一步一步取娃然后在最里面的娃从里到外解决问题。
现在我们看往例子如果我们要解决阶层问题那么结束递归的条件就是一个你知道的数比如你从5的阶层那么自然1的阶层是你知道的那你就可以把1作为结束条件。当然2你也知道是多少甚至于更高。我们先用1来作为结束条件
//结束条件
if(n 1)
{return 1;
}那我们接下来就是要写函数等价式了这实际上是一个创造套娃的过程从最小的娃开始和相邻的娃建立联系。也就是说我们只关注第n个娃和n-1个娃之间的关系在这个例子中它们的关系就是f(n) n*f(n-1)。
等价关系式的寻找在这里看起来十分简单可实际上递归最难的就是此步。
接下来我们把上述写成代码如下所示
int func(int n)
{if(n 1)return 1;return n*func(n-1);
}也可以用2为结束递归条件如下所示
int func(int n)
{if(n 2)return 2; //2的阶层return n*func(n-1);
}综上所述这就是一个最简单的递归了。在下面我们层层递进来解决一些实际的问题。
2.2 斐波那契数列的第n项
我们来解决这么一个问题 斐波那契数列的是这样一个数列1、1、2、3、5、8、13、21、34…即第一项 f(1) 1,第二项 f(2) 1…,第 n 项目为 f(n) f(n-1) f(n-2)。求第 n 项的值是多少。 按照上面的套路函数实际上是要返回一个第n项的值所以我们可以这么定义
int func(int n)
{}接下来我们要寻找递归结束的条件根据题意我们知道f(1) 1,f(2) 1… 那么根据我们在最开始讲到的我们实际上是寻求函数关系等价式在本题中如果你采用n 1作为递归结束条件那么在函数等价式中本题已给出有一个f(n) f(n-1)f(n-2)你把2填进去会出现一个f(0)这样的话越过了f(0)越过了递归结束条件n 1会无限死循环下去。
这显然是我们不希望的所以我们可以用n2来作为循环结束条件这样f(n)中的n只能填3以上的数字才会出现循环。
综上所述代码如下所示
int func(int n){if(n 2){return 1;}return func(n-1) func(n-2)
}2.3 逆序打印数组
上面的斐波那契数列问题实际上很容易看出函数等价关系式让我们来一个不那么明显地例子。 我们需要逆序打印一个长度为n的数组。请问如何解决 也就是说我们要的是打印一个数组我们可以这么做
int func(int arrs[])
{}接下来我们需要寻找递归结束条件这个结束的条件就是数组为空即n 0就结束。
int func(int arrs[])
{if(n 0)return false;
}现在让我们来找函数等价关系在这里我们明显要倒序打印所以首要任务是先打印再倒推倒推的过程实际上是一个类似于指针移动的过程n n-1所以我们可以写出如下代码
void func(int arrs[], int n)
{if (n 0)return;cout arrs[n - 1] endl;return func(arrs, n - 1);
}3 反转链表
回到我们的主题我们要解决的最终问题是如何解决反转链表乃至解决更多问题既然要使用递归这个工具乘风破浪那就先拿这道破题开刀吧。 定义一个函数输入一个链表的头节点反转该链表并输出反转后链表的头节点。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 限制 0 节点个数 5000 来源力扣LeetCode 链接https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 采用递归首先要明白函数要干嘛函数要反转链表并且返回头结点。
//逆置链表函数
ListNode* reverseList(ListNode * head)
{}但是实际上我们要实现递归的地方不是在这个逆置函数内所以我们可以另外写一个递归函数。我们的思路是分别指定两根指针一根为pre一根为cur反转链表后cur.next pre。最开始pre一定是空cur一定是处于head的位置。
//逆置链表函数
ListNode* reverseList(ListNode * head)
{}//递归函数
ListNode* recur(ListNode* cur, ListNode* pre)
{}接下来找结束条件。最开始pre是空cur处于head的位置。当递归执行时最内层的循环是cur快跑到null了。所以结束递归的条件一定是cur-next NULL。
在最内层循环中我们做的是改变指针指向即cur.next pre。并且在最内层循环是cur所处位置恰好是逆置后链表头结点所处位置。当递归函数执行完成返回逆置链表头结点位置。而在逆置链表函数中仅仅需要调用递归函数并且返回逆置链表头结点位置即可。
class Solution {
public:ListNode* reverseList(ListNode* head) {return recur(head, nullptr); // 调用递归并返回}
private:ListNode* recur(ListNode* cur, ListNode* pre) {if (cur nullptr) return pre; // 终止条件ListNode* res recur(cur-next, cur); // 递归后继节点cur-next pre; // 修改节点引用指向return res; // 返回反转链表的头节点}
};从套娃的角度来看我们可以这样做 4 回顾递归
递归实际上是一个解决子问题的过程。我们要解决f(n)实际上首先解决f(n-1)要解决f(n-1)实际上要先解决f(n-2)以此类推直至先解决最根本的问题再回溯整个过程。
递归实际上也是需要优化的比如f(n) f(n-1)f(n-2)如果n 5,那么n-1 4,n-2 3后续在递归的过程中会出现多次f(4)、f(3)等如果每次都计算开销挺大一般可以用某个值来保存但是这篇文章是针对像我一样的初学者的我们就偷个懒放自己一马吧。
好了彦祖别太累了好好消化一下就休息吧。
