设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    # d+ N, A& K2 X
    . A  w; Y7 K6 ?* |7 W' S# t解释的不错: S" s: P5 [5 S. ^. q" N* D

      @. E5 h4 p& t递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。' l) D& V. d+ d& L% g& Y
    3 W* R4 _" h- H* W
    关键要素$ D( w0 p. }: M9 P
    1. **基线条件(Base Case)**: x) A. t* ?$ }9 ^+ X
       - 递归终止的条件,防止无限循环  ~; O: j9 [) ~. ?; s: ~
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 14 I2 g' I! z7 ~
    8 B! h3 f( G% x9 E! K0 e5 v
    2. **递归条件(Recursive Case)**
    # \- ]/ O0 h! s1 h   - 将原问题分解为更小的子问题
    # G1 Y+ p0 E- U2 d. j& q   - 例如:n! = n × (n-1)!& N& I/ J) l3 g/ L9 X

    - j; S/ V( V8 T2 y+ L# u 经典示例:计算阶乘
    * o& G/ {5 O0 ^% ~- H" Y( K7 Spython
    ' M7 x8 l6 r( I( \  A& adef factorial(n):1 b# ]0 Q" R& y9 `- \
        if n == 0:        # 基线条件
    ! H6 d: X7 G" L" P3 d        return 1; ^0 }3 @# o' S- Z
        else:             # 递归条件( Z. ?: b7 e+ z9 d
            return n * factorial(n-1)
    6 u5 r# V+ M* m; \8 `0 ]执行过程(以计算 3! 为例):
    4 [5 U7 d6 n' K6 S8 s- A9 Ofactorial(3)
    9 |" q4 y4 _' T% z$ \3 * factorial(2)' [* ~- V) c. o( S9 J7 P9 X
    3 * (2 * factorial(1))2 o+ K7 q; F: e% C; `& y
    3 * (2 * (1 * factorial(0)))
    ; {+ e& Q# ^) ~8 ^. g  }$ C0 h3 * (2 * (1 * 1)) = 6. t6 l! r4 d! q! A/ L) b

    * S0 O$ u0 f2 f$ H. r* x% h 递归思维要点
    , V+ f6 r% h  J2 }* U5 C2 y, q1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    * d; \/ z7 l0 p0 M+ C& u2. **栈结构**:每次调用都会创建新的栈帧(内存空间), W- q8 b& s* g/ m% u4 c) c
    3. **递推过程**:不断向下分解问题(递)) b7 V0 A; C- w: j8 \' A" d
    4. **回溯过程**:组合子问题结果返回(归)
    ' N2 p. b5 B% w3 E# a# Q: C! d9 F- D9 c# y' E
    注意事项' ~( c3 y  h5 r1 R
    必须要有终止条件" M: y! F9 [7 n# a+ I8 D& N; l$ o
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
      M& R1 t6 D: B+ G$ Y$ X% B# z7 o某些问题用递归更直观(如树遍历),但效率可能不如迭代
    7 L. v+ `. A. f, d4 u4 w尾递归优化可以提升效率(但Python不支持)/ a  ]/ }  j* d# L$ J4 k/ h: F" E
    ; Q, b! \9 d  J! F$ U, r+ M
    递归 vs 迭代5 k) `3 q* a/ s+ i/ B" l
    |          | 递归                          | 迭代               |
    9 u/ p6 l! k/ L5 O9 A|----------|-----------------------------|------------------|8 V. Y' \5 ]5 s! T4 z
    | 实现方式    | 函数自调用                        | 循环结构            |
    ( ~# A2 a% z6 b/ ?# T  m6 X+ k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    : B+ a- e3 t/ Q9 D- o' o3 Y| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |/ ?( C5 V: u  ?) g0 X
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |% y8 t$ G% s" d! i& }7 C5 F- D
    - }( g  T% o  J2 Y' k) a) Z9 j
    经典递归应用场景
    6 |! T# p1 `1 c% O# R1. 文件系统遍历(目录树结构)
    0 T6 B  z+ g  M( p& p- L2. 快速排序/归并排序算法
    1 f1 i# |7 ]4 H9 U/ O3. 汉诺塔问题
    * F5 P; ]2 C8 L! V8 ], l4. 二叉树遍历(前序/中序/后序)
    $ T$ B* @2 f" B4 x# h  A: Q5. 生成所有可能的组合(回溯算法)
    + G2 F8 l& X3 k  g! c3 O' R3 I4 E/ U* z  ?; `+ `- `! J% h
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    4 小时前
  • 签到天数: 2899 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    5 M6 T( @$ X# H/ r我推理机的核心算法应该是二叉树遍历的变种。
    8 s3 o6 r  V& R8 O6 F$ W另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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( @7 ~" J$ U/ w) I$ R
    Key Idea of Recursion
    # v: R+ C. S) Q
    $ R9 [2 v% i( m* fA recursive function solves a problem by:
    - i2 q2 d/ w3 E& A" n4 k9 \) @3 P; a* m. R( W  {
        Breaking the problem into smaller instances of the same problem.
    , v4 [( ^! E$ q9 d; Q! K0 B2 a7 |) F0 U' ^' N1 D( {) T
        Solving the smallest instance directly (base case).( ]1 \# y! |3 O! g, ?; k7 _3 `

    8 x7 ]' I8 @+ ^8 v- O# Y! @6 w    Combining the results of smaller instances to solve the larger problem.& ]3 r3 a- ~5 c* e) ^

    . W1 y! i) A0 s7 z1 n1 U  GComponents of a Recursive Function
    6 N+ {6 t/ F* P9 T& p. L, y* E. s* Z/ w
        Base Case:) v5 a  p- y$ D5 s  N) R1 K
    - S- h+ n0 p. r" J
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.$ Q; L5 {9 M) y5 x( T; |% k1 ?
    5 g. J( E! M5 d9 R
            It acts as the stopping condition to prevent infinite recursion.* t8 O4 j- I/ D- P: h+ J2 T
    ; D' d' C1 b- [+ n) f- c
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    6 \) m! H2 h& z0 C- d; N. d' Y" l( q8 {; _1 V! V) _, V( ]
        Recursive Case:
    ! n/ m0 [1 w/ T- H' N# q
    ' U/ ?8 a' B# o4 H1 R# P) E        This is where the function calls itself with a smaller or simpler version of the problem.
    1 l. L" _- H& c/ M% p% w( J2 M6 _9 Z* p
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    5 ?8 h! ?) v# W$ J: C0 T- o3 B8 ^' V/ a0 \
    Example: Factorial Calculation- }1 V9 F! A1 z1 V: j1 M

    9 n  [8 E/ M/ i! D: a) HThe 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:4 G( N$ P9 W3 l% Y( P
    # ?% w0 A9 L# t& q. H- d$ T
        Base case: 0! = 1  b$ A/ ^9 W. u1 b. Y- y5 v

    , o! q& i/ _3 z6 U- x' e& x  G    Recursive case: n! = n * (n-1)!
    , [& V8 \0 M+ @5 q
    , k% q1 I0 M6 H8 z# t( m6 i  `5 H3 sHere’s how it looks in code (Python):  N' V2 ^/ U4 X" l0 D. b
    python+ F8 h! N/ S) V& n4 p5 I
    9 K0 w' s/ s* s9 D

    ! Q& _7 E! ~% w8 `3 w% J: Y6 Udef factorial(n):* I% o4 h4 P4 b) g0 W
        # Base case4 I, W8 S2 C: B& b5 h
        if n == 0:! Q# s1 i1 |& `- @. P
            return 1
    & j" ^+ T* i, ]9 l) F& I# _- j    # Recursive case
      J* O+ i7 h- J) o- Y, P4 J' X    else:
    ) p4 b; J* y3 ]& M        return n * factorial(n - 1)
    6 R# X7 d- m1 Y  x- ?* E5 n& Z  K5 }* k, @& L. x0 h) z
    # Example usage- t. Q0 e; r( j8 o6 q
    print(factorial(5))  # Output: 120% ~' s: [" D# d0 }9 F" U2 p) G
    : S8 w; g, O! A; S8 v( d+ p  H, ?
    How Recursion Works
    / a7 I7 Y. ]" C1 I5 \% T/ X) q! Z: }. }) j) y- R
        The function keeps calling itself with smaller inputs until it reaches the base case.0 r" G+ ?8 C+ y9 v0 }" Z

    . J! L* B3 x8 M; ~3 F! i    Once the base case is reached, the function starts returning values back up the call stack.) g7 o  j) U. n  ~& I3 r# x! y! G

    % v: C6 s) o8 K- T0 O& V    These returned values are combined to produce the final result.
    # w- [" }. y, c
      o, O4 y0 P# P5 @/ F2 R( x: G5 w3 k" P2 NFor factorial(5):
    2 G% ~" }& D4 R* R4 m8 m7 w! |; U% z) n7 `! `" l$ n' C

    5 i2 q& i8 X: |- P; Mfactorial(5) = 5 * factorial(4)
    3 Z. E3 E- y& C2 D( T4 R5 d: Y1 ffactorial(4) = 4 * factorial(3)+ U6 ~( m  V3 e5 O& I
    factorial(3) = 3 * factorial(2)
    ! ]  B/ X+ n) J5 T, o  vfactorial(2) = 2 * factorial(1)
      B+ N# I  O' t0 sfactorial(1) = 1 * factorial(0)
    9 h( W" g, f; r7 J: dfactorial(0) = 1  # Base case
    ( N& Z9 @$ \& o3 l, ]
    ( z  |4 E( V9 ?1 \Then, the results are combined:
    0 q: J7 k" }- `& E
    ! V( L7 m4 ?9 k& j" m, [" t, c- ~6 _( k! i. ]: J4 a
    factorial(1) = 1 * 1 = 1
    ( T7 D0 A+ q- A# n2 y# A& Ofactorial(2) = 2 * 1 = 2
    ' z8 P7 N$ ^8 H9 N/ w7 wfactorial(3) = 3 * 2 = 69 {" B9 K; V" I
    factorial(4) = 4 * 6 = 24# u+ @; {( T% y6 \+ W7 w2 q
    factorial(5) = 5 * 24 = 120
    & c8 v9 c( a& \& @3 z
    ; E: N. x- [+ I' o0 gAdvantages of Recursion
    6 Q7 g! f3 E; A& `' O
    0 i$ B% c7 u% a    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).
    # [! A( Y8 e! w$ G, u6 F: Y; x4 a, }9 i- }/ f; k8 E. y) I7 X: g
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    6 W/ q9 F! V" d0 R' z0 Q, z
    9 B8 A- G) D, l. q4 Z' MDisadvantages of Recursion
    ' T. ~) ]- S) m) i/ T3 F5 a# c% ^5 V# i$ A9 `
        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.
    , J3 X' H0 ?) c! X( t* p% f2 R, `
    # u# z+ t3 E1 y( @, o' q' H    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).1 E: i1 l  A! h6 z& l6 V& Q

    . D+ K% G3 ~* k; rWhen to Use Recursion
    $ h# \/ v" \3 o
    6 {& I0 B1 P9 @" j& X9 b5 M, z    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).+ x: n% b/ T* [( f
    ( C! M. |( ?& q( T# `/ I7 E1 k
        Problems with a clear base case and recursive case.
    8 n0 f  K/ S; n9 n2 h/ t4 S; D9 |1 p
    Example: Fibonacci Sequence* f+ W  R- U- Y3 Y1 K

    , l# C7 [- D1 I' cThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:" G1 i6 T" l" S

    5 ~" Z2 q& f  h0 a, ~3 V) r3 K8 i    Base case: fib(0) = 0, fib(1) = 17 W7 x3 Q; b# Q$ f( y
    # D, P1 C- `( o. E. q8 `# R
        Recursive case: fib(n) = fib(n-1) + fib(n-2)0 |* Q# B0 S" G- s: E

    4 _" ?  g9 ?! K. gpython
    4 ]2 q' s: A; o  w0 a, j4 C  P& R1 ^( p# m4 F

    ; ^/ ?+ c) e3 a* K# |3 N" fdef fibonacci(n):
    / Z7 [, S, ?' {    # Base cases
    + d# S8 o# B, Z' J/ H' K    if n == 0:
    + F1 h4 I: N  U4 K$ B& l. P        return 0# m; \3 F  o# f  H% q# [3 M. c4 R
        elif n == 1:9 M/ W' j( [  `& F- ~
            return 1- |% W7 z, z" ^/ ]% M7 P3 W
        # Recursive case5 U1 [" i9 o0 r1 u
        else:$ B6 U8 @* D6 C( @( M& w
            return fibonacci(n - 1) + fibonacci(n - 2)' A8 m5 i# M, P0 A6 Z0 E6 K. L
    : a9 a* W8 J5 f; B( V
    # Example usage4 m1 N; F3 m) l
    print(fibonacci(6))  # Output: 8
    9 b! q6 F6 |4 k: S0 s  M7 u6 m  [. n% }5 K
    Tail Recursion
    $ J, p$ _) F5 ^( X7 t. h9 ]! I( D) p, D# |; J
    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).
    4 G. c# u& l* n+ \% W* C9 X5 B5 ^. Q" z
    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-4-23 07:38 , Processed in 0.041734 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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