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. 获取栈顶的桢对象,并且使用 addrresult 调用该桢对象的 execute 方法
  3. 重复过程 2,直到栈空,result 的值就是递归调用的返回值

3. FAQ

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