CloudObsidian

深入理解 Recursion，及其衍生算法

7 min read

【小小福讲算法】硅谷工程师十五分钟带你深入理解 Recursion （递归）算法，及其衍生出的算法（分治算法Divide and Conquer, 回溯 Backtracking）

LeetCode

标签

编程 算法 递归 LeetCode 技术 核心 油管链接🔗： https://www.youtube.com/watch?v=AqGagBmFXgw&t=70s

  • Recursion

  • 为什么 Function 需要 Call 自己？

  • 因为大问题（Big problem）可以分解成小问题（Sub problems）

  • 小问题通常很容易解答！

  • e.g. 跑步 10 km 很难，但是跑步 10 km = 跑步 9 km + 先跑 1 km，所以后一步不是个艰难的任务…

  • 递归函数的结构模版

  • 终止条件（#Base_Case） + 递归关系（#Recursion_Relation）

    def foo( arguments ):
Base Case
 
Recursion Relation

  • Recursion 在计算机中的实现方式

  • 任何一个函数调用，计算机会在内存中生成一块区域，用于存放函数的参数，返回地址等，这块区域叫做“栈（Stack）“

  • 递归函数也是一种函数调用 ⇒ 因而也会生成一系列的 stack

     
step-1:
跑步函数（3km）
call 跑步函数（2km）
call 跑步函数（1km）
call 跑步函数（0km）
 
step-2:
跑步函数（0km）back & release
跑步函数（1km）back & release
跑步函数（2km）back & release
跑步函数（3km）

  • 例题讲解

    例题 LeetCode 700. Search in a Binary Search Tree

    # Definition for a binary tree node.
 
# class TreeNode:
 
# def __init__(self, val=0, left=None, right=None):
 
# self.val = val
 
# self.left = left
 
# self.right = right
 
class Solution:
 
def searchBST(self, root: Optional[TreeNode], val: int) -\> Optional[TreeNode]:
# base case
if not root: return None
if root.val == val: return root
 
# recursion relation
if val \> root.val:
return self.searchBST(root.right, val)
else:
return self.searchBST(root.left, val)
 
    /**
 
* Definition for a binary tree node.
 
* public class TreeNode {
 
* public var val: Int
 
* public var left: TreeNode?
 
* public var right: TreeNode?
 
* public init() { self.val = 0; self.left = nil; self.right = nil; }
 
* public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 
* public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 
* self.val = val
 
* self.left = left
 
* self.right = right
 
* }
 
* }
 
*/
 
class Solution {
 
func searchBST(_ root: TreeNode?, _ val: Int) -\> TreeNode? {
 
// Base code
 
guard let root = root, root.val != val else {
return root
}
 
 
// recursion relation
 
if root.val \> val {
return self.searchBST(root.left, val)
 
} else {
 
return self.searchBST(root.right, val)
 
}
 
}
 
}

  • 递归的三种形式

  • Memorization 缓存

    • 将计算结果保存，避免重复计算

  • Divide and conquer 分治

    • 将一个大问题分解成小问题，各个击破，然后将小问题的解组合起来

  • Backtracking 回溯

    • 不断试错，知错就改
    • 类似于暴力搜索，但是比暴力搜索高效（因为知错就改）

  • 递归问题的形式（一）

  • 如果递归问题会产生重复的子问题，那么可以使用 cache 记住子问题的答案，避免重复计算。

    # Initialize cache (which is essentially a dictionary)
cache: Dict[arg, value] = dict() # 初始化 cache
 
def foo(arg):
# check answer if already exists
if arg in cache:
return cache[arg] # 直接返回 cache 答案，如果答案存在
 
# Base
 
# Recursion Relation
 
# Save the answer
cache[arg] = result # 将计算的答案写入 cache

  • 例题 Memorization

    heading:: 2 LeetCode 509: Fibonacci-number !#Pasted_image_20231024113314.png

    class Solution {
 
var cache = [Int: Int]()
 
func fib(_ n: Int) -\> Int {
 
if let c = cache[n] {
 
return c
}
var result = 0
 
if n \< 2 {
result = n
} else {
result = fib(n - 1) + fib(n - 2)
}
 
cache[n] = result
 
return result
}
}

  • 递归问题的形式（二）Divide and Conquer 分治

    heading:: 2 Divide and Conquer 分而治之，几乎等同于标准的 Recursion，唯一的区别是，最后需要将子问题的结果进行合并！

    > 1. Divide. Divide the Problem S into a set of subproblems: {S1, S2,…Sn} where n >= 2, i.e. there are usually more than one subproblem > > 2. Conquer. Solve each subproblem recursively > > 3. Combine. Combine the results of each subproblem.

  • 例题 Divide and Conquer

    heading:: 2 LeetCode 98: Validate Binary Search Tree

    class Solution:
def isValidBST(self, root: TreeNode) -\> bool:
def validate(node, low=-match.inf, high=math.inf):
# Empty trees are valid BSTs
if not node:
return True
# The current node's value must be between low and high.
if node.val \<= low or node.val \>= high:
return False
# The left and right subtree must also be valid.
return (validate(node.right), node.val, high) and validate(node.left, low, node.val))
return validate(root)

  • 递归问题的形式（二）Divide and Conquer 的代码模板

    heading:: 2

    def divide_and_conquer( S ):
# (1). Divide the problem into a set of subproblems.
[S1, S2, ... Sn] = divide(S)
 
# (2). Solve the subproblem recursively,
# obtain the results of subproblems as [R1, R2, ... Rn].
rets = [divide_and_conquer(Si) for Si in [S1, S2, ... Sn]]
[R1, R2, ... Rn] = rets
 
# (3). combine the results from the subproblems.
# and return the combine result.
return combine([R1, R2, ... Rn])

  • 递归问题的形式（三）Backtracking 回溯

    heading:: 2 回溯的问题的形式：通常要求寻找满足所有xxx条件的结果，并且问题可以使用递归实现。

    个人理解：一步一步先前探索，每一步尝试所有的可能，一旦发现当前不是可行解，立即停止（知错就改）

  • 例题 LeetCode 22: 找出所有由 n 个左右括号组成的有效的表达式

    heading:: 2

    class Solution {
 
func generateParenthesis(_ n: Int) -\> [String] {
 
var res: [String] = []
 
func backtrack(left: Int, right: Int, s: String) {
 
 
 
// find solution:
 
// left == right && left == n * 2
 
if s.count == n * 2 {
 
res.append(s)
 
return
 
}
// try and given or back
 
if left \< n {
 
backtrack(left: left + 1, right: right, s: s + "(")
 
}
 
 
 
if left \> right {
 
backtrack(left: left, right: right + 1, s: s + ")")
 
}
}
 
backtrack(left: 0, right: 0, s: "")
 
return res
}
}

  • Backtracking 问题的模板

    heading:: 2

    def backtrack(candidate):
if find_solution(candidate):
ouput(candidate)
return
 
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)

  • 写在最后

    heading:: 2

  • 递归是一种非常 intuitive 的解决复杂问题的方法

  • 递归分两步：Base Case + Recursion Relation

  • 递归遇到重复计算的情况 ⇒ 使用 memorization

  • 递归遇到子问题结果组合的情况 ⇒ 使用 divide-and- conquer

  • 递归要求返回所有满足条件的解答 ⇒ 使用 backtracking

Graph View

Backlinks