宏观视角看递归
码个蛋
共 3718字,需浏览 8分钟
·
2021-03-17 23:57
通过数组求和看递归的基本性质
链表的天然递归性
01
通过数组求和看递归的基本性质
![](https://filescdn.proginn.com/7236f58bb4d5036331dde4056ad1afc2/aeeed058a21e3848f3f07c124d88e153.webp)
![](https://filescdn.proginn.com/5cc333a04c295b4c58ce6c6160b56a7f/bf34f4e8742c8e1c02fb1c15148ab63a.webp)
![](https://filescdn.proginn.com/fcff4fbbc619a4db63cecd379751e1c3/781e1a9ca9dcff31a5335fe6cf2301c7.webp)
![](https://filescdn.proginn.com/7ef849432e150ac2795b071577706bec/6bb74b63cfcc284b9ab1b9c424dd11bd.webp)
![](https://filescdn.proginn.com/7aeaa1b3ce0f0e12faf7818dc821029d/3f692e0e32b708eac5ed999ecb35a04c.webp)
![](https://filescdn.proginn.com/2d7f151fc9594d288120182595d3f62a/4922b245bbd5747308813c2b990a2777.webp)
![](https://filescdn.proginn.com/272864f9e9614672366571b2b3322373/ab14e873994ac3e0b7c8d3e75859b954.webp)
![](https://filescdn.proginn.com/6f6b1ae0c44f383f32d2d11e9b7fa3bc/5af9c2a92d8c67d07abdb4bc87e33a22.webp)
![](https://filescdn.proginn.com/a2b003e7b8974679ace9a3b8bde0ec76/10777c4a53c4686ff58ee2e3e383da26.webp)
// begin 表示从数组中哪个索引位置开始
// 当begin == arr.length表示数组中没有剩余元素
if (begin == arr.length) {
return 0;
}
二是要知道递归递推公式,就数组求和这个问题来说,递推公式是:
arr[begin] + sum(begin + 1, arr);
有了终止条件和递推公式,就可以写出递归求解数组中所有元素和的代码了,实现如下:
public int sum (int[] arr) {
// 调用递归函数,初始从0开始
return sum(0, arr);
}
// 递归函数
private int sum(int begin, int[] arr) {
// begin 表示从数组中哪个索引位置开始
// 当begin == arr.length表示数组中没有剩余元素
if (begin == arr.length) {
return 0;
}
// 我只计算我拿到的数组中第一个元素的值
// 和数组中剩余元素总和的和
return arr[begin] + sum(begin + 1, arr); // 递归调用
}
这里我们在第7行sum(int begin, int[] arr)这个方法中调用了sum(int begin, int[] arr)方法它自己,即16行的sum(begin + 1, arr),这一点可能会让你觉得困惑。
我们可以这样理解,方法sum(int begin, int[] arr)是计算数组中从索引begin开始所有元素的总和,而该方法的计算规则是我计算的是当前数组起始位置begin所对应的元素值和数组中剩余元素的总和的和。那么,我就需要有个方法可以告诉我数组中剩余元素的总和是多少。
这时,刚好有个方法fun(int begin, int[] arr),只要我告诉它数组是什么样的,以及从哪个索引位置开始计算,它就会告诉我数组中剩余元素的总和。只不过这个方法fun(int begin, int[] arr)所需的参数和我自己一样而已。于是,在代码中看起来就是方法sum(int begin, int[] arr)调用了它自己。
02
链表的天然递归性
接着我们看下如何用递归思想解答LeetCode中#203.移除链表元素这个问题。
题目描述:
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
LeetCode
![](https://filescdn.proginn.com/b18f0d6972bde97b703ff1be78e02c8a/665b50c489f60b246d3593c9809dd804.webp)
![](https://filescdn.proginn.com/693afdf054ade92b31fe7a980b08fc12/283c22adc457bcca44ceef6a235041b8.webp)
![](https://filescdn.proginn.com/18adc9f28f5d4bba2a0e2f3e6bcb38d5/3e6da3f4468758b553cc297a07d6426b.webp)
![](https://filescdn.proginn.com/eeefc5ef31098bea75351606ed075fd2/0b536cb9f07e05ddffadfba2cc60918c.webp)
![](https://filescdn.proginn.com/c6c947b560ae413b7ee4186e4ac7d3db/cde62f79c979dd8c54bf9badfd970ccf.webp)
![](https://filescdn.proginn.com/14285799265621d2ac43fe3b932b215b/655afa50295598104d00fb82a64640e5.webp)
![](https://filescdn.proginn.com/7a017dfc72094affec1e25a0d6febafc/552f747e7d888ce3ed656efe75009a4a.webp)
![](https://filescdn.proginn.com/e5e1151f38e0e67a7f62a1048b281556/7720c38935e19025eb603604dd36ebdc.webp)
![](https://filescdn.proginn.com/d60fd8a03cd2c661c24208502166c86d/d039d3b7cd9c84f3d8df6a79d96d7301.webp)
![](https://filescdn.proginn.com/d060f90a8e93c3e41c9a092a70bc3f0b/d16a6957478b4ed79c33af9ccf27349f.webp)
public ListNode removeElements(ListNode head, int val) {
// 递归终止条件
if (head == null) {
return null;
}
// 调用方法removeElements将当前结点之后的链表部分中的
// 和val值相等的结点删除
ListNode result = removeElements(head.next, val);
// 如果当前结点head的值等于val则返回result
if (head.val == val) {
return result;
} else {
// 如果当前结点head的值不等于val则
// 将result挂在当前结点head之后返回
head.next = result;
return head;
}
}
题图:stux / Pixabay
评论