1. 相关知识

2. 基本思路

在基于栈的运行时环境中，每次函数调用都在栈顶产生新的桢，并且将控制权交给被调用函数，当被调用函数返回时，相对应的桢从栈顶弹出，将控制权重新交给调用方，调用方从函数调用的下一条语句处继续执行。桢中保存的信息，主要分为两类：

本文将说明如何通过模拟桢和栈消除递归。

需要说明的是消除递归不一定非要使用栈，因为递归只是算法设计的一种方式。比如对于斐波那契数列而言，可以使用递推的方式实现：

package main

import "fmt"

func Fibo(n int) int {
	var result int
	first := 1
	second := 2
	if n <= 2 {
		return n
	}
	for i := 3; i <= n; i++ {
		result = first + second
		first = second
		second = result
	}
	return result
}

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

但是使用栈，一定可以消递归。

2. 代码实现

下面以快速排序为例进行说明：

package main

import (
	"cmp"
	"fmt"
)

// 分区处理
func partition[T cmp.Ordered](arr []T, start, end int) int {
	i, j, pivot := start, end, 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
}

// QuickSort 是快速排序的递归实现
func QuickSort[T cmp.Ordered](arr []T) {
	quickSort(arr, 0, len(arr)-1)
}

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)
}

// 快速排序的消递归实现

type frame[T cmp.Ordered] struct {
	// 实参
	arr   []T
	start int
	end   int
	// 局部变量
	m int
	// 前一个桢的桢指针
	pre *frame[T]
	// 返回地址（函数调用的下一条指令的地址）
	addr int
	// 返回结果
	result any
}

func (f *frame[T]) execute(addr int, _ any) *frame[T] {
	switch addr {
	case 0:
		if f.start >= f.end {
			return nil
		}
		f.m = partition(f.arr, f.start, f.end)
		// 返回新的桢
		return NewFrame(f.arr, f.start, f.m-1, f, 1)
	case 1:
		// 返回新的桢
		return NewFrame(f.arr, f.m+1, f.end, f, 2)
	case 2:
		// 设置执行结果，并且返回 nil，表明调用结束
		f.result = nil
		return nil
	default:
		panic("invalid addr")
	}
}

func NewFrame[T cmp.Ordered](arr []T, start, end int, pre *frame[T], addr int) *frame[T] {
	return &frame[T]{
		arr:   arr,
		start: start,
		end:   end,
		pre:   pre,
		addr:  addr,
	}
}

// QuickSortStack 是快速排序的消递归实现
func QuickSortStack[T cmp.Ordered](arr []T) {
	var stack []*frame[T]
	var addr = 0
	var result any = nil
	var activeFrame *frame[T]
	var nextFrame *frame[T]

	// 将第一个桢压栈
	stack = append(stack, NewFrame(arr, 0, len(arr)-1, nil, addr))

	// 循环处理
	for len(stack) > 0 {
		activeFrame = stack[len(stack)-1]
		nextFrame = activeFrame.execute(addr, result)
		if nextFrame == nil {
			addr = activeFrame.addr
			result = activeFrame.result
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, nextFrame)
			addr = 0
			result = nil
		}
	}
}

func main() {
	arr := []int{11, -1, 22, 1, 3, -4, 22, 999}
	QuickSortStack(arr)
	fmt.Println(arr)
}

QuickSortStack 是递归函数 QuickSort 的消递归实现。它的执行流程主要是：

  1. 第一个桢对象入栈，同时使用局部变量 addr 保存桢对象的返回地址，result 保存桢对象的返回值，初始时，addr 为 0，也就说，所有桢第一次都从位置 0 开始执行
  2. 获取栈顶的桢对象，并且使用 addr 和 result 调用该桢对象的 execute 方法
  3. 重复过程 2，直到栈空，result 的值就是递归调用的返回值

3. FAQ

1，当函数间接的调用自身时，比如 f 调用 g，g 又调用 f，此时：