← 返回算法分类

递归与回溯

什么是递归？

递归是一种通过函数自身调用来解决问题的方法。递归算法将问题分解为更小的子问题，直到达到基本情况。

核心要素

基本情况 + 递归式

空间复杂度

O(n) - 栈空间

回溯

探索+撤销

递归三要素

  1. 明确递归函数定义：清楚函数要做什么
  2. 找出递归关系：问题如何分解为子问题
  3. 确定递归终止条件：何时停止递归

阶乘计算

递归的经典例子：n! = n × (n-1)!

function factorial(n) {
    // 基本情况
    if (n <= 1) return 1;
    
    // 递归关系
    return n * factorial(n - 1);
}

// 测试
console.log(factorial(5)); // 120
console.log(factorial(0)); // 1
                            
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# 测试
print(factorial(5))  # 120
print(factorial(0))  # 1
                            
package main

import "fmt"

func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5)) // 120
    fmt.Println(factorial(0)) // 1
}

汉诺塔问题

经典的递归问题：将n个盘子从A柱移动到C柱，可以借助B柱，每次只能移动一个盘子。

function hanoi(n, source, auxiliary, target) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${target}`);
        return;
    }
    
    // 将n-1个盘子从源柱移到辅助柱
    hanoi(n - 1, source, target, auxiliary);
    
    // 将第n个盘子从源柱移到目标柱
    console.log(`Move disk ${n} from ${source} to ${target}`);
    
    // 将n-1个盘子从辅助柱移到目标柱
    hanoi(n - 1, auxiliary, source, target);
}

// 测试
console.log('3层汉诺塔解法：');
hanoi(3, 'A', 'B', 'C');
                            
def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    
    hanoi(n - 1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, source, target)

# 测试
print('3层汉诺塔解法：')
hanoi(3, 'A', 'B', 'C')
                            
package main

import "fmt"

func hanoi(n int, source, auxiliary, target string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", source, target)
        return
    }
    
    hanoi(n-1, source, target, auxiliary)
    fmt.Printf("Move disk %d from %s to %s\n", n, source, target)
    hanoi(n-1, auxiliary, source, target)
}

func main() {
    fmt.Println("3层汉诺塔解法：")
    hanoi(3, "A", "B", "C")
}

回溯算法

回溯是一种通过试错来解决问题的算法范式。它系统地搜索问题的解空间，当发现当前选择不可行时，就回溯到上一步。

N皇后问题

在n×n棋盘上放置n个皇后，使得任何两个皇后都不在同一行、同一列或同一对角线上。

function solveNQueens(n) {
    const solutions = [];
    const board = Array(n).fill(null).map(() => Array(n).fill('.'));
    
    function isValid(row, col) {
        // 检查列
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // 检查左上对角线
        for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // 检查右上对角线
        for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row) {
        if (row === n) {
            solutions.push(board.map(row => row.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    }
    
    backtrack(0);
    return solutions;
}

// 测试
const result = solveNQueens(4);
console.log(`4皇后有 ${result.length} 种解法`);
console.log(result[0]);
                            
def solve_n_queens(n):
    solutions = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_valid(row, col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        
        return True
    
    def backtrack(row):
        if row == n:
            solutions.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return solutions

# 测试
result = solve_n_queens(4)
print(f"4皇后有 {len(result)} 种解法")
print(result[0])
                            
package main

import (
    "fmt"
    "strings"
)

func solveNQueens(n int) [][]string {
    var solutions [][]string
    board := make([][]string, n)
    for i := 0; i < n; i++ {
        board[i] = make([]string, n)
        for j := 0; j < n; j++ {
            board[i][j] = "."
        }
    }
    
    isValid := func(row, col int) bool {
        for i := 0; i < row; i++ {
            if board[i][col] == "Q" {
                return false
            }
        }
        
        for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
            if board[i][j] == "Q" {
                return false
            }
        }
        
        for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
            if board[i][j] == "Q" {
                return false
            }
        }
        
        return true
    }
    
    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            solution := make([]string, n)
            for i := 0; i < n; i++ {
                solution[i] = strings.Join(board[i], "")
            }
            solutions = append(solutions, solution)
            return
        }
        
        for col := 0; col < n; col++ {
            if isValid(row, col) {
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
            }
        }
    }
    
    backtrack(0)
    return solutions
}

func main() {
    result := solveNQueens(4)
    fmt.Printf("4皇后有 %d 种解法\n", len(result))
    fmt.Println(result[0])
}

全排列

生成数组的所有可能排列。

function permute(nums) {
    const result = [];
    
    function backtrack(path, used) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            
            path.push(nums[i]);
            used[i] = true;
            
            backtrack(path, used);
            
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack([], Array(nums.length).fill(false));
    return result;
}

// 测试
console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
                            
def permute(nums):
    result = []
    
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            
            path.append(nums[i])
            used[i] = True
            
            backtrack(path, used)
            
            path.pop()
            used[i] = False
    
    backtrack([], [False] * len(nums))
    return result

# 测试
print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
                            
package main

import "fmt"

func permute(nums []int) [][]int {
    var result [][]int
    n := len(nums)
    used := make([]bool, n)
    
    var backtrack func(path []int)
    backtrack = func(path []int) {
        if len(path) == n {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }
        
        for i := 0; i < n; i++ {
            if used[i] {
                continue
            }
            
            path = append(path, nums[i])
            used[i] = true
            
            backtrack(path)
            
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    
    backtrack([]int{})
    return result
}

func main() {
    result := permute([]int{1, 2, 3})
    fmt.Println(result)
    // [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
}

子集生成

生成集合的所有子集。

function subsets(nums) {
    const result = [];
    
    function backtrack(index, current) {
        result.push([...current]);
        
        for (let i = index; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    
    backtrack(0, []);
    return result;
}

// 测试
console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
                            
def subsets(nums):
    result = []
    
    def backtrack(index, current):
        result.append(current[:])
        
        for i in range(index, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

# 测试
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
                            
package main

import "fmt"

func subsets(nums []int) [][]int {
    var result [][]int
    
    var backtrack func(index int, current []int)
    backtrack = func(index int, current []int) {
        temp := make([]int, len(current))
        copy(temp, current)
        result = append(result, temp)
        
        for i := index; i < len(nums); i++ {
            current = append(current, nums[i])
            backtrack(i+1, current)
            current = current[:len(current)-1]
        }
    }
    
    backtrack(0, []int{})
    return result
}

func main() {
    result := subsets([]int{1, 2, 3})
    fmt.Println(result)
    // [[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
}

学习建议

  • 理解递归的调用栈机制
  • 掌握回溯的模板：选择 → 递归 → 撤销
  • 学会画递归树理解执行过程
  • 注意递归深度过大可能导致栈溢出