设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    : f" C. |& N8 l, W) R* h( `7 A% g
    3 i' G- u. w; H2 a  h1 e5 u  I解释的不错7 c9 j/ I6 g/ P% r- \; m5 Q
    ) @8 T& i" ~' Z5 U" v' C, P0 [. r
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    1 b+ P$ k( I6 I' X1 O+ ~
    : Y$ l! t* F) D  I6 ^. m 关键要素
    0 c5 }  I( i7 r% u' t5 s  C1. **基线条件(Base Case)**7 V, x" S; L7 c/ i. W6 V
       - 递归终止的条件,防止无限循环, Y" P, @, h7 J+ w5 p
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    9 C) }, D' l, e# K9 a/ y1 N+ A3 ]. T1 w, d5 G$ {. Y% e' J- Y8 V
    2. **递归条件(Recursive Case)**2 u* M) P% ]$ n( P
       - 将原问题分解为更小的子问题
      {) H9 _: R+ m, s1 x* |1 _! l" E   - 例如:n! = n × (n-1)!
    ( ~; \+ s- J& q, g; S7 `+ U: l& g# M
    经典示例:计算阶乘
    2 F9 p8 c: b" x. d' C" @1 npython. @  G; F* F/ I$ _  D
    def factorial(n):( h, B8 F8 S5 G. g& n, {4 K
        if n == 0:        # 基线条件8 t( {  b2 c/ J, V
            return 1! ^  S% C9 L- p6 h. y2 |
        else:             # 递归条件$ z0 K; T( H: N7 v& m) y3 U
            return n * factorial(n-1)8 ^: |7 x. X- x+ Z; _4 ?
    执行过程(以计算 3! 为例):+ f7 x6 p3 w6 G0 W0 d2 R
    factorial(3); W4 m! q; ^+ B% [5 ^1 y( s7 m9 J' z
    3 * factorial(2)
    , }8 }: E" ~# z' A3 * (2 * factorial(1))- I$ n  a6 n# |3 S1 k0 }" I! W% r
    3 * (2 * (1 * factorial(0)))% a* E- A: p( K0 T
    3 * (2 * (1 * 1)) = 60 t$ g0 F. t! V* ^+ F
    6 O' J2 ~3 e$ y' m7 J
    递归思维要点7 \# o, }8 T. W; O" c( {$ `
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    $ Y* Y+ D/ v- D; X% o2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 s" }& B) l( q3 z- f. ~
    3. **递推过程**:不断向下分解问题(递)
    ) i5 f. U5 Z7 j# d8 j4. **回溯过程**:组合子问题结果返回(归)
    0 F1 U' ?7 J( X9 R9 w& Q- R, `4 g, q: t3 D, X4 J
    注意事项5 t3 K; n5 v, b2 ~, f2 x, ?
    必须要有终止条件) f% c4 O9 X, q" l1 Z$ B
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)- ]+ G8 G. U( Y& x* U
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    & Y; q4 N3 a7 q尾递归优化可以提升效率(但Python不支持)% v+ X: l* H5 ~: M8 }/ c% w+ C( J

    5 K  E7 d% e. @& C 递归 vs 迭代. U) v$ P9 P0 @
    |          | 递归                          | 迭代               |  F5 @# Z0 W8 C: G
    |----------|-----------------------------|------------------|
    $ v, p( g8 F3 h5 P3 {| 实现方式    | 函数自调用                        | 循环结构            |1 a) N) T$ \& g7 X
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |. \, W! [0 e' u# z/ u* J% p
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |- _$ {- l2 r% [. j/ g% h& Q
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    + v2 i2 }6 o& a% |  U3 L3 M, d) f6 D2 ]1 \; w/ r3 \
    经典递归应用场景2 {. z0 `! S4 M8 s  C$ {! o
    1. 文件系统遍历(目录树结构)$ t& O2 m$ N% P; {. @
    2. 快速排序/归并排序算法
    5 b8 Y9 Y" i3 f  `+ b7 N! @3. 汉诺塔问题( W. r* w+ m1 K1 t1 h3 h) n; e) p& Z
    4. 二叉树遍历(前序/中序/后序)6 U4 r: U9 Y; `3 @0 @: R
    5. 生成所有可能的组合(回溯算法)
    , v9 S4 t$ @" K: ^* u- D
    9 j0 R* f, \( F试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    昨天 07:10
  • 签到天数: 3113 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 S7 n( f$ y( u
    我推理机的核心算法应该是二叉树遍历的变种。
    3 n0 M+ F2 Z( L' \另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:. g* p- T( c+ v- M
    Key Idea of Recursion) D; X2 i8 s% ^; a, L) O+ |  A

    4 Y+ }( R6 y* a8 r, M: i( ~A recursive function solves a problem by:2 r8 h) q0 G8 D: l1 z: b  L
    - Y  m( C6 a) h" V( x- R
        Breaking the problem into smaller instances of the same problem.
    $ b! w3 R4 O- U0 b' ^3 C. |; {6 v3 [" ]& x3 _. b
        Solving the smallest instance directly (base case).
    , U4 m- h; u. C; ]7 S3 o, I! p# R- \' y
        Combining the results of smaller instances to solve the larger problem., c3 a7 K5 V" N+ o7 x# p% ?
    - H! ~" e1 d- p  K! N% Q
    Components of a Recursive Function
    ( u" _7 o* }& k& B  d: I  Q: c" M
    7 Y% Q" ^0 U0 W# ~    Base Case:5 H$ {/ ]0 B" ^2 Q8 T

    5 c2 B6 h; p& V# T6 X        This is the simplest, smallest instance of the problem that can be solved directly without further recursion./ J" I. h/ J7 E% H5 j

    6 Q% {! {* ]3 [# U% b+ b! m" \        It acts as the stopping condition to prevent infinite recursion., r( Q, V) J2 s
    . ?" W$ b5 ^. `) L, `9 I" S" J- A
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    % n8 ~! \0 f8 Y& v
    : Z7 ~3 x" N) y9 |    Recursive Case:
    & A1 A" r$ v# Y, ]  `
    " `/ |4 g, h! K8 n' F        This is where the function calls itself with a smaller or simpler version of the problem./ R0 T# ~- j3 @4 |- W: X

    # p1 R5 n1 w9 B" v! w- K( [& M) X        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    * ?# N2 H( B* m' Q# G  U" Z$ ?" u' F$ [7 E  _# _7 m* _
    Example: Factorial Calculation
    ! r0 B. x, `0 a7 V9 v; h/ ?5 H+ u0 z4 P" `/ m2 t
    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:
    . o3 q5 @7 |5 }, f& u" y% D$ R6 e) v2 l$ t5 O+ Z4 g& h. V
        Base case: 0! = 1
    ' _) W7 ?. x/ U2 B- ~; `, o4 s. t. \  \2 ?/ ~
        Recursive case: n! = n * (n-1)!! V; s& |3 L: [
    1 j9 d. e: }7 ~
    Here’s how it looks in code (Python):6 S$ B, g$ g& v: l+ w2 g6 r
    python
    $ m& k+ i+ T$ P
    4 \/ }4 q& g0 d5 E5 T+ [# g4 D: d4 j9 V- Z+ m' i7 ]. W! k
    def factorial(n):& W- U! F7 I7 l0 b* c! c
        # Base case
    0 y4 {' o+ B4 `" _$ u3 l- W# }    if n == 0:& U( j, T" U% B$ n. g9 S
            return 1
    7 e4 I0 _- R$ t. {9 V; P4 v    # Recursive case
    0 v4 ~2 d2 d: l  h# d    else:) Q6 |, C3 N0 i2 F* X6 Z1 t+ g
            return n * factorial(n - 1)
    * b& H( _0 m: p/ I1 a& n
    " c, T( @3 r7 G( j# ~/ W# Example usage
    8 g9 [5 ~; e. O/ Jprint(factorial(5))  # Output: 120, K2 d) Y$ i% e5 i
    / @5 N0 S3 ]3 R9 C7 Q* d4 k0 I( m
    How Recursion Works
    5 l4 g  i" N; h% F7 Y  [# w0 n$ R
    ; |5 p  ?9 X: R( [    The function keeps calling itself with smaller inputs until it reaches the base case.9 w0 H3 H; n6 L3 U% u0 Q5 ~

    1 M; g8 V8 f* z8 |9 E' U    Once the base case is reached, the function starts returning values back up the call stack., I* |! P3 ^- ~9 z$ T
    ( S5 p& I8 U  ~' Y
        These returned values are combined to produce the final result.
    ! I; K; R! [( Y4 L- f
    4 ?* A* K' b9 ?3 [For factorial(5):: T0 y3 s& V& Y: z: q7 n. k
    2 N! T0 \+ V+ d1 B  z  R: R! P

    ) }4 _9 y; ?; x* u2 k0 |6 ?* nfactorial(5) = 5 * factorial(4)& R; b/ n( Q# \: ^' ]+ d7 M0 B
    factorial(4) = 4 * factorial(3)
    ; m! |, f/ q! D5 L/ ?( z  N0 U# Y/ n$ Ufactorial(3) = 3 * factorial(2)& H1 _6 x3 D: Z
    factorial(2) = 2 * factorial(1)
    ! ^9 `# |- q5 p5 V4 `factorial(1) = 1 * factorial(0)
    7 t! o9 R5 J, }! nfactorial(0) = 1  # Base case
    8 c0 w, x4 S0 c; A" I5 R
    . P- I- e4 q/ Y! @& R! sThen, the results are combined:- c3 }4 B& p& E9 O' l+ |5 n
    6 S6 S& J2 i: Y7 N" U
    . _/ {8 W: c( H! j/ v* w& d
    factorial(1) = 1 * 1 = 1/ L! ?9 q! ~/ W+ T
    factorial(2) = 2 * 1 = 2  G1 f, s3 k; \3 b1 n% ]2 f" Z
    factorial(3) = 3 * 2 = 6) }+ R6 k5 T( ?- T
    factorial(4) = 4 * 6 = 24
    0 t/ V( ]* m, \8 r; T# I9 ^factorial(5) = 5 * 24 = 120' N! ]: L8 s; K2 [  e5 ~0 T" x: z

    5 [+ ?, v3 N2 b: x) k- cAdvantages of Recursion0 p( L2 j* `7 e0 Z+ U) n
    / R: R8 E; s0 Y" Q# z
        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).
    3 x. A9 R+ U4 ^( _
    $ G$ z' R6 Z/ m" Q) A    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ) V: x8 Q* n- a: `- K
    8 N0 M; v( @9 M; |Disadvantages of Recursion8 y9 ~/ |% L5 Z7 H

    1 z$ D; R3 |/ S  w! [6 n7 k    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.% M* E9 _; o$ ?9 \

    8 Q5 G: m' |8 p: K( G    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    / h- d0 D: S& M5 ?9 o2 ^% M3 I" ]- x8 A) t& k
    When to Use Recursion' @) f( C) w8 u1 Y4 {2 d; E/ m  T

      [9 k% f9 r5 m( n) C    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    4 K1 T0 K6 B: R
    ( L5 n" M& m" j* B1 ^( a; N    Problems with a clear base case and recursive case.
    & }3 J' n# c% m( I$ Y/ W
    - M) N/ V; \  k7 ~  s9 k- h6 AExample: Fibonacci Sequence
    6 G. D  t$ ?$ h, y0 A9 G% `) s5 P. H: D/ W7 d; J: y" x4 x  p# A6 I
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    3 f* j2 b1 r3 p5 k: [6 F
    + F- U/ J0 e5 [9 W    Base case: fib(0) = 0, fib(1) = 1" `0 A9 p) ]0 Q% m$ _

    * q& a: J2 f0 l/ k    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ! [0 @0 r# G3 H8 i2 ?0 B7 u2 S
    ! w" M# b; R& l# _python
    ) z' |- b) V" a: d) r
    / b7 d. j- t& ]# M  v0 }) i  r, L9 `5 ]3 v& Y# M
    def fibonacci(n):
    " b' U- y* c: l- F    # Base cases) ?0 q9 ]( }$ ^8 V/ S) r
        if n == 0:
      E- d5 [9 J  w* l& h        return 0' ^$ O8 T$ o8 M8 v
        elif n == 1:
    2 Z/ a" K8 w6 `6 k& _" i8 j        return 1
    0 b' N' u3 T2 ^& F    # Recursive case
    4 J0 b0 B" R+ b/ |7 Y# Z    else:, B2 y. j  ^% I3 t) L7 w
            return fibonacci(n - 1) + fibonacci(n - 2)6 X. a! t- S9 J1 V) L, ?
    ! q5 q% e, R% p$ R
    # Example usage
      K; }- T. g; m) n+ ]print(fibonacci(6))  # Output: 8
    ) i3 |/ _& Y% g1 `& ^- D5 u& d8 ?! [- i
    Tail Recursion) V* d, N. l% x' r* ?6 Q/ `$ P
    , C7 U" X+ {- g% A- n
    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).$ ?9 u- w; R. x# a0 w
    & e3 P& Y  ?6 a/ C
    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, 2025-12-10 01:24 , Processed in 0.032740 second(s), 24 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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