设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 % N* ?" O/ M+ i& g
    1 v: w! {! R4 x+ e
    解释的不错
      {7 G$ o+ l/ k$ i, E1 e% f
    + M$ i3 x: {5 U, F( x; Z递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    + O" k/ i( j7 N% o" u- {! \' |5 ^
    + ^+ `) ~; x7 h5 J; u, s4 l 关键要素
    ! K) e6 c3 w! c8 s. W& I1. **基线条件(Base Case)**" L3 W- \* h& X2 A2 m! S
       - 递归终止的条件,防止无限循环3 l/ ?9 P" J) |/ R+ j
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - W: p; C1 I" K# }; V" s4 X
    ! V% O# B7 H: r+ i2. **递归条件(Recursive Case)**
    * U; v4 q; S. e9 G; }   - 将原问题分解为更小的子问题: x2 {5 P- U- D, P: F) g) c
       - 例如:n! = n × (n-1)!
    ' x- K1 d! @1 g: p+ b. i+ t0 |. H/ O% J- n/ j* a  E
    经典示例:计算阶乘
    7 M! M( d8 O4 s9 Bpython
    , {* \1 n2 t/ G% kdef factorial(n):% U/ t3 B% e; d3 I- W) _6 Q
        if n == 0:        # 基线条件. Y* T, O# d. Y
            return 10 [. t1 r! ?$ ~( @
        else:             # 递归条件
    # x2 c6 E, j% w7 O' y; a( Y) I% H        return n * factorial(n-1)
    ! }# U( G3 E8 [执行过程(以计算 3! 为例):6 x: r. Y7 ]& w4 o2 q
    factorial(3)
    $ C8 m. o7 t( N5 V: o" {% ^3 * factorial(2)6 m* {8 m  L' F/ s# o; {
    3 * (2 * factorial(1))
    2 W  Y/ y8 S. u7 |' y3 h3 * (2 * (1 * factorial(0)))* U2 ~, ~$ J' M- q1 y+ Z
    3 * (2 * (1 * 1)) = 6/ X+ h) w* s. C- U$ L: Q

    0 U% h' a6 o: a# l, H 递归思维要点6 ~- J9 }. h" |9 ?) u! f) z3 d/ X
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑  E0 p$ w: P2 W9 b2 ?* X
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    # C" X* v: C0 G. y" g3. **递推过程**:不断向下分解问题(递)
    5 a) t: ]  z" _" l* Q9 n4. **回溯过程**:组合子问题结果返回(归)
    * d( \3 i" Y( U( O+ E. b2 t2 F; P0 J/ |' Y$ |7 K9 @9 G
    注意事项& r+ q0 c% \$ ~) Y
    必须要有终止条件
    8 B" M" V4 i1 y递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " Q4 m$ H2 t) b某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ' o# {+ `& V& L  s" E; ^% p尾递归优化可以提升效率(但Python不支持)
    7 ]' R6 R; M1 r- B4 z
    & \6 w# [: `2 M% _9 e 递归 vs 迭代5 s! }  x, Z1 F8 n" X
    |          | 递归                          | 迭代               |
    " P. D0 \3 p  e9 Z9 o9 [. y7 i/ G|----------|-----------------------------|------------------|
    * w! F. C. t( q5 G! q| 实现方式    | 函数自调用                        | 循环结构            |
    : N. N2 y+ t3 K" a( f/ C| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |9 n( _6 s: T* u; {2 k& d* J
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |' U* D! I5 \3 R7 b9 }
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ; ?; t& S" H. p6 W& W& |0 T" _8 h. c! G4 I( n3 K) s* S
    经典递归应用场景; s( \  A- |5 b/ _3 Y' [$ b0 C
    1. 文件系统遍历(目录树结构)+ P) V) g) ?+ s; k- L! H' j# ?
    2. 快速排序/归并排序算法) e# j* K1 `9 [, Z
    3. 汉诺塔问题
    4 }' l# |, y' R  z% M4. 二叉树遍历(前序/中序/后序)
    / V: Z7 J+ H" Z5 |; W  `5. 生成所有可能的组合(回溯算法)
    5 v4 s' N- p2 P: b. T  \, ~0 z& N
    - `9 ?7 o1 i# L# p. Z( ~" }% `4 P# F  J' H试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    11 小时前
  • 签到天数: 3204 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    - [2 c7 U' v0 }+ @: a2 N我推理机的核心算法应该是二叉树遍历的变种。
    ( v. P0 {7 r" m7 w* `: E: d; l. M另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:! Y& R- I* x/ B8 K" F& f0 C
    Key Idea of Recursion
    0 _9 s( w/ {1 V
    ' C6 ^2 W$ `" d; ^5 ZA recursive function solves a problem by:$ |4 n. [: A9 T) \9 z4 q
    8 o5 z4 y; K0 _: z! v# h7 ^
        Breaking the problem into smaller instances of the same problem.
    0 k6 y2 [0 H+ |1 Q& E! j% x  q# A8 W2 j) _
        Solving the smallest instance directly (base case).
    : O& r7 p! @; B; _) w" X
    ( s" n. d, U6 T- u    Combining the results of smaller instances to solve the larger problem.+ J' e! P- d: V

    ' \6 ?* H7 g: q$ f! Q9 _Components of a Recursive Function) s$ @  \0 r$ \+ ]' r" T' L
    , u- g  T8 a+ @! O
        Base Case:! I3 l6 A1 w# P* f- p

    $ A/ L! a9 x& n. {8 w0 A4 Y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 u( P& }( e3 q+ |' y5 d: J0 a) Q: N. N' H8 z, z
            It acts as the stopping condition to prevent infinite recursion.# U# I9 N! X1 k- A0 c. v
    ) ^% C) t* [  o$ G; O$ \& n
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    & J% M7 \; E7 ~$ w5 F3 J; D6 ?( Q
    9 n  D" W5 g+ P% b1 e! [    Recursive Case:8 F2 g' _* u! O  o

    2 Z1 Y) Y/ T3 z        This is where the function calls itself with a smaller or simpler version of the problem.
    $ k4 W- J/ R. y9 H0 U8 i' B. B% ~  Z: R. A3 T2 S" M: E
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).$ `& |! }' J1 D

    # V% W7 R& l$ E4 E7 |; fExample: Factorial Calculation$ q1 s. d# h( z7 @% j
    ' F; G3 D" q6 y( i. S! ^* S, |6 A
    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:
    5 h# b* X) H; t* b5 z5 U2 ~1 @
    * r* M, i$ E4 [$ ?1 m    Base case: 0! = 1
    , I: e& `# h2 F8 ]
    $ N) g, e- o, m# X    Recursive case: n! = n * (n-1)!
    , i: a/ T) _. D. @
    , t5 Y) T' L6 wHere’s how it looks in code (Python):5 _& \4 `3 ?/ |1 M5 A
    python
    - _" b1 y* U3 n$ x- F: N: P" X- U- [3 w4 L( }9 j2 C! r9 E5 C
    : F7 l9 {8 B; w( |8 }7 @
    def factorial(n):3 c# E2 P7 {$ }) q
        # Base case. P# O9 k+ z! B
        if n == 0:/ b$ v4 o- f7 b7 Q2 g/ O
            return 1, F! T+ Z' M3 W
        # Recursive case5 N  ^: u9 M9 J: |7 T1 ~
        else:8 Y' R( ?5 W1 s' E
            return n * factorial(n - 1)$ s% o, L3 y( Q, p# z. a$ J% @

    6 c( l0 J9 H1 J( ?: p5 Z& ]4 \# Example usage
    8 E2 G9 j/ U( D: D, Aprint(factorial(5))  # Output: 120& s, _; X: W) q5 D+ p

    . ~$ |) q/ ~* b! [+ }" V: Z% K  \$ d7 XHow Recursion Works% R" v$ T4 F3 J* f2 J; G

    2 x4 @, w+ E8 X4 P. x    The function keeps calling itself with smaller inputs until it reaches the base case.
    9 ^* v' `0 g7 z+ z1 d7 ~
    2 W" u2 r" v! `% n- E    Once the base case is reached, the function starts returning values back up the call stack.- C  M- J5 E, E9 \! f: M- v

    ! V! m0 Q% b9 o! {! l, K    These returned values are combined to produce the final result.
    ' a$ U  \/ s5 n: n0 N! M- J
    . g: g6 A- a3 i; R' {3 e: SFor factorial(5):$ {" P9 D1 e8 U( ^1 f

    5 I, ?; K4 q5 g4 ]1 d1 {! V1 c, J: U! G$ w
    factorial(5) = 5 * factorial(4)
    7 F. F8 d3 Y( A  Y4 |factorial(4) = 4 * factorial(3)
      S, G3 V8 i4 L4 Afactorial(3) = 3 * factorial(2)
    ! g! G3 ^1 O" Y" cfactorial(2) = 2 * factorial(1)
    . J3 o+ y) ~3 @  Lfactorial(1) = 1 * factorial(0)
    * @7 H; m  E3 ?3 d7 R* vfactorial(0) = 1  # Base case/ |5 q6 `) B+ K& V* g+ T
    ( S! R7 Y: I" t; V: D+ `0 v  e% Z  s
    Then, the results are combined:/ l5 ?9 q3 E/ W" X4 b0 D. {

    & P9 F: h. B6 t
    . `" Y9 C% p! j, |factorial(1) = 1 * 1 = 1
      J. o# W" v% C2 ffactorial(2) = 2 * 1 = 2
    6 v4 k0 W) x7 U. Kfactorial(3) = 3 * 2 = 6
    8 t. z) j% E- T! g/ Y5 wfactorial(4) = 4 * 6 = 24
    * \. K& \( ?: |# `factorial(5) = 5 * 24 = 120
    3 I+ a/ u) f- Q2 F2 C
    2 y# [0 ^# Y( P% eAdvantages of Recursion
    9 |7 i# K% l7 g8 r% [# I( ~4 k. j: Q: ]% f5 x& z9 C( 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).
    6 A- l( h6 Y; J4 F( h( e7 |# O, w' N9 F& F. f6 y6 g# o
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    # g4 ]; W8 S; V6 h
      @( Q) P: V# m) |Disadvantages of Recursion
    & T1 `3 h! @. |+ y8 u* i% c# Q+ C) h4 ]; |, i) I4 e: n5 ~
        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.
    / [8 F1 F* x+ Z9 ?, Q# p) u1 X1 P: o
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).! H3 J1 W) Y4 A

    0 o6 b1 B2 }4 O, fWhen to Use Recursion
    1 X8 A- h. S7 O4 ~. X9 I6 }& c! N- m, w! N8 L
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    3 z- z5 J4 l2 f. q* S9 f# X( u6 u% G6 ]3 B9 r$ d
        Problems with a clear base case and recursive case.7 j7 X# W- b7 J( Y, R$ Q

    ) L; C7 |  ]( p0 v/ O+ o9 QExample: Fibonacci Sequence4 S( X9 i* c/ Y% L
    " Z' Q6 H9 U2 @$ s2 b* u
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    3 W- l2 u( _8 O) C% O* P- g# ~4 l* y9 n% v" z
        Base case: fib(0) = 0, fib(1) = 1( d! q& d4 Y" y% U* h

    9 r# M$ f. x6 p( |; E/ t    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    " X. P  h+ J% R, l; Z7 N
    : p; e" P! e2 L/ s9 ]2 @6 k4 B" g  ?python7 q5 J+ J! B! Y2 A. m) m( u
    ) [/ O) B2 ^1 A( F7 [7 l
    6 \9 s* H3 H' J5 L; [$ v- R) K
    def fibonacci(n):
    6 T3 V+ w) {0 d, G2 Y/ y    # Base cases  w) y2 D. b4 ], S1 h
        if n == 0:2 W2 m4 c, [7 V
            return 0
      n0 e& @# s, o: G! F1 @  v    elif n == 1:
    1 D! B  g* _7 p( E$ ^3 \        return 1
    . V* G  h3 n# D8 K; H# P  i    # Recursive case
    9 j* G- r3 J: S; l- F1 u    else:7 Y9 T( h1 i9 M, r+ @
            return fibonacci(n - 1) + fibonacci(n - 2)- b2 h5 C3 s  n8 i- ^5 ~
    - q$ e6 x" f/ F: V. o: j
    # Example usage
    ; s7 E, w0 [0 N  e4 {  Pprint(fibonacci(6))  # Output: 8
    7 ^" g3 Y* x+ W8 r2 a
    7 K* D: d9 h" x; m2 c7 A; BTail Recursion
    8 l1 Z7 E( b9 G; h3 }1 R
    & C* O6 ^0 W. ]9 {, N6 DTail 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).! D- r, j4 k5 a7 {! e# E
    % m; X( h/ [8 j& K  [
    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-3-18 17:59 , Processed in 0.063133 second(s), 21 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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