3.5 递归

1. 递归是什么

• 函数自己调用自己

2. 递归的调用过程

• 以求和函数为例

package recursion

func Sum(data ...int) int {
	return sum(data, 0, len(data)-1)
}

func sum(data []int, left int, right int) int {
	if left == right {
		return data[left]
	}

	return data[left] + sum(data, left+1, right)
}

• 测试

import (
	"fmt"
	"testing"
)

func TestSum(t *testing.T) {
	fmt.Println(Sum(1, 2, 3, 4))
}

• 过程分析

3. 递归基本思想

1. 拆解问题
   1. 把规模大的问题拆成规模较小的问题
   2. 规模较小的问题拆成规模更小的问题
   3. 规模小到一定程度可以直接得出答案
2. 求解
   1. 由最小规模问题的解得出较大规模问题的解
   2. 由较大规模问题的解得出规模更大问题的解
   3. 最后求解出原问题的解

4. 递归模板

1. 函数的功能
   1. 不用考虑代码怎么写，而是这个函数是干嘛的完成什么功能
2. 明确原问题和子问题的关系
   1. f(n)和f(n-1)的关系
3. 明确递归基
   1. f(1)的解

5. 举例

5.1. 汉诺塔

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

func hanoi(n int, p1 string, p2 string, p3 string) {
	if n <= 1 {
		move(n, p1, p3)
		return
	}
	//  将 n – 1 个盘子借助 p3 从 p1 移动到 p2
	hanoi(n-1, p1, p3, p2)
	// 将编号为 n 的盘子从 p1 移动到 p3
	move(n, p1, p3)
	// 将 n – 1 个盘子借助 p1 从 p2 移动到 p3
	hanoi(n-1, p2, p1, p3)
}

func move(n int, from string, to string) {
	fmt.Println(fmt.Sprintf("%v号盘子从%v->%v", n, from, to))
}

5.2. 斐波那契

• 斐波那契数列.md（原链接已失效）

5.3. 跳台阶

• 跳台阶.md（原链接已失效）

5.4. 变态跳台阶

• 变态跳台阶.md（原链接已失效）

6. 递归转非递归

• 方法一：维护一个栈保存参数和局部变量

type Frame struct {
	data  []int
	left  int
	right int
}

func NewFrame(data []int, left int, right int) *Frame {
	return &Frame{data: data, left: left, right: right}
}

func Sum2(data ...int) int {
	stack := make([]*Frame, 0)
	for i := 0; i < len(data); i++ {
		stack = append(stack, NewFrame(data, i, len(data)-1))
	}

	sum := 0
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		sum += top.data[top.left]
	}

	return sum

}

• 方法二：循环

func Sum3(data ...int) int {
	sum := 0
	for _, datum := range data {
		sum += datum
	}

	return sum
}

7. 尾递归

7.1. 是什么

• 尾调用：一个函数最后一个动作是调用函数
• 尾递归：一个函数最后一个动作是调用自己

7.1.1. 例子

func test1() {
	a := 10
	b := a + 20
	test2(b)
}

func test2(n int) {
	if n < 0 {
		return
	}
	test2(n - 1)
}

7.2. 尾调用优化

2026 注：Go 编译器并不保证通用的尾调用优化；这里保留当时对 TCO 原理的理解。

• 编译器会对尾调用进行优化，节省栈空间
  • test1的栈帧复用给test2，然后jump到test2的函数代码
  • 

8. 为什么只有尾调用才能优化

func test3() {
	a := 10
	b := 20
	test4(b)
	//正常来说这里会输出30
	//如果尾调用优化，那么a被x覆盖，b被y覆盖，此时结果是70，就不正确了
	fmt.Println(a + b)
}

func test4(n int) {
	x := 30
	y := 40
	fmt.Println(x + y) //70
}

9. 参考

• 【恋上数据结构】递归（函数调用过程、斐波那契数列、上楼梯、汉诺塔、递归转非递归、尾调用）_Jerry House-CSDN博客