递归是计算机科学中的一项强大技术，其中函数调用自身来解决问题。它通过将复杂问题分解为更小、更易于管理的同类子问题来简化它们。以下是您需要了解的有关递归的所有信息：
1. 基本概念
递归有两个基本组成部分：
func factorial (n int) int {
if n == 0 {
return 1 // base case
}
return n * factorial(n-1) // recursive case
}
- 间接递归：一个函数调用另一个函数，最终返回到原来的函数。
func a() {
// do something
b()
}
func b() {
// do something
a()
}
3。它是如何工作的（调用堆栈）
递归依赖于调用堆栈。每次调用递归函数时，都会将一个新帧添加到堆栈中。当满足基本情况时，堆栈展开，并从基本情况返回链计算结果。
4. 递归的优点
func factorial(n int) int {
if n == 0 {
return 1
}
return n * factorial(n-1)
}
b。斐波那契数列
另一个经典的递归示例，其中每个斐波那契数都是前两个数的总和。
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2)
}
c.树遍历
基于树的算法，例如前序、中序和后序遍历，使用递归来遍历树的节点。
func inorder(node *treenode) {
if node == nil {
return
}
inorder(node.left)
fmt.println(node.val)
inorder(node.right)
}
d.回溯
像 n 皇后或迷宫中的老鼠这样的问题需要探索所有可能的配置，这自然适合递归。
func solvenqueens(board [][]int, col int) bool {
if col >= len(board) {
return true
}
for i := 0; i < len(board); i++ {
if issafe(board, i, col) {
board[i][col] = 1
if solvenqueens(board, col+1) {
return true
}
board[i][col] = 0 // backtrack
}
}
return false
}
e。分而治之
合并排序和快速排序等算法使用递归将问题划分为更小的子问题并单独解决它们。
func mergesort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergesort(arr[:mid])
right := mergesort(arr[mid:])
return merge(left, right)
}
8.记忆
递归可能会导致冗余计算，尤其是在像斐波那契这样的问题中。记忆化存储之前计算的结果以避免重新计算。
var memo = map[int]int{}
func fibonacci(n int) int {
if n <= 1 {
return n
}
if val, ok := memo[n]; ok {
return val
}
memo[n] = fibonacci(n-1) + fibonacci(n-2)
return memo[n]
}
9.动态规划
动态编程（dp）是递归的扩展，其中重叠的子问题可以使用记忆或制表来有效解决。 dp 问题通常依赖于递归关系。
10.尾递归
某些语言优化尾递归以避免增加调用堆栈。尾递归函数将其递归调用作为函数中的最后一个操作执行。然而，go 不执行尾调用优化。
func tailFactorial(n, acc int) int {
if n == 0 {
return acc
}
return tailFactorial(n-1, acc*n) // Tail recursion
}
11. 用递归解决的常见问题
- 排列和组合： 生成一组的所有排列或组合。
