设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 # ?7 B! y- k" i( s

    # D! M' L) |. h! R; S' \* c  M解释的不错9 [9 X% H+ n# `* W  I! L* z* j; W& S
    & E; W: l) l: B- b% I6 y; f2 b
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。5 `5 B8 B' W, y+ g: d5 H$ A8 g
    % X& |7 B, c" A: g' j
    关键要素
    9 G) E3 M9 z3 C; G! q1. **基线条件(Base Case)**) G9 K: a6 Q8 G
       - 递归终止的条件,防止无限循环
    * G/ ?) F3 k, A* M4 _+ g/ `  p  K   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1! Q" h: Y5 `' B8 R6 U

    ) s) m/ N& \& x; o$ s, X, D2. **递归条件(Recursive Case)**
    " Z, X, D! [% G% p7 S( \. d* |. n   - 将原问题分解为更小的子问题
    1 A! }( W; V3 Z8 e   - 例如:n! = n × (n-1)!& k, e) k8 _$ v/ I9 z

    # _: q8 s, x; W: p 经典示例:计算阶乘
    ' M6 ?# a2 V& i" R7 T1 Xpython( i8 W& H* [' ~$ x' ~6 ]; n- i7 c
    def factorial(n):7 w+ `" V9 ]( f% W! u
        if n == 0:        # 基线条件* q3 v; X' \; v+ E5 O6 l/ h
            return 18 d4 b. T+ }' b: d5 ?8 X
        else:             # 递归条件1 ~9 I# `- M  E
            return n * factorial(n-1)8 T& f) u+ }( |
    执行过程(以计算 3! 为例):( x/ K. h) O1 J7 k
    factorial(3)! V$ k' I% ?3 s* G* t. P* y2 N
    3 * factorial(2)
    ) c9 w" U* [, |9 ?* o# K: D3 * (2 * factorial(1))5 H0 ^5 z$ a* W/ P
    3 * (2 * (1 * factorial(0)))% P' [- Q# t5 a; W
    3 * (2 * (1 * 1)) = 63 g1 B8 W+ y( \: T0 i

    $ R: |2 `+ B* t3 D9 W 递归思维要点
    3 }, b: z, z" q1 s1. **信任递归**:假设子问题已经解决,专注当前层逻辑$ Z0 S: a7 D5 V1 i
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    7 M1 |* i( E8 z3 @3. **递推过程**:不断向下分解问题(递)& x4 {! M3 R5 h. Y0 l. O' X% d
    4. **回溯过程**:组合子问题结果返回(归)( x$ W, s; G. {" Y
    ' ^" z) l3 N  e$ C' E2 B- k# W
    注意事项
    1 U( G4 ^1 W, _& N3 E0 M# w9 E必须要有终止条件
    1 K% }" g0 P. q. l) T9 J递归深度过大可能导致栈溢出(Python默认递归深度约1000层)9 ]4 k, u- g9 o: x5 a
    某些问题用递归更直观(如树遍历),但效率可能不如迭代# S% k9 f+ M3 H
    尾递归优化可以提升效率(但Python不支持)+ [3 p0 r5 B4 n' w
    % M/ B, E+ _! }- D* X8 \
    递归 vs 迭代
    & e5 V" H( o: m7 _|          | 递归                          | 迭代               |1 k9 b9 q: U! V# W" H+ ?: \4 L6 a
    |----------|-----------------------------|------------------|
      e& M8 Y9 |) w! {  l  X' S( F| 实现方式    | 函数自调用                        | 循环结构            |
    - p4 \' G6 {4 R: t| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ( i& q! G  E1 }& z$ r* c| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |% }  Y# {; k( B3 K4 @
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    % M4 \9 @: f/ A
    % R+ A; t6 u0 v3 i 经典递归应用场景" V0 o7 |  Y8 E: U4 M" F
    1. 文件系统遍历(目录树结构)5 c; X- C' K: h" p
    2. 快速排序/归并排序算法# o0 g0 Y9 @# }/ v2 K
    3. 汉诺塔问题% X# G+ w% _+ S5 V) l/ V' m
    4. 二叉树遍历(前序/中序/后序)3 j$ ?7 j5 P  h0 l8 j
    5. 生成所有可能的组合(回溯算法)0 g5 X1 \2 |, K/ c2 [& I+ V
    ( [& `4 Y" f9 M4 o
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    7 小时前
  • 签到天数: 3160 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    0 Q0 K4 `  o; l( |* b5 D& i' ?我推理机的核心算法应该是二叉树遍历的变种。0 @, X% f$ K. W! S
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:" l+ H! M3 y8 t" F. n
    Key Idea of Recursion; Z, t5 ?4 C7 n" W
    ' b5 g0 e# k' C3 B9 g6 n
    A recursive function solves a problem by:
    * W$ l+ L( P2 a  q/ ~0 Z3 T
    8 o4 j- }, _( w3 L+ @1 y# N) ^* e    Breaking the problem into smaller instances of the same problem.
    $ M9 k" v& Q: k! J: c' }
    5 [9 h% ?8 Z* b. B7 N# s6 B    Solving the smallest instance directly (base case).9 H/ l8 L& b0 y6 a; _) J: |

    ; H: Y# ^" g  g. o    Combining the results of smaller instances to solve the larger problem.
    " g8 r' {# D2 X5 v* v6 L7 Z4 Q! ~9 @2 f6 ~. P" |
    Components of a Recursive Function
    " D0 B1 B/ |8 i3 h! U* b$ n, V  G
    5 D1 A2 C8 Z& V5 ~    Base Case:. P6 G; z0 t( E
    7 _: b5 \, V5 f8 S% m: a" z: z
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.% |4 i( s* S$ h6 D# _) _

    7 J( A- i3 L1 @2 R8 ~* |! i2 Q        It acts as the stopping condition to prevent infinite recursion.. L0 ~2 s' |8 B& x* ]
    ; g5 U7 H5 S! F
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    8 _. P: x. j  P; i4 q
    5 V8 y6 ^$ b& g$ E+ V; [6 _& k    Recursive Case:, d  D* l$ V; b+ ^7 g

    8 h8 M" H2 E4 B        This is where the function calls itself with a smaller or simpler version of the problem.
    $ b  G( c3 g. K, w0 q1 B' d+ u4 g5 T6 o! @  @
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).% l8 D# @9 y" s' U: u& V  S
    / [) F" `  R. q9 m' K
    Example: Factorial Calculation
    7 }+ j9 {- G9 R/ X- c/ Z; `* F
    . W- d; H% W& W& NThe 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:/ e+ k1 k0 I! P3 @0 U
    - n# {$ E9 _& `1 ?# e6 C/ Y
        Base case: 0! = 1: g# q( }0 b, b: S" h5 u% |* O
    & T5 J1 p+ T3 _) V" _4 t! i  R- M: N. D: m
        Recursive case: n! = n * (n-1)!
    . x' |  B0 e" W. T0 N2 N: ~6 K1 U$ a0 [  U1 y
    Here’s how it looks in code (Python):% W/ s9 e% K. X9 _
    python/ X7 m6 x1 c  }; v5 T% i
      x, J2 }% x: S8 y4 m

    1 Q" ~2 L9 W/ X) Cdef factorial(n):/ S, m$ F% G  t7 D. p$ s8 N
        # Base case( q% o0 T3 W+ C- @& L0 n+ O
        if n == 0:
    1 h' s& w* G: ~2 A" ^0 n        return 18 L8 o: y# T- Z5 c1 S  f$ W2 i, i3 c
        # Recursive case
    + e. _4 E" V; J3 h. E    else:' g6 b9 x; k1 C5 w2 a
            return n * factorial(n - 1)- R5 j$ d! u0 F8 U# \

    9 G5 h0 ~( k+ H( F# Example usage
    + W& K: g9 N$ c7 y0 Uprint(factorial(5))  # Output: 120
    - k# Z3 F* n! F% T4 N" e% Q. c# m9 o* m8 j: H# W% Q7 p5 }
    How Recursion Works
    8 w) x* q; `, K6 Z, `/ E9 V& \4 z
    5 k. Y7 t) H+ B1 G7 R  [    The function keeps calling itself with smaller inputs until it reaches the base case.
    6 L/ Y4 t8 S/ {, U
    % m4 d' `3 g7 Y5 J, _9 G* D    Once the base case is reached, the function starts returning values back up the call stack.
    5 i8 K' e  r; U) O! G+ {' b9 F' H+ b# u3 O" ?) h; Z( W( l5 P2 v, y
        These returned values are combined to produce the final result.5 M5 m; g- V, C0 S' W$ m" I

    * M$ j3 x* V$ s. y5 r4 RFor factorial(5):7 m- x2 [" F# Q0 G' E' O! Q0 T

    & y3 [' L0 b2 d/ E; k9 I; S# g# V% m6 [0 N
    factorial(5) = 5 * factorial(4)9 y5 c; A* x. b; h5 l- }+ y
    factorial(4) = 4 * factorial(3)
    " [+ q$ u2 G  }3 ?# }  }' Tfactorial(3) = 3 * factorial(2)
    / T8 V' [& v, l( N! I+ b% d1 E4 vfactorial(2) = 2 * factorial(1)
    ; m& E1 O. C/ y2 kfactorial(1) = 1 * factorial(0)
    , D' Z1 E1 u  D, }. T, nfactorial(0) = 1  # Base case7 I& s3 _6 ^1 B# w
    0 N: B' I" x) U: H# p
    Then, the results are combined:! d) ?0 c. t) _/ I, w. s

    3 D# S9 B  q) Q* Y, C- [7 y7 E* F* i% i
    factorial(1) = 1 * 1 = 16 a4 I: m% j+ G7 Z% B2 K5 c  Z
    factorial(2) = 2 * 1 = 2% d& v) `' d5 g: u& ^
    factorial(3) = 3 * 2 = 6
    5 H9 X! \) N/ Rfactorial(4) = 4 * 6 = 24- W+ _; ^" t4 _
    factorial(5) = 5 * 24 = 1205 U' u/ D4 l3 e% K. V
    6 _  c5 N. A6 a: ]* c
    Advantages of Recursion
    6 r) ]/ S4 H7 K9 S
    / G8 h# p7 N. 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).: U9 U! }0 m5 I: \3 n$ Y
    8 F5 Z5 v' P/ p
        Readability: Recursive code can be more readable and concise compared to iterative solutions.. a. z' }# I% Y7 c* S
    ( ?9 U9 E; q" ?9 \
    Disadvantages of Recursion
    ( u3 z2 G- y$ d/ O7 }) f8 i  E  P8 f8 [
        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.
    5 q1 h+ D5 Q5 F+ z+ W& r+ C' {9 Z+ }/ N
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).1 Q* c0 p. q/ y

    " \# q* }/ r- _9 [6 q% [When to Use Recursion
    ) |0 P1 n6 l. Q) y# s( w6 w9 v6 Z8 ~5 P9 u: K/ f
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    % U6 N  J! Z/ k1 e+ s" X
    ) x1 R  y" a* @' k( Z9 h8 [    Problems with a clear base case and recursive case.
    ; {9 p% v5 }0 M- O
      V! a7 C1 S: N$ SExample: Fibonacci Sequence
    / p, V5 M* [# z
    + f+ \5 J. z# DThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, f: _6 u0 W6 O% w/ U1 g: R
    4 Y% y. E8 E: E) D( Q& y. G
        Base case: fib(0) = 0, fib(1) = 1
    : f" S8 e, F; S6 R
    - I# u5 g$ m# D0 ^, J    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ; r$ L& L1 m' G3 H' i6 U+ @3 b
    * X+ m- ?. Z& W% [* gpython6 C5 Z+ R. M5 n1 N* w4 ?
    + W# ~% w8 a. m( S2 A# P& r" P" ]
    0 A0 k9 f$ K3 a" j* t* r/ A" W* z
    def fibonacci(n):0 f4 y  h- j4 u& b; H
        # Base cases( _4 q: H8 C! Q  e6 o% }, ~6 [
        if n == 0:; h' _& f7 C+ s9 V# u6 |' Q* w2 [& T
            return 0# P. ?3 W) T' m5 q
        elif n == 1:3 R/ y( g* N! C2 _( i( c" ~9 E2 K% o
            return 1
    & M; |: a+ k8 x* F    # Recursive case
    , E0 c4 O8 a" M, O" Y5 ~    else:) W+ C4 S5 z9 y  V9 U. c. N
            return fibonacci(n - 1) + fibonacci(n - 2)( X" M6 ]( U' R: Q: p6 `

    8 c, h$ o" w9 v- u/ r" h# Example usage
    9 {: p' ~/ d: }6 H" `" E2 F, U8 `print(fibonacci(6))  # Output: 8" i0 ^  p' `# X: w
    / }! L5 ]; b+ V. n
    Tail Recursion. H$ G7 h, L2 @, K
    9 T6 T) v, Q; i2 M
    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).
    2 a/ [. ^# z8 z3 c/ b9 P. F; u
    8 n& F. |2 H9 S; x1 h) @, g# tIn 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-1 16:08 , Processed in 0.055431 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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