DSA：递归

来源：dev.to 2024-12-08 16:24:39 0浏览收藏

大家好，我们又见面了啊~本文《DSA：递归》的内容中将会涉及到等等。如果你正在学习Golang相关知识，欢迎关注我，以后会给大家带来更多Golang相关文章，希望我们能一起进步！下面就开始本文的正式内容~

DSA：递归

递归是计算机科学中的一项强大技术，其中函数调用自身来解决问题。它通过将复杂问题分解为更小、更易于管理的同类子问题来简化它们。以下是您需要了解的有关递归的所有信息：

1. 基本概念
递归有两个基本组成部分：

基本情况：递归终止的条件。如果没有基本情况，递归将无限继续。
递归情况：函数中使用修改后的参数调用自身的部分，使问题更接近基本情况。 2. 递归类型 - 直接递归： 函数直接调用自身。

    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. 递归的优点

简化了可以分解为类似子问题的问题的代码。
优雅且易于编写，特别是对于涉及树、图和链表等结构的问题。
许多算法（dfs、分而治之）本质上是递归的。 5. 递归的缺点
堆栈溢出：深度递归会耗尽堆栈内存，导致崩溃。 - 性能：由于函数调用和堆栈管理的开销，与迭代解决方案相比，递归解决方案可能会更慢。 - 尾递归：在某些语言（非 go）中，可以优化尾递归以防止堆栈溢出，但 go 没有尾递归优化。 6. 递归与迭代 对于树遍历或回溯等问题，递归通常更直观，而对于循环或线性计算等问题，迭代在内存使用方面可以更有效。 7. 递归的常见用例 a.阶乘 递归的经典示例，通过将问题减 1 来计算数字的阶乘。

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. 用递归解决的常见问题
- 排列和组合： 生成一组的所有排列或组合。

河内塔：在具有特定约束的杆之间移动圆盘。
子集和问题：查找集合中总和达到给定总和的所有子集。
数独求解器：解决需要回溯的谜题。
图遍历：深度优先搜索（dfs）本质上是递归的。 12.可视化递归 将递归可视化为递归树可以帮助理解问题是如何分解和重新组合的。每个递归调用都是树中的一个节点，基本情况充当叶节点。 13.递归深度控制 在某些情况下，您可能希望控制递归深度，以避免性能问题或通过限制递归深度来有效处理非常大的输入。 14. 最佳实践
始终定义一个基本情况以避免无限递归。
当子问题重叠时使用记忆进行优化。
注意深度递归造成的性能和空间限制。