递归是什么？如何优化？递归的理解总结

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第13天，点击查看活动详情

递归

在算法刷题中，往往会使用到递归方法解题，虽然递归将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，可以简化代码，但在阅读上往往不好理解。

递归的要点：

1. 找到原问题的子问题，推导出解决问题的递推式。
2. 找到递归的出口，即终止（边界）条件。

递归的写法： 按照递归的要点，把原问题拆解成子问题，推导出递推式。再描述出终止条件，释放递归的出口。

来看几个例子，加深理解。

斐波那契数列（有明显的递推式）

0、1、1、2、3、5、8、13、21、34、……

递推式：

f(n)=f(n-1)+f(n-2)		n>=2
f(n)=n				0<=n<2

终止条件很明显，就是n=0,n=1的时候

if (n==0) return 0;
if (n<2) return 1;

递归代码就可以写成这样

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

递归优化（记忆化搜索）

对于同一个子问题，递归会对此再次进行计算。优化思路：将子问题的计算结果保存，同一子问题可直接调取使用。

int[] nums;
int solution(int n) {
	nums = new int[n+1];
	return dp(n);
}

int dp(int n) {
	if (n==0) return 0;
	if (n<2) return 1;
	if (nums[n]!=0) return nums[n];
	nums[n] = dp(n-1) + dp(n-2);
	return nums[n];
}

逆序打印一个数组（隐晦的递推式）

递推式：

假设F(n)为数组下标为n的元素 递推式：F(n) = 打印F(n) + F(n-1)

终止条件：

if (n<0) return;

递归代码就可以这样写：

void solution(int[] nums) {
	print(nums, nums.length);
}

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

单向链表的反转

递推式：

令 reverse(n1,n2) 表示翻转链表中n1节点和n2节点，即n1->n2变成n2->n1

F(n)表示以n节点为头的链表，F(n-1)表示以n.next节点为头的链表

递推式：F(n1) = F(n2) + reverse(n1,n2)

举例来理解：

n1 -> n2 -> n3 -> null

F(n1) = F(n2) + reverse(n1,n2)

这里假设F(n2)已经处理好了，处理F(n1)就是将n1与n2翻转。

具体到链表表示为：n1.next.next = n1, n1.next = null 即n2.next = n1, n1.next = null

终止条件：

当前节点为null，或当前节点的下一节点为null时，退出递归。

if (node == null || node.next == null) return node;

递归代码：

ListNode reverseList(ListNode node) {
	if (node == null || node.next == null) return node;
	ListNode newNode = reverseList(node.next);
	node.next.next = node;
	node.next = null;
	return newNode;
}