设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 / e, W6 K& \) k% j4 y* [2 U1 l

    % _  M% Z; |4 x* H4 |; t! o+ q# I1 l' j1 Z解释的不错/ f* N: w! ~! @5 i$ P
    ; M$ Y1 _- X. k+ T! d1 k
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。, l+ w. B/ a+ ?

    ) z; @' B8 P2 H/ z 关键要素! ?! Y( m9 [1 E, P
    1. **基线条件(Base Case)**
    2 S' K* a7 J4 r2 q9 k: _& V   - 递归终止的条件,防止无限循环
    1 a8 f1 L( `0 M) r8 v% B* }   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    $ q! U2 A& L6 V. z6 o* D$ ^, O) n8 E8 L/ m  ?
    2. **递归条件(Recursive Case)**
    6 [& s4 Y7 I! `+ z   - 将原问题分解为更小的子问题
    ! k2 [4 Z5 n2 H3 I2 m   - 例如:n! = n × (n-1)!6 G! X5 A6 @! w! w, M
    ; l" K7 ?. i  H2 s! d
    经典示例:计算阶乘
    8 i1 Q" i) H; |5 \" v; Cpython
    + E( J, x& T3 Q7 \- K& X- z" Sdef factorial(n):
    2 I( I5 o) t) \# c    if n == 0:        # 基线条件
    ; X& E2 g# S6 G" i4 n        return 19 j9 g/ L) K9 G
        else:             # 递归条件: f9 m9 s1 i( b) i: Y
            return n * factorial(n-1)
    9 B6 h* z' n+ w; M执行过程(以计算 3! 为例):
    ( O. f+ d2 C: K+ G/ Kfactorial(3)
    ' e8 c3 j$ y! {/ |, S8 n9 W3 * factorial(2)
    ( r+ K6 N: p! t' K: G& Y& G3 * (2 * factorial(1))
    ( [. ]# x8 l- X( N  C3 * (2 * (1 * factorial(0)))
    7 M& U& X) i/ x* ^1 L3 * (2 * (1 * 1)) = 6
    + g3 p. R/ A" h/ [0 ]6 _) Y; ?0 V( J* u3 N) o
    递归思维要点$ m9 ?1 R- q0 w9 |' A
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ' D: ^4 V" k1 x' ~- I0 [2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    # z" c" K; H9 T0 t3. **递推过程**:不断向下分解问题(递)
    / u) R" p) I$ v4. **回溯过程**:组合子问题结果返回(归)
    " \$ V8 b  v! b. N9 O) v2 p- k/ S: H3 s# U3 n7 }( x4 c, y
    注意事项
    5 |* x& c! `' y( a& E8 l9 i必须要有终止条件. C6 u  ^8 M2 ^2 V- i" T8 q7 U1 C& B7 X2 ~
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)) O- p$ E! u& U" T" p
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    + {, A# |' V  G9 b  p+ T& }- O尾递归优化可以提升效率(但Python不支持)' L9 ^4 C8 @& u$ @

    ( v  H) u1 z9 `% Y) K9 D3 |5 \ 递归 vs 迭代
    ; A- E8 B7 `' \|          | 递归                          | 迭代               |, D) E$ B- ]8 n6 }' H1 l
    |----------|-----------------------------|------------------|
    : [8 D+ B$ `% H# ], d| 实现方式    | 函数自调用                        | 循环结构            |
    ; d, k9 p, v2 Q' Q; ?- @# W, A4 [| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    # T1 w4 W  Z$ O+ n% U| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |2 Y# H6 @9 V+ N; W# U1 \
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    2 L. x- K% G8 `; a1 ^1 g1 c; L- Z* ~, P5 c8 P. V& o6 \8 [
    经典递归应用场景
    1 W% N5 `% e  S# n4 V& _1. 文件系统遍历(目录树结构)
    5 M9 X2 l9 U8 T0 H& j2. 快速排序/归并排序算法
    ( m- a; Y3 z, V& p3 D3. 汉诺塔问题8 ~4 S* a2 f' M0 q4 i9 f6 P& ]
    4. 二叉树遍历(前序/中序/后序)5 ~( v- h6 c+ M8 F2 r; X( p
    5. 生成所有可能的组合(回溯算法)
    7 ^9 |. S  c1 B, c- W% ^9 F/ U+ J3 h/ q. \
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    昨天 08:41
  • 签到天数: 3228 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,% m2 o7 g9 K0 N
    我推理机的核心算法应该是二叉树遍历的变种。9 l. w6 C$ ~" d
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:$ E  b. w0 B6 a2 {# `: e
    Key Idea of Recursion
    ; ^% t2 v3 }* i& g- }
    . s9 j  Z$ G0 R! i6 K" k, VA recursive function solves a problem by:' U' `" l2 p- W9 w1 m

    . p5 R1 D+ ]' _' s9 Y6 H    Breaking the problem into smaller instances of the same problem.
    . S1 ]  y" Z% r- \1 X; K
    8 D& \% m1 W6 k) {& C    Solving the smallest instance directly (base case).
    ! c3 G& X& U8 g, r/ M/ {2 h8 ^4 [; s8 I: E1 m
        Combining the results of smaller instances to solve the larger problem.- w5 U0 T7 O, J! ^# ]. C7 Q

    9 s& A+ I' K" e' m! r6 }# C) qComponents of a Recursive Function0 w7 g0 h9 v8 {6 n4 x
    / R/ h+ u  U3 X; k5 t7 D5 @% H
        Base Case:
    ' ^3 _, q$ U% I  ~: I0 |# Z7 U
    5 ?. A1 w! I. ~        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    * }, ]7 }) Z# k2 ?% f$ E, W7 Y  x. y
            It acts as the stopping condition to prevent infinite recursion.2 ~8 A' k4 N$ P; }  K
    . q( Y; ~8 m' W" q
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1./ N* V6 o3 C2 C; ?: a& d4 z6 F$ Y
    5 h1 \) A" v) w! y( \7 N
        Recursive Case:
    3 _3 x6 o2 ^( ?$ A6 q* N* }$ i" D; y0 y/ k
            This is where the function calls itself with a smaller or simpler version of the problem.
    ! c6 `( a5 {/ T5 ~4 Y. B
    - I4 T/ N& }5 u" Y/ n        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    . r1 Y/ h) d4 \9 q  F- X- p6 M# H8 L" M9 o9 T
    Example: Factorial Calculation+ w3 p7 j( r( g) P* y" C
    2 n) b1 L  S4 n$ f" b
    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:2 D1 ]/ V0 O, A' T2 i
    - ?1 ~7 v# ^3 r+ ]$ J5 A0 \) j0 Y0 W  ]- N
        Base case: 0! = 1( ~; [; H' ?1 C
    / Q4 {& v' t, E4 M) h3 T
        Recursive case: n! = n * (n-1)!
      _8 {" v& r' L1 b) v2 F9 u$ |- ?8 }* \
    Here’s how it looks in code (Python):
    - N: g7 {# t2 O) Lpython7 N* C/ c+ q# I( N0 h$ P  c
    . x3 |4 g3 n; v) H
    + Y' K+ D+ I6 Z; m" E) j: b
    def factorial(n):
    7 U" R2 r1 b1 S1 \+ r    # Base case
    3 M# [2 t- i; i    if n == 0:
    % w4 p  ~) V  ~; Z5 F        return 1
    2 O: z# i( B$ p5 }: \8 R    # Recursive case7 x; c/ H" E; c
        else:5 o1 o4 O1 w( e5 |2 e: v# M5 c6 t) x
            return n * factorial(n - 1)+ @1 g- I+ W* w9 ]% I. {' C+ ~  U8 q
    & b/ O$ V- X* T/ X
    # Example usage; v! H, P7 a7 n# h+ M! W
    print(factorial(5))  # Output: 1208 H& u* B" z! u& u! u
    + L- y1 X% R  ?$ g
    How Recursion Works
    # O& B" d6 o% u: A0 G
    4 C1 E8 G# I7 x( {. d$ o) U    The function keeps calling itself with smaller inputs until it reaches the base case.
    " ?* g5 R7 }5 t* E8 h5 v& Y$ O/ L. w' z/ ]
        Once the base case is reached, the function starts returning values back up the call stack.6 E3 T! Y# A7 {& r0 a

    5 L* y9 [% v/ A' m$ \2 k    These returned values are combined to produce the final result.
    - B4 T3 j; ?) Y. [
    ! T0 ]0 W6 g' ?7 u0 u7 V  B( qFor factorial(5):% U& E2 U! f0 l7 r  H1 ^' _6 B
    ; ~6 ^5 `& i) R% B2 m
    1 e& p( O: I3 A4 x. D
    factorial(5) = 5 * factorial(4)
    ' _5 R6 a0 A. h: d1 s! ofactorial(4) = 4 * factorial(3)
    # B6 G0 a* n& H$ H1 mfactorial(3) = 3 * factorial(2)7 I* M6 k/ J# E
    factorial(2) = 2 * factorial(1)
    1 v  w* w- I! w6 R" N) _/ efactorial(1) = 1 * factorial(0)
    6 _1 p( ^) U" p$ `+ {# ?. Z" ]# ]factorial(0) = 1  # Base case
    . [, `! h' J5 c4 p! L6 `' e6 O. J# p. S6 E
    Then, the results are combined:* V  ]! R$ d) c# x' a, o! m
      |. r% M1 s% ]( m3 o2 Z

    9 ]" I- h- m) l3 Yfactorial(1) = 1 * 1 = 1" }9 A* ~6 p/ E  M: x
    factorial(2) = 2 * 1 = 2
    ( T- W8 H! P0 ~6 J. A8 @/ N/ mfactorial(3) = 3 * 2 = 6
    " D" o  \. F9 Z, ]9 l7 ^factorial(4) = 4 * 6 = 24
    % T/ @" b8 I; D% _factorial(5) = 5 * 24 = 120$ m/ {7 @) [& V5 d

    ; p. a2 L' A2 P% _' Y4 rAdvantages of Recursion
    6 i: {) d5 ?' ?" F, e
    0 B* C1 F- Y, ?    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).. w4 M& k$ R/ u/ w. L& w

    : L& t- r  e% g) N/ s, O    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ' R' j$ P$ b! c% f% p/ J; m3 U! y
    0 h% ?" K7 t7 f" C' o- VDisadvantages of Recursion
    % X6 X; R7 g# C* }1 c0 a* F1 S4 M9 B% P
        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.
    ; l8 r! q; L0 J' Q9 Z0 G. U: O: C9 `6 ^7 ~" Y& W$ b- S
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization)., U4 ^9 s+ k* g/ ^! m+ a/ d

    1 T4 ?& T" w* \9 Z3 v4 `When to Use Recursion) W' K9 `' ]0 t+ Y
    # k- D& K0 a: z7 g, a4 I# s% \
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    + R7 `$ C# c! U; L  H$ x7 x) e- U+ B# t; [# y0 y* `. z
        Problems with a clear base case and recursive case.# u( D1 U1 I9 b1 y5 \- a( @% N

    . }3 Z0 C* V. N$ ^Example: Fibonacci Sequence* b: |0 ]! u# o3 ?5 B& {7 @6 H$ {, V

    : j) h6 L2 O- h5 Z. |The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:# Y  z8 B: |6 E: K: L" _

    ! J* K" z- a- m    Base case: fib(0) = 0, fib(1) = 17 s+ f. B$ @$ W% Y
    / y. P; m* E3 b* F! r; _
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    & n  [! y- e5 J) `# d# E; }
    ( z; Q) c+ C5 P+ Ypython0 R) X4 k! z+ R( m1 v7 |, p) o
    & H; q  ^" ?  B2 [* Z

    " v" a: L" J& f) I/ C) Y7 X. H8 s) sdef fibonacci(n):, W2 g* p' m$ A# N$ S; e
        # Base cases7 Z& a0 B6 V. t, M3 [
        if n == 0:
    9 j7 \- p* |' {$ o        return 0; ]1 h; C( k! Z/ B! [
        elif n == 1:
    4 q$ X# {, F" }0 u( ~5 H( a        return 1
    % |# Y. x7 ^' r0 @# D" X( d    # Recursive case% i: S0 e% {! n" k5 y4 C9 G/ R
        else:
    ! V- n. h& A1 Q, I* ^        return fibonacci(n - 1) + fibonacci(n - 2)
    . W- b/ P2 y/ x. L: P6 _% q5 ]
    ! Y, N% A  a- }: Y) R# Example usage- z+ w. K8 O! A) J$ p, j
    print(fibonacci(6))  # Output: 8( e5 k9 `9 |8 R" x3 h1 j$ X
    1 l) x. H8 c; [/ f
    Tail Recursion7 a7 U4 p! i9 ^. _$ P  n
    ( w8 L3 j! J( N2 y
    Tail 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).
    ) ~  Y- S  N* J2 J. F$ }+ ?9 d
    9 M. A/ T, O3 _4 u( t% lIn 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-5-2 16:50 , Processed in 0.059383 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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