设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 0 E8 y" Y" n8 @. N0 I6 I2 z

    ! c  {: k9 h. y$ v解释的不错2 r5 q2 ^/ R# ~8 g

    ! g+ q: Z* |$ B0 F, C递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。5 h6 w" L4 x4 u+ Q& K6 }
    8 |7 y: Y' ]8 i) s/ j' l4 n
    关键要素( r2 N* R" z6 K
    1. **基线条件(Base Case)**
    . j0 }& j8 C/ a2 ~3 _$ c   - 递归终止的条件,防止无限循环
    1 p6 f1 j" r1 f1 }   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1' H1 G2 r1 W2 L
    7 b0 t- G$ s) s2 W2 k# j* B" k
    2. **递归条件(Recursive Case)**
    9 H1 v' h* r; {0 ~   - 将原问题分解为更小的子问题9 m- l! n  V7 a( O. @5 h! g0 ~
       - 例如:n! = n × (n-1)!
    ! m0 N" q3 z. h. z6 j# o1 z# J" x! y( R( H& S& T5 `
    经典示例:计算阶乘
      W. ^$ u7 ?8 w  @" v4 qpython3 K5 L7 o0 j  h$ ]" f* |$ R* I8 H2 {* Z
    def factorial(n):
    # |  }8 ^  z- w6 `9 e2 u, I    if n == 0:        # 基线条件, u1 ?" T# ]5 a. ~
            return 1
    0 R  t, j' ~, I5 Q. ~7 R7 F    else:             # 递归条件
    2 O" y) j: W! Q& z" D        return n * factorial(n-1)0 r, N7 f+ Y& o# w$ j8 `" Z3 `9 U
    执行过程(以计算 3! 为例):% r1 Q8 Q  S- [9 t& I
    factorial(3)1 A+ @; r' d8 Z, O
    3 * factorial(2)
    $ Q/ K5 s) ?" a3 * (2 * factorial(1))
    . _5 y. S0 C) Q) a9 n3 * (2 * (1 * factorial(0)))
    , {1 F+ a6 C7 }, D* J- X3 * (2 * (1 * 1)) = 6
    3 j& X2 d* L0 J) s+ _2 q, s9 b: P! e$ I
    递归思维要点
    2 r) H0 X$ u! M- }6 v3 ]+ o1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    * f+ L4 w; h$ S% q3 f: g8 H2. **栈结构**:每次调用都会创建新的栈帧(内存空间)' q. N. u/ G* Q# _3 C  M, N
    3. **递推过程**:不断向下分解问题(递)
    : A3 v$ f: t- b3 k; C7 O, B2 b4. **回溯过程**:组合子问题结果返回(归)% I7 a. B7 f. l9 v6 R
      ^/ Q) }( B% Q, U+ D' W* X* _+ ]: G3 w
    注意事项. q3 Z4 p8 M$ f" f7 k
    必须要有终止条件2 R7 z% j8 W) w- T
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)% N/ @& X, Y" g
    某些问题用递归更直观(如树遍历),但效率可能不如迭代; Z. U9 C) l" x; M0 {( q  A
    尾递归优化可以提升效率(但Python不支持)
    , p+ l5 F4 b7 b  w9 {. l4 m. u
    " \' b) E( z: C( X$ Q: _7 Z 递归 vs 迭代
    $ u* k7 i: m3 s+ Z0 m+ j! S|          | 递归                          | 迭代               |
    ; P( K. u* {* A7 j9 y0 A' F|----------|-----------------------------|------------------|
    4 y( @" r" }. w| 实现方式    | 函数自调用                        | 循环结构            |
    5 x. }/ K# i  y" Z/ m. g% h: y% P/ v4 f| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 s- b0 F" J9 q) R6 U
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    * K6 M& b; X& C# f4 e3 Q+ G8 Q| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    # s# `3 A& i8 F4 l8 O% p5 s' k4 G- l% i, _
    经典递归应用场景
    + I! ^: h8 j! H  K& q+ D+ |8 ^- r' h1. 文件系统遍历(目录树结构): b/ H7 }) b$ e" Z8 K
    2. 快速排序/归并排序算法
    ! F+ M7 G1 X  d5 P# d" p- O+ F: s3. 汉诺塔问题
    : s% e/ n/ [$ j/ F3 O6 _4. 二叉树遍历(前序/中序/后序)6 H- }3 n3 }+ `$ X- q# k
    5. 生成所有可能的组合(回溯算法)
    7 g' f0 \9 m7 ^0 g/ C6 d+ Z7 Q9 i
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    3 天前
  • 签到天数: 3217 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    : c5 F$ \: Y+ m6 w! i7 x0 k, F我推理机的核心算法应该是二叉树遍历的变种。2 b5 ^, z4 r/ s$ }; ~3 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:
    ( R% U" x% V5 o/ HKey Idea of Recursion" b) D' `3 Y8 u
    : l, w( G6 }  @2 P/ t1 D
    A recursive function solves a problem by:
    , {7 K  X8 R: ^2 ^1 }; @. l. I
    + ~0 F! ~9 n* j$ y, }' s: Q    Breaking the problem into smaller instances of the same problem.0 T" Q0 |5 n8 J$ @' h, t, ^

    6 i' G$ r' r- b    Solving the smallest instance directly (base case).
    3 t7 O" V" U5 J4 l, `4 ^4 r; I! b0 n. W" d9 _5 ~3 a; h0 c
        Combining the results of smaller instances to solve the larger problem.( |5 z, G( a* i: F$ h2 Q

    & T7 o& N6 V& J# C# L# u0 c4 FComponents of a Recursive Function2 Z& T; _1 G( _5 T: h% M( H+ J
    # g6 `  F1 o% B* ^+ f+ b9 K/ y. @3 j
        Base Case:: |1 ~. K$ e7 \+ S$ M

    - n: t" g$ n4 @0 J! x4 j: `        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    / b4 A) w6 ], q) Z4 u3 A
    . R* S. H7 M# x% S        It acts as the stopping condition to prevent infinite recursion.
    6 q5 X( x0 g4 z
    % a" i! ^9 y& c2 e: B: O! f* m        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    " |! U* D0 t6 B0 t* `3 r2 Q- F2 T' V* n
        Recursive Case:1 @$ x& B# b* o& Y' V
      l. E7 ]  Z5 g2 z3 H' {; x5 X: m5 D
            This is where the function calls itself with a smaller or simpler version of the problem.
    + q; v, G2 g4 m: z& Y* o3 K1 f* l1 R+ i% d+ G6 P& W6 I4 X
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    / m1 Z6 ?7 c) D6 N& P: `$ b6 G! @+ @: o4 m0 N3 h
    Example: Factorial Calculation
    & j. _; Z' x" p+ p+ I
    + a- Q, K$ o' e8 ^# R; YThe 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:7 e# B% W, i7 y! t4 J  ?

    + w" C( ?0 o' W* U9 ~    Base case: 0! = 1
    9 l  V3 i$ e8 B! e) N, Q0 c6 \, _) @0 @8 i9 f3 f. E
        Recursive case: n! = n * (n-1)!8 D: [' `8 f) y& S5 ~4 C1 H

    ( `- p' v& g7 E: m- e# ZHere’s how it looks in code (Python):
    - h0 C8 g; x* n3 p! |$ q9 r% Epython
    * I  h0 t$ C8 r/ l7 M, E- ]' |0 ~! ?0 U7 e# b! ]$ ]) `

    ) p/ n" i( T' ~2 T- Ldef factorial(n):
    4 ]. h) s$ Y5 Z- L& v; Y( g7 J1 Z    # Base case: L& r- Q( b: q0 _
        if n == 0:
    , ]: {$ t3 ?1 [+ P$ n/ b0 s% Q        return 1
    ' D$ b& d5 @3 ]0 p9 ]7 O, K    # Recursive case
    . p9 A" i/ I4 h/ \    else:
    ! a* ~0 h+ Q& ?6 D% k        return n * factorial(n - 1)
    . h! D" B4 s% G8 _+ @9 M9 t( Z! T
    # Example usage
    : s4 y. M" o* o% g% `9 B; zprint(factorial(5))  # Output: 1204 d5 P6 B* I$ x2 s! l6 \

    * ]0 h' E" F& A# E0 [- b4 h9 i2 kHow Recursion Works
    # R/ j$ z& \% y2 n1 ]$ T3 V$ B
        The function keeps calling itself with smaller inputs until it reaches the base case.
    6 N, H2 z( p0 \" v. S* Y) W) x' |* `( R- I/ T' K5 D2 ~
        Once the base case is reached, the function starts returning values back up the call stack.5 w  o$ A5 V1 c7 z5 b6 L  M0 X% {

    / Q# H7 c; `. m# D1 h! R    These returned values are combined to produce the final result.
    4 S& o5 F5 H' z5 r% G% c4 N8 q
    % d+ O: ^7 A# H7 z0 Z3 {& J4 hFor factorial(5):3 a% |0 K" P; u
    " K; s+ O" X% v' Z' ^* N2 I1 ?0 v6 T9 Y
    6 U/ q- g: w, N5 ]8 y
    factorial(5) = 5 * factorial(4): D& Q- D+ F8 }6 g9 L" T  V
    factorial(4) = 4 * factorial(3)
    7 P  C% K; D) u9 ~8 T! U5 K& y( x: Afactorial(3) = 3 * factorial(2)8 w/ ~% Z4 Q/ g  v/ x
    factorial(2) = 2 * factorial(1)
    7 T- M. g( v! ?factorial(1) = 1 * factorial(0)8 ~) \3 {& A, b. O& T. d" s7 i. D/ ~
    factorial(0) = 1  # Base case* f4 b4 w1 d( z5 a4 J2 ^3 S
    * H% q* Y+ i* W4 u; g2 U
    Then, the results are combined:: [8 K4 H9 G% v  w, @. Q
    # a# [9 ~( j( [  l# k9 i* b

    : x8 t' s4 L+ Z# _% r  K7 N. }- Yfactorial(1) = 1 * 1 = 1% y( o+ N- k/ Z' ?
    factorial(2) = 2 * 1 = 27 g% F5 I. E( x7 }
    factorial(3) = 3 * 2 = 6: q, {2 _  Q, d7 q* Z
    factorial(4) = 4 * 6 = 24
    ( L4 S4 m" V# G. ifactorial(5) = 5 * 24 = 120
    / J' b( M4 m9 L2 _) ~$ Q1 E% H  Q2 ?1 g
    Advantages of Recursion
    , ^8 \5 U/ r2 X8 _: H9 P( v. h! I- a; W- E6 s9 p, b
        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).! Q+ y+ A( E( N# B
    * h2 {+ ]: C- `1 C1 V, G2 L- ~* ~( O* G
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    2 Z! m; m$ P  ^0 N3 X& D1 a: {
    4 Z4 a0 c; |0 {# }: ^$ O: nDisadvantages of Recursion- o  _; i, F/ S$ s5 I9 z7 Z3 ?
    * p7 N9 y, v$ V2 v
        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.
    ( J5 V. o, q9 ~) O, B) r4 T& y* L4 v5 K
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    4 W0 g1 ?! z" B# H! ^2 W3 B+ v' Q! I, I# h( V! x
    When to Use Recursion5 \7 I. g8 B) ?2 ~  O. V
    ) X& Y; |3 p0 s: n7 V2 _- A+ t
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ; s3 o4 b$ U% |- @( E: U% J- }& F" Q  d: X8 \
        Problems with a clear base case and recursive case.& V! C  v/ Q" D6 F6 s6 D
    . ^2 g! C$ Q: Y: e7 h, `% e, k8 S
    Example: Fibonacci Sequence
    6 C. [; f8 E, @; r! F1 z
      w1 W4 t/ f5 W# d: v. eThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:0 N, `- H( N' `8 M& ~
    , |1 R3 z$ A5 u% D' v7 l5 Q
        Base case: fib(0) = 0, fib(1) = 18 Y: V& P% x. L; K  L

    6 B1 C. G4 Z8 M" Z6 w9 s& v    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    " k! l; |1 k* ?
    $ J5 J. S. |2 g% c: ~1 O: _python
    4 Q# K7 c7 I7 U" |) U
    - m1 a9 z+ N4 J6 ~- {5 d% r
    ( T7 a+ j$ E$ N( U+ ]def fibonacci(n):
    1 N0 T& K: h1 r  G: E3 M    # Base cases% s- A; k, d: k
        if n == 0:
    ( g4 q0 V( p! ]: `  _        return 0- `; `' E! C0 ~" U2 v+ k) S1 n
        elif n == 1:. c: h: j! k2 c
            return 1
    . d! D: v% K- v3 N; k! B    # Recursive case" R1 J* o& ]: i, W' }
        else:) q$ E0 }* y' Z5 Z& m1 @7 M
            return fibonacci(n - 1) + fibonacci(n - 2)+ w( Z. K- h1 W& z# W" ]( d5 i8 f

    $ e/ Z! b* C" Q  z) g8 j# Example usage) Z, N2 v/ Z8 \1 Q- N
    print(fibonacci(6))  # Output: 8
    $ e# I% h3 ~9 T' v8 X$ V0 o# p8 F' A( @8 V' U( _* f/ C! s- \
    Tail Recursion
    + _0 T0 Z( x: X% o' m2 j7 n
    ; ^5 n  F! i6 W, f- m+ U; x  m; hTail 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).
      G( T' ?5 y$ S9 o
    7 R$ z, V, ~' u' WIn 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-4-12 17:19 , Processed in 0.056769 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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