1. 递归

递归就是一个函数直接或间接地调用自身。一般来说,递归需要有边界条件递归前进段递归返回段。当边界条件不满足时,递归前进;边界条件满足时,递归返回。使用递归时,需要注意以下两点:

下面是使用线性递归实现斐波那契数列的例子(Golang 版):

package main

import "fmt"

func Fibo(n int) int {
	if n < 2 {
		return 1
	}
	return Fibo(n-1) + Fibo(n-2)
}

func main() {
	// 1 1 2 3 5 8 13
	fmt.Println(Fibo(6))
}

2. 辅助递归算法设计的工具

为帮助思考和表述递归算法的思路,使算法更直观和清晰,我们定义两个节点:或节点与节点

或节点

or-node.png

A 为或节点,A 依不同的条件有两种不同的取值,B 或 C。或节点用空心圆表示。

如果多于两种取值,可用如下图表示:

2-or-node.png

与节点

and-node.png

A 为与节点,A 的最终取值是 C 节点的值,但为求得 C 的值,需要先求得 B 节点的值,C 是 B 的函数。

与节点可能有多个相关联的点,这时可描述为下图:

2-and-node.png

A 的最终取值是 D 节点的值,但是为求得 D 的值,需要先求 B 节点和 C 节点的值。从图上看,需要先求左边的节点的值,才能求最右边的节点的值。我们约定最右边的 D 节点的值就是 A 节点的值。


3. 什么样的程序是递归程序

试编写函数 fact(n),求解 n!。
n! = n * (n-1)!

Golang 线性递归实现:

package main

import "fmt"

func Fact(n int) int {
	if n == 1 {
		return 1
	}
	return n * Fact(n-1)
}

func main() {
	// 1 * 2 * 3 * 4 * 5 * 6 = 720
	fmt.Println(Fact(6))
}

下面是 fact(3) 的调用和返回的递归示意图:

fact-3.png

n=3 为例,与或节点图如下:

n-equals-3-example.png

fact(n) 的与或图如下:

fact-n-and-or.png

A 为或节点,B 为直接可解节点,值为 1。C 为与节点,当 n > 1 时,A 的值即为 C 的值,而 C 的值即为 E 的值,为求得 E 的值,需要先求出 D 的值,E 是 D 的函数:E = D * n,也就是 E 的值等于 D 的值 fact(n-1) 乘以 n。

递归算法的出发点不在初始条件(递归边界)上,而是在求解目标上,也就是从所求的未知项出发,逐次调用本身,直至递归边界(初始条件)的求解过程。

递归算法比较符合人的思维方式,逻辑性强,可将问题描述的简单扼要,可读性强,易于理解。许多看起来相当复杂、难以下手的问题,如果能够使用递归算法,就会变得易于处理。


4. 递归算法举例 - 快速排序

快速排序的基本思想:

通过一趟排序将待排序数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

函数 sort 接受两个参数(z 和 y),分别表示数组中一个片段的起始与终止下标值。

quicksort.png

A 是或节点,当 z >= y 时,A 的值是 B 节点的值,B 是直接可解节点(递归边界);当z < y时,A 的值是 C 节点的值,C 节点是与节点,C 节点的值就是 F 节点的值,要想求得 F,需要先求 D、E 的值,F 是 D、E 的函数:分区处理; sort(z, m-1); sort(m+1, y)。

需要特别注意的是分区处理过程。下面是快速排序算法的 Golang 实现:

package main

import (
	"cmp"
	"fmt"
)

func partition[T cmp.Ordered](arr []T, start, end int) int {
	i, j := start, end
	pivot := arr[start]
	for i < j {
		for ; j > i; j-- {
			if arr[j] < pivot {
				arr[i] = arr[j]
				i++
				break
			}
		}
		for ; i < j; i++ {
			if arr[i] > pivot {
				arr[j] = arr[i]
				j--
				break
			}
		}
	}

	arr[i] = pivot
	return i
}

func quickSort[T cmp.Ordered](arr []T, start, end int) {
	if start >= end {
		return
	}
	m := partition(arr, start, end)
	quickSort(arr, start, m-1)
	quickSort(arr, m+1, end)
}

func QuickSort[T cmp.Ordered](arr []T) {
	quickSort(arr, 0, len(arr)-1)
}

func main() {
	arr := []int{0, 111, 2, 1, 1, 5, -1, 6, 4}
	QuickSort(arr)
	fmt.Println(arr)
}

5. 递归算法举例 - 汉诺塔问题

hanoi.png

汉诺塔问题的与或图:

hanoi-and-or.png

其中 move(n, A, B, C) 的含义是将 n 个盘子从 A 借助 B 搬到 C。

下面是汉诺塔问题的 Golang 实现:

package main

import "fmt"

func Hanoi(n int, A, B, C string) {
	if n <= 0 {
		return
	}
	Hanoi(n-1, A, C, B)
	fmt.Println(fmt.Sprintf("move #%d from %s to %s.", n, A, C))
	Hanoi(n-1, B, A, C)
}

func main() {
	Hanoi(4, "A", "B", "C")
}

6. 尾递归

6.1. 尾递归

当递归调用是整个函数体中最后执行的语句,并且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。

6.2. 尾递归优化

当编译器检测到函数调用是尾递归时,它覆盖当前的活动记录而不是在栈中创建新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行语句,所以当这个调用返回时帧中没有其他事情可做,因此也就没有保存帧的必要。通过覆盖当前帧而不是在其之上重新添加的方式,这样所使用的栈空间就大大缩减,使得实际的运行效率变得更高。

例子:

Golang 尾递归实现求解 n!:

package main

import "fmt"

func FactTail(n, result int) int {
	if n == 1 {
		if result == 0 {
			return 1
		}
		return result
	}
	return FactTail(n-1, result*n)
}

func main() {
	fmt.Println(FactTail(6, 1))
}

6.3. 尾递归的优势

尾递归极其重要,不用尾递归,函数的栈耗用难以估量,需要保存很多中间函数的栈。比如尾递归 f(n, sum) = f(n-1, sum+value(n)) 只保留后一个函数栈即可,之前的可优化删去。

6.4. 理解尾递归

尾递归从最后开始计算,每递归一次就算出相应的结果,也就是说,函数调用出现在调用者的尾部,因为是尾部,所以根本没有必要保存任何局部变量。直接让被调用的函数在返回时越过调用者,返回到调用者的调用者。

尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题 —— 因为参数里带有前面若干步的运算路径。对于阶乘而言,越深不意味着越复杂。

尾递归适用于运算对当前递归路径有依赖的问题,传统递归适用于运算对更深层递归有依赖的问题。


7. 参考文档