第一个问题,什么时候对数据进行操作?
我们递归的过程中是一定要对数据结构进行处理的,包括两个时间段,递归时处理数据,和回溯时处理数据。它们的区别就是一个写在递归函数调用处上面,一个写在调用处下面,此时需要注意,如果直接return 递归函数,也是属于递归时处理数据。
第二个问题,我们的递归函数中到底需要return什么?
这里大致分为四个大类:
一是回溯时return的数据被用到了,而且是每一次递归函数时都会被用到,这时就要考虑好递归的逻辑以及最终递归终结条件的返回值。
二是回溯时return的数据是递归函数本身,这个情况比较特殊,他有一个很明显的特点,就是回溯到最后时,return的数据还仍然是终止条件return的那个值,所以在什么情况下我们可以使用这种情况?就是我们最终需要返回的数据是我们递归到最深处时返回的数据;
例如,我们反转链表,边递归边进行翻转,翻到最后,我们需要返回的就是最后一个节点,此时就用我们上述的方式,将最后一个节点返回即可。
注(而且这种情况,也属于是递归过程中处理数据;)
三是回溯时return的数据是递归函数与递归函数相互计算的结果,这个也是在递归时进行数据操作,然后我们返回数据时,按照题目要求进行计算即可。技巧就是,我们此处写递归函数时,可以关注前面两次递归,然后你会发现,后面的递归都自然而然的好了。
例如,我们判断一个树是否是对称树,就需要左子树和右子树同时是对称树,那么我们return的就是左右两个子树的判断结果,最终返回它们向与的结果。
四是我们的递归函数不需要return数据,它起到的作用仅仅就是边递归边对数据进行操作或者回溯时对数据进行操作。例如二叉树的中序遍历,前序遍历,后序遍历等等
第三个问题,决定好终止条件的判断以及我们应该返回什么?
要注意,终止条件这里的重点并不仅仅是判断是否终止的语句,我们return的东西也很重要,这里我们就需要先考虑这个递归函数最开始要return 的是什么数据,然后在递归过程中是否需要使用这个递归结果等等,然后对症下药。文章来源:https://www.toymoban.com/news/detail-469868.html
总结:当然这一切的前提是先要理解好题目,想好解题方法,然后问问自己的思路怎么回答这三个问题,最后总体再理一遍思路,相信就八九不离十了~文章来源地址https://www.toymoban.com/news/detail-469868.html
到了这里,关于写递归题目的思路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!