3.5 Recursion

1. What Is Recursion

• A function calls itself

2. The Recursion Call Process

• Take a sum function as an example

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

• Test

import (
	"fmt"
	"testing"
)

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

• Process analysis

3. Basic Idea of Recursion

1. Break down the problem
   1. Break a large problem into smaller problems
   2. Break smaller problems into even smaller problems
   3. When the problem is small enough, the answer can be obtained directly
2. Solve
   1. Use the solution of the smallest problem to obtain the solution of a larger problem
   2. Use the solution of the larger problem to obtain the solution of an even larger problem
   3. Finally obtain the solution to the original problem

4. Recursion Template

1. Function purpose
   1. Do not first think about how to write the code; think about what the function does and what function it completes
2. Clarify the relationship between the original problem and the subproblem
   1. The relationship between f(n) and f(n-1)
3. Clarify the recursion base case
   1. The solution of f(1)

5. Examples

5.1. Tower of Hanoi

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
	}
	// Move n - 1 disks from p1 to p2 with the help of p3
	hanoi(n-1, p1, p3, p2)
	// Move disk n from p1 to p3
	move(n, p1, p3)
	// Move n - 1 disks from p2 to p3 with the help of p1
	hanoi(n-1, p2, p1, p3)
}

func move(n int, from string, to string) {
	fmt.Println(fmt.Sprintf("disk %v: %v->%v", n, from, to))
}

5.2. Fibonacci

• Fibonacci Sequence

5.3. Climbing Stairs

• Climbing Stairs

5.4. Variant of Climbing Stairs

• Variant Climbing Stairs

6. Converting Recursion to Non-Recursion

• Method 1: maintain a stack to save parameters and local variables

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

}

• Method 2: loop

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

	return sum
}

7. Tail Recursion

7.1. What It Is

• Tail call: the last action of a function is to call a function
• Tail recursion: the last action of a function is to call itself

7.1.1. Example

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

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

7.2. Tail Call Optimization

• The compiler can optimize tail calls to save stack space
  • Reuse test1’s stack frame for test2, then jump to test2’s function code
  • 

8. Why Only Tail Calls Can Be Optimized

func test3() {
	a := 10
	b := 20
	test4(b)
	// Normally this should print 30
	// With tail-call optimization here, a would be overwritten by x and b by y, so the result would be 70, which is incorrect
	fmt.Println(a + b)
}

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

9. References

• Recursion: Call Flow, Fibonacci, Stairs, Hanoi, and Tail Calls - CSDN