递归思想以及常见的算法题

一、理解递归

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归（Recursion）是一种非常广泛的算法，与其说递归是一种算法不如说递归是一种编程技巧。

1.1 递归的特点

1）可拆解成可重复的子问题（重复子问题）

如果一个问题的解能够拆分成多个子问题的解，拆分之后，子问题和该问题在求解上除了数据规模不一样之外，求解的思路和该问题的求解思路完全相同，也就是说能够找到一种规律，那么这个问题就可以用递归解决。这种最近重复子问题的求解思路会形成一种规律，如果将这个规律用数学公式表达出来就是我们所谓的递推公式。

2） 归要有出口（终止条件）

把一个问题的解分解为多个子问题的解，把子问题再分解为子子问题，一层一层分解下去，不能存在无限递归。这就需要终止条件。

所以写递归代码的关键就是找到如何将一个问题拆分成多个小问题的规律，并且基于此写出递推公式，然后再找到递归终止条件，最后将递推公式和终止条件翻译成代码即可。

1.2 递归与迭代思维

• 迭代法：主要是从“已知”—>“未知” 推进的正向思维；
• 递归法：主要是从 “未知”—>“已知” 推进的逆向思维；

1.3 递归思想总结

递归函数一般要做什么事情可以抽象出一个模板：

以计算n!（n的阶乘）为例：

public void recur(int level, int param) { // 场景不同，参数不同
  // 先编写终止条件（没有终止条件的递归就是无限递归，类似死循环）
  if(level > MAX_LEVEL){
    // 处理结果数据
    return;
  }
  // 处理当前层逻辑（有时需要先处理当前层逻辑再递归到下一导，
  // 有时候需要递归到下一层根据返回结果处理当前层，所以需要灵活运用）
  process(level, params);

  // 进入到下一层（即开始递归）
  recur(level + 1, param);
 
  // 当前层资源清理，比如全局的参数等
}

二、常见递归算法

2.1 翻转链表

使用递归函数，一直到递归到链表的最后一个结点，该结点就是反转后的头结点，记作ret
此后，每次函数在返回的过程中，让当前结点的下一个结点的next指针指向当前节点

func reverse2(pHead *ListNode1) *ListNode1 {
	// 1. 递归结束条件：只有一个节点（或者头结点为空，直接不进行递归直接返回）
	if pHead == nil || pHead.Next == nil {
		return pHead
	}

	// 2. 递归调用
	newHead := reverse2(pHead.Next)

	// 3.递推到当前层

	// 让head的下一个节点反过来指向head
	pHead.Next.Next = pHead
	// 将head的next置空
	pHead.Next = nil

	return newHead
}

整个递归实现反转的过程如下：
1） 由于 head 不为 NULL，因此函数每执行 newHead := reverse2(pHead.Next)时，递归都会深入一层，并依次将指向节点 2、3、4 的指针作为实参（head_next 的指向）参与递归。而根据递归出口的判断条件，当函数参数 head 指向的是节点 4 时满足 head->next == NULL，递归过程不再深入，并返回指向节点 4 的指针，这就是反转链表的新头指针。

相关材料