设为首页收藏本站

爱吱声

 找回密码
 注册
搜索
查看: 2134|回复: 3
打印 上一主题 下一主题

[科技前沿] 突然想到让deepseek来解释一下递归

[复制链接]
  • TA的每日心情
    开心
    2025-9-8 05:08
  • 签到天数: 3 天

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    3 Y% s) `  W$ v/ b; {; O' x0 P" u
    解释的不错3 z# K# Q1 g. y
    - \$ J; w4 R. |; H3 u. Q7 Q
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    * K7 z: g. p& U4 x# y3 b4 ]: L/ F$ L( V0 \  ~1 n8 R) h! V
    关键要素* j2 D. L1 l- r# h0 _9 o
    1. **基线条件(Base Case)**; D7 Y# M; n3 U0 A: N/ Z5 D$ J
       - 递归终止的条件,防止无限循环
    # |5 C# w+ I0 X& _7 R7 N   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    / T- O! B8 J# M  C7 B- H( ?0 w4 ~7 U+ [# c8 `; H- w
    2. **递归条件(Recursive Case)**
    : P* x9 D. A1 v& r   - 将原问题分解为更小的子问题! T7 _( a& X8 M8 ?0 Z. h
       - 例如:n! = n × (n-1)!
    , x3 a- p5 j' }" [
    8 ^; M1 f8 i# b( ]- \ 经典示例:计算阶乘) h' Z/ @4 U5 }5 F0 l' L
    python' ?9 J" O+ l5 Z5 r
    def factorial(n):
    / f; a$ q  Y* _$ Z9 m4 J    if n == 0:        # 基线条件
    6 x* e$ S" M$ G% T" {  ]. ?        return 1, Z5 q, k! Y7 x2 @. V
        else:             # 递归条件
    0 \4 U) v* Q- w6 R, ]/ C        return n * factorial(n-1)- A/ R# L: E& \. Y* |
    执行过程(以计算 3! 为例):
    9 |' V7 `: x0 v7 l8 X8 Z* Gfactorial(3); J% d8 a7 s6 ?' z
    3 * factorial(2)
    ( D3 R2 H# r7 x7 _1 [; n3 * (2 * factorial(1))+ v* ~& j# \% u0 ^4 D
    3 * (2 * (1 * factorial(0)))
    1 x! f& I. J+ L5 K2 Y' F6 [$ v3 * (2 * (1 * 1)) = 6
    % Z( k) ^9 ~6 _- J  G6 B- C$ J  H
    7 D/ k+ a0 ~, t- ~0 N0 \* c9 Z 递归思维要点
    + i' ]) {7 k$ ^1 o' ?1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ) O; ^2 g# B  ]2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 Q$ M7 s9 N& x6 e' z( f+ E7 v, b
    3. **递推过程**:不断向下分解问题(递)
      R7 U9 S  ]- X/ }3 X4. **回溯过程**:组合子问题结果返回(归)+ z  M0 z* W# s" W

    - ?& F% x; n3 \) m6 Q 注意事项
    0 E, a0 v$ n6 y0 [; z# L. q必须要有终止条件& J' s7 S" O/ W. |  V3 Y# g" u$ }
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)4 Z9 z: u$ T: p1 v
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / S" a/ ]6 j& Y3 v2 j) m2 K( H; U9 v' C. l尾递归优化可以提升效率(但Python不支持)+ w: d" F' {7 E8 {! H9 Q7 j

    , U4 K" o2 N( Z 递归 vs 迭代
    / A1 U$ |1 r3 N/ r5 r$ a|          | 递归                          | 迭代               |9 n- N/ T% P( c) E' {
    |----------|-----------------------------|------------------|
    & [, l/ S# b% ~9 M+ w) o( k. p| 实现方式    | 函数自调用                        | 循环结构            |
    $ p: k) U- M5 \" s* {( r| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    % Y2 Y; A  ?' G! N2 k* Z  Y| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |+ X1 w; u  `" ?4 O, x
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |: x9 L0 T6 @; I( X! g4 [
    " L! z' e, @( W- _3 T
    经典递归应用场景! O: d6 f' [% C2 }1 n1 ^
    1. 文件系统遍历(目录树结构). F+ ^5 M0 V$ W  W! b1 o  W% m
    2. 快速排序/归并排序算法6 P7 v# }, ^: @1 |2 ?! E& o
    3. 汉诺塔问题
    " ^; |- C( a4 I4. 二叉树遍历(前序/中序/后序)
    - l: `! \# Z/ W1 j5. 生成所有可能的组合(回溯算法)% L: c( ^* D  l+ k( T8 _' m
    3 |9 z- B% U" e1 z' R6 j
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

    参与人数 3爱元 +26 收起 理由
    pcb + 4
    老票 + 16 涨姿势
    住在乡下 + 6 给力

    查看全部评分

  • TA的每日心情
    难过
    昨天 06:15
  • 签到天数: 3181 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    3 q. E. i) i% D我推理机的核心算法应该是二叉树遍历的变种。
    / @* [& A) C- E另外知识系统的推理机搜索深度(递归深度)并不长,没有超过10层的,如果输入变量多的话,搜索宽度很大,但对那时的286-386DOS系统,计算压力也不算大。
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    板凳
    发表于 2025-2-2 00:45:59 | 只看该作者
    Recursion in programming is a technique where a function calls itself in order to solve a problem. It is a powerful concept that allows you to break down complex problems into smaller, more manageable subproblems. Here's a detailed explanation:, [. [+ F3 {" K
    Key Idea of Recursion
    $ N+ ~; B. E1 |  f; Q8 J4 U% N# U/ Q
    A recursive function solves a problem by:
    3 Z6 N# _% m- i. @' o# ~) t
    1 e, [! Z  ^1 |  g! {) A    Breaking the problem into smaller instances of the same problem.
    . i/ }- i0 I1 ^
    : H/ [  @. b" i, v    Solving the smallest instance directly (base case).
    " I! v# @- R  t* e
    ! \. T# N; M* N  r; D    Combining the results of smaller instances to solve the larger problem.1 U/ d* I0 i" h! X9 D, w2 [0 s  o
    / S2 e6 i) @; f7 r* ?) u
    Components of a Recursive Function' n; C7 x& A/ Y* f2 k  o5 g% l

    7 H0 {/ R( Z/ @' Y3 ~2 X* c: L' j    Base Case:) L# k% d; ^) w" v1 P% ~9 l
    . T; \" _( z" {7 N5 T! x
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.* w) C6 [( b5 x0 u  e
    5 A" b! N3 Q! d! B- E+ N3 d. O8 G
            It acts as the stopping condition to prevent infinite recursion.+ }& C) X1 i9 N, U7 d8 k

    4 H( `  U5 l5 T% r6 k6 g! k2 B        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.! h3 {: B, a" k  @" T2 \6 `) D

    ' |; D- T% c* J" E9 [. i+ N    Recursive Case:% N* K, r. k1 U; u" c" L
      P4 {3 D( H7 F! C7 N  U' ?. Q& v
            This is where the function calls itself with a smaller or simpler version of the problem.7 O3 U2 Z" f: h( M& j: @. T3 }

    / b! ?8 v' v0 t4 v. z( N2 H        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).$ M) [* K! i) N

    0 `( _0 |5 S1 c5 f5 JExample: Factorial Calculation
    8 s  C9 _9 f  u5 M  G1 k3 y# m
    2 d) k! \4 v. ]The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. It can be defined recursively as:( [! l; q: _! K1 c+ s1 l
      G& k- H* j  O% `
        Base case: 0! = 1$ v% }; C8 l6 ^
    1 j1 T7 z: m; X. a
        Recursive case: n! = n * (n-1)!
    / X0 O  i, o4 }( I: o9 w/ l5 H1 c$ ^8 B- J2 l5 e( F
    Here’s how it looks in code (Python):- q6 e5 H2 \$ x6 w7 Z
    python
    8 R3 b) U- G5 Y& x
    * f& n+ A) d# z0 A9 l& m& C3 l( m" X7 A) o% [
    def factorial(n):
    9 C* X& d9 X4 ?+ o8 k    # Base case
    ; V7 h- e' n1 z0 I( V0 x    if n == 0:5 @. A5 L, u0 ]/ e, D  M  s
            return 1
    6 V% Y( x( [" s2 t1 q5 `# x    # Recursive case
    ) b# v7 Q+ w6 N( n% F    else:' p4 {* N! O* c" i7 I
            return n * factorial(n - 1)
    1 E: `% l  A$ _0 z! v8 _" Q
    7 l% `) |* O! T, A( [# Example usage
    " c+ f' B$ u! B3 bprint(factorial(5))  # Output: 120+ ]- ]# V& B( ]8 t; _
    9 p4 A* r4 J; v+ ]
    How Recursion Works
    + V2 X4 J& d' U% `. }7 D2 k' Y1 b3 S5 Q& j, Z3 D, K! ?
        The function keeps calling itself with smaller inputs until it reaches the base case.% u: h7 c  N( i2 h
    2 v  _% a: K9 U: e5 a; M
        Once the base case is reached, the function starts returning values back up the call stack.' T# L( @3 l+ w2 X! V9 F

    2 p- @, i. ^3 N! y. A    These returned values are combined to produce the final result.
    ) f3 w) m/ F1 H1 ^- \4 _. u+ o) Z' n6 v% a9 O' Z& M) T
    For factorial(5):
    4 Z; p- J. L1 V! y
    + }: d. d9 `& [* _& q, ~2 p0 L! W
    6 f- Z( M0 x8 t6 b+ K3 Ifactorial(5) = 5 * factorial(4)$ y, n% u$ w& m6 v
    factorial(4) = 4 * factorial(3)
    % h3 ?9 r( {$ ?1 ofactorial(3) = 3 * factorial(2)
    . I5 Y" l/ W1 L7 Pfactorial(2) = 2 * factorial(1)
    8 p& J, e! R2 _! e; A+ {factorial(1) = 1 * factorial(0)" `6 I3 ]5 S, Q/ L/ ^
    factorial(0) = 1  # Base case$ Y4 R' Z& L1 ?6 ]: Y8 S
    / \/ n! N) B: U/ d1 \
    Then, the results are combined:, J% [& J+ Y" b, u2 d% u0 H: T
    9 L4 B+ `0 q/ s2 `# Z
    ; g0 W+ v, G8 U& }* |
    factorial(1) = 1 * 1 = 1
    % l0 ]; M7 Z3 A9 p; ~7 Gfactorial(2) = 2 * 1 = 2
    # t* V0 a3 S4 h- c0 X- T  f4 F1 hfactorial(3) = 3 * 2 = 6
    / D( b: |5 f5 B8 X5 l$ g6 f  tfactorial(4) = 4 * 6 = 24: d1 L5 [& J8 \6 _/ J# O/ `* Z
    factorial(5) = 5 * 24 = 120
    3 R' m9 ?9 b2 D" r9 B' A$ B2 ~( O
    Advantages of Recursion  R$ I1 O4 f! b' u( t4 r) P
    ) z; z7 H" S8 J3 q
        Simplicity: Recursive solutions are often more intuitive and easier to write for problems that have a natural recursive structure (e.g., tree traversals, divide-and-conquer algorithms).
    + _; b$ W' D: N% c0 k5 H6 q& Z% s1 }5 J4 |7 f' D
        Readability: Recursive code can be more readable and concise compared to iterative solutions.2 R; G6 i& Q8 E* i1 j$ Q
    3 K8 j; A. {2 s: o9 n
    Disadvantages of Recursion& U& @9 u' r- F2 s& V

    ) s8 g# m0 D8 D4 ~1 e- G    Performance Overhead: Each recursive call adds a new layer to the call stack, which can lead to high memory usage and potential stack overflow for deep recursion.. R, Q) D9 B1 B. R: K
    ( ~7 ^% Q; `- s2 N3 W* D$ e
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    5 H  g7 G# B- R; i& l5 @' ]8 \: ]
    When to Use Recursion
    : M4 H3 y- G  [+ F" q( @: N$ P5 d4 @* H. }& w2 w9 o3 }  |: O
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    1 P4 i' u* \5 {2 A- _2 b$ B; ?$ S2 l8 R. o
        Problems with a clear base case and recursive case.
    . O$ W/ n' i  p/ d: W
    / {, u. x" B1 l" l) TExample: Fibonacci Sequence: k; Z3 d5 _" U# z
    / J3 \4 I6 w' v+ ?+ e. R9 E
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:3 m6 C+ M2 a% q1 _

    % z% h2 B8 r- |1 Y9 j, |( x    Base case: fib(0) = 0, fib(1) = 1. ~1 |8 Z5 N/ R3 [. |/ Y- Z3 P
    ! i8 c  g3 I! c
        Recursive case: fib(n) = fib(n-1) + fib(n-2): [( i& C+ ]; N8 y' u. m2 O
    - m6 m4 Q: @1 l8 T" ?! @# @
    python8 i8 h7 Q/ D. a. m7 ]0 l* v
    : A" i( Y' c) Z; U9 X

    , N" U3 }- q" D9 V2 z: h, {! ?! l% Jdef fibonacci(n):
    8 i; V) N/ `7 J& j    # Base cases
    + s6 w( |1 h! b  Z9 f+ @5 K; Q    if n == 0:
    ( `. {) }1 H# M  @% U        return 0
    - I  k/ I& V  V1 |3 g& q    elif n == 1:
    , R' l7 [8 J3 a2 C( o        return 1; |6 ?  y6 i2 I* b
        # Recursive case; ]1 a6 B% [" S) F, o
        else:
    & O1 e& x7 o4 D& X) _        return fibonacci(n - 1) + fibonacci(n - 2)" _# t! j. h. j7 ^0 @2 q. T% y
    6 I$ h: S! L0 ?0 G7 X
    # Example usage' {3 I7 A9 L1 U
    print(fibonacci(6))  # Output: 8
    % j+ b  u% [+ O+ [+ I5 q, f% o
    - }# e, s+ s. C3 L9 }Tail Recursion- w- T2 p% b( E; |1 Z. Q/ R

    / X& l" X6 `$ k/ a+ STail recursion is a special case of recursion where the recursive call is the last operation in the function. Some programming languages optimize tail-recursive functions to avoid stack overflow, but not all languages (e.g., Python does not optimize tail recursion).
    4 m3 W+ A; X$ l5 ]; ^" w, V2 [! t5 Y% s0 }1 |  g
    In summary, recursion is a fundamental concept in programming that allows you to solve problems by breaking them into smaller, self-similar subproblems. It’s important to define a base case to avoid infinite recursion and to understand the trade-offs between recursion and iteration.
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    地板
    发表于 2025-2-2 00:47:27 | 只看该作者
    我还让Deepseek 给我讲讲Linux Kernel Driver 现在的开发流程,让一个老同志复习复习,快忘光了。
    回复 支持 反对

    使用道具 举报

    手机版|小黑屋|Archiver|网站错误报告|爱吱声   

    GMT+8, 2026-2-23 02:26 , Processed in 0.057931 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表