递归之我见

host
host
host
33
文章
0
评论
2022年7月15日16:54:26递归之我见已关闭评论127

0.前序

递归问题是一个非常经典的问题,大家应该都看过盗梦空间,就像两面镜子对着照一样,你永远看不多结局在哪里,但我们解决实际问题的时候,千万不要让自己的大脑也是试图去一层层的解析每一层的问题,这样就会掉入递归的陷阱,问题难以得到解决,今天我以一种简单的方式试图去解释清楚递归问题的解法。

1.先放结论

Rules Number One,基本上,所有的递归问题都可以用递推公式来表示。有了这个递推公式,我们就可以很轻松地将它改为递归代码。。所以,遇到递归不要怕,先想递推公式。

例1: (比较明显的能递推公式的问题)
问题:斐波那契数列的第n项
递推公式:

f(n)=f(n-1)+f(n-2) 其中,f(0)=0,f(1)=1

终止条件:

if (n <= 2) return 1;

递归代码:

int f(int n) {
if (n <= 2) return 1;
return f(n-1) + f(n-2);
}

 

例2:(不那么明显的有递推公式的问题)
问题:逆序打印一个数组
递推公式:

假设令F(n)=逆序遍历长度为n的数组
那么F(n)= 打印数组中下标为n的元素 + F(n-1)
终止条件:

if (n < 0) return ;

递归代码:

public void Print(int[] nums,int n){
if(n<0) return;
System.out.println(nums[n]);
Print(nums,n-1);
}

到这里,不知道大家对写递归有没有一些理解了。其实写递归不能总想着去把递归平铺展开,这样脑子里就会循环,一层一层往下调,然后再一层一层返回,试图想搞清楚计算机每一步都是怎么执行的,这样就很容易被绕进去。对于递归代码,这种试图想清楚整个递和归过程的做法,实际上是进入了一个思维误区。只要找到递推公式,我们就能很轻松地写出递归代码。

到这里,我想进一步跟大家说明我这个思路是比较能够容易出代码的,那么就树的遍历问题来和大家讲。递归总是和树分不开,其中,最典型的便是树的遍历问题。刚开始学的时候,不知道大家是怎么理解先/中/后序遍历的递归写法的,这里我提供我的思路供参考,以前序遍历为例:

问题:二叉树的先序遍历
递推公式:

令F(Root)为问题:遍历以Root为根节点的二叉树,
令F(Root.left)为问题:遍历以F(Root.left)为根节点的二叉树
令F(Root.right)为问题:遍历以F(Root.right)为根节点的二叉树

那么其递推公式为:

F(Root)=遍历Root节点+F(Root.left)+F(Root.right)

递归代码:

public void preOrder(TreeNode node){
if(node==null) return;
System.out.println(node.val);
preOrder(node.left);
preOrder(node.righr);
}

Rules Number Two, 递归是一种关于某个重复动作(完成重复性的功能)的形式化描述。具体点讲,如果一个问题 A 可以分解为若干子问题 B、C、D,你可以假设子问题 B、C、D 已经解决,在此基础上思考如何解决问题 A。而且,你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可,不需要一层一层往下思考子问题与子子问题,子子问题与子子子问题之间的关系(也就是说,递归只能考虑当前层和下一层的关系,不能继续往下深入)。我们需要屏蔽掉递归细节,理解为完成了某种功能的形式化描述即可。

2.好了,那我们来分析这个题。

  • 问题:单向链表的反转
  • 递推公式:

令F(node)为问题:反转以node为头节点的单向链表;
一般,我们需要考虑F(n)和F(n-1)的关系,那么这里,如果n代表以node为头节点的单向链表,那么n-1就代表以node.next为头节点的单向链表.
所以,我们令F(node.next)为问题:反转以node.next为头节点的单向链表;
那么,F(node)和F(node.next)之间的关系是?这里我们来简单画个图,假设我们反转3个节点的链表:
1 -> 2 -> 3
那么,F(node=1)=F(node=2)+?
这里假设子问题F(node=2)已经解决,那么我们如何解决F(node=1):
很明显,我们需要反转node=2和node=1, 即 node.next.next=node; 同时 node.next=null;
所以,这个问题就可以是:F(node=1)=F(node=2)+ 反转node=2和node=1
递归代码:

public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) { //终止条件并不难想
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node; //按上面的例子,F(node=1)和F(node=2)它俩反转后的头节点是同一个
}

3.写递归的小tips

(发现写递归的过程中有些小体会,虽然时隔很久但还是过来更新啦!)

将问题抽象化,可以将问题抽象为f(n)(或者其他的数学符号), 然后用f(n)代表欲求的问题,然后去发现和子问题(比如f(n-1))的递推关系!(这一点在写动态规划的时候特别有用,其实动态规划就是记忆化的递归!)
递归函数是带语义的,但是记住一个递归函数只有一个语义,如果在写递归函数实现的时候,发现出现了多个语义,需要对新出现的语义重新定义一个函数!
这里推荐问题572. 另一棵树的子树和问题100. 相同的树

在写递归函数的时候,可以先写子问题f(n-1),再写所求问题f(n),这样的话就很好知道f(n)和f(n-1)的关系,更容易保证一个递归函数只包含一个语义。

host
  • 本文由 发表于 2022年7月15日16:54:26
  • 转载请务必保留本文链接:https://www.zenook.cn/algorithm/leetcode/recursion.html
剑指Offer-栈和队列 Leetcode

剑指Offer-栈和队列

剑指 Offer 09.用两个栈实现队列 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功...
剑指Offer-搜索与回溯算法Ⅰ Leetcode

剑指Offer-搜索与回溯算法Ⅰ

剑指 Offer 26. 树的子结构 输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A:...