设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 3 z9 Z; _$ Q, |8 H1 e# E  l! [

    % ?" I4 S5 g) c* C% m& P$ W% y解释的不错
    6 p2 ]) `6 u6 i  Q# C3 J% m1 R" X/ n& Y5 I* S  x: [
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。) F% {. n$ X( o; f

    ) d/ o1 C  D+ ^1 f- m7 ?/ T5 j 关键要素
    ! k1 v5 l' J: u6 _4 o3 r1. **基线条件(Base Case)**9 z6 O8 y6 ~4 H
       - 递归终止的条件,防止无限循环
    # k7 O3 r0 o8 d6 j& u8 ~# |   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    + u' n( [9 |. l% \# o, y" ]$ v2 }; G7 |; x2 W
    2. **递归条件(Recursive Case)**
    : I, x) l( ^6 ]1 J; |" b( ^+ D   - 将原问题分解为更小的子问题1 j4 X; O- n: N" b2 U# P
       - 例如:n! = n × (n-1)!
    0 L8 Z. |# w; f; E2 H0 y2 p
    - L+ {8 `& {& j8 Z2 ]+ p6 ?0 Y 经典示例:计算阶乘
    5 ~9 X4 A% x. p# fpython/ l; m  V$ Q4 e) g2 [& k8 m+ Q
    def factorial(n):
    - p# N. Y& g; l+ M; o    if n == 0:        # 基线条件
    : M8 Y# e: b7 b" K) [& p6 C3 H8 S& Q        return 1
    . j1 N0 k& X2 k1 ]3 V    else:             # 递归条件/ \" c5 d& @/ w; P, o- l
            return n * factorial(n-1)  `# y* A1 u% j! E+ e
    执行过程(以计算 3! 为例):$ I  s; r1 o" r  H+ d) D/ T
    factorial(3)
    2 I' k& {* z8 a0 Y) c6 z) P3 * factorial(2)3 s8 l9 o7 W* {. Z) _, a  `
    3 * (2 * factorial(1))
      g$ \) m- s0 n% D* I9 ^/ a3 * (2 * (1 * factorial(0)))# C0 T4 o% d* F  @& m
    3 * (2 * (1 * 1)) = 61 X$ L2 N8 p, y

    8 U6 Q) P: e. i0 A2 U 递归思维要点1 c2 `2 P, H. _9 }
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑4 f- ~0 k+ J* C
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ( B* b' Y3 K+ R+ y" P3. **递推过程**:不断向下分解问题(递)
    " \6 \3 t. r' @) {4. **回溯过程**:组合子问题结果返回(归)
    , f" T) S6 F5 ]
    ! ]" R2 A: w. @* q% N3 [4 I& ~0 `% _ 注意事项
    ' J( G$ H) B" ]3 \0 A! f# w, L: i& p! R必须要有终止条件
    7 Q  Q/ C  a" e  Q0 S3 H递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ( t2 \, _! d9 ?% l# _7 w' A4 \6 q某些问题用递归更直观(如树遍历),但效率可能不如迭代
    : l0 f  {2 n8 l# i尾递归优化可以提升效率(但Python不支持)
    + y& l& t0 a& n$ H0 Y! ?
    9 b5 A( A+ V# U7 X! v; X/ i 递归 vs 迭代( t# J% y4 H# o) P0 ?
    |          | 递归                          | 迭代               |& j4 P% M1 ~7 E- O. ]+ @
    |----------|-----------------------------|------------------|
    3 G- }- ?4 L1 u/ m, C3 X| 实现方式    | 函数自调用                        | 循环结构            |# W. O! R$ C" S; A' R' W* D
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |! }9 V7 Y' h6 ?, u
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |4 k( ^  G) k6 J- o
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    & u" N& T" e' G. @* q: x% R2 R$ B1 f+ U7 a+ k* i
    经典递归应用场景
    ) L; h/ t/ Z7 h* h% g1. 文件系统遍历(目录树结构)- i0 b! u% @+ c1 N+ `! d
    2. 快速排序/归并排序算法) M! I! J3 h2 }# P4 A! i1 B9 @" M
    3. 汉诺塔问题1 Q, x& e4 w# X* d. x
    4. 二叉树遍历(前序/中序/后序)0 A9 R9 K; A3 ~# Y6 W3 t9 R$ T2 w
    5. 生成所有可能的组合(回溯算法)
    ; }& a9 q. ^( T6 l. F! p+ ?# \0 e2 Y' z3 A0 W& F! u
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 08:35
  • 签到天数: 3194 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    6 Q( ^; N3 d! D3 P我推理机的核心算法应该是二叉树遍历的变种。! r3 A& s# c( G
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    ' z, B' t& C3 ]! V' o0 WKey Idea of Recursion
    1 Q# P3 a3 Y* t9 W. @1 p
    % N0 ^9 `3 S! a  A; HA recursive function solves a problem by:$ ~) d; u  P' n* c/ e
    7 k, z1 J1 u6 K% \3 v& v# L
        Breaking the problem into smaller instances of the same problem.
    ' n. O2 j# w! ^
    " \5 E" a, X4 O' y- z    Solving the smallest instance directly (base case).
    & S" W/ \, N) v4 U, y+ \" W" b! Q9 R- M+ u
        Combining the results of smaller instances to solve the larger problem.
    1 V2 M' h; c& j  n0 r% @3 O; P
    - d# g/ m2 L4 @: p' S% HComponents of a Recursive Function* |5 W  N# v& U; y; ~" o) k/ T
      q4 T/ w( L! D1 Y* j4 b
        Base Case:
    4 U1 V6 n) o1 ~7 g2 t
    8 Z; T3 ?" x2 g        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.2 {) g5 n2 }9 X+ t$ j0 v
    3 m1 R. O' [, ]6 K. W& \6 f  e6 r* Q) F
            It acts as the stopping condition to prevent infinite recursion.+ j# F" q7 T6 g! d  n
    / a; m7 Z- n6 `$ F+ x1 A
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / W4 f. C+ t) W- K. g" z8 J- U$ I
    # C; B5 z$ ^. J; l" U( s; W- d6 `' c    Recursive Case:7 p' m8 C: S! m7 c3 k% H( R
    1 Q- w( X5 E  o9 i2 @9 a) d
            This is where the function calls itself with a smaller or simpler version of the problem.3 }: c) j( \* F
    - X) X. k* `5 S2 l  L/ K
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 x; l6 n/ ?/ X1 w( T& e* Z; b0 V3 r  g7 Q2 q
    Example: Factorial Calculation4 J8 O8 s5 |6 l' ?
    # C5 n& n. `7 @9 _* S5 b! f8 v  N
    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:
    6 l1 v) T/ o$ M- s0 S( c, w/ `, r6 `; o% E( k  B% B7 _
        Base case: 0! = 1
    # Q1 `# w3 L, W9 ~* G. H4 I8 @2 ]5 q4 T  t. z
        Recursive case: n! = n * (n-1)!% `' I" }4 e$ j3 a0 ?

    9 F( [$ n# j8 NHere’s how it looks in code (Python):/ W# ~1 B' y: r- Y8 s& g9 ?
    python
    . g% I7 Z! R- Z4 V; f, B! b
    # f1 a1 l3 Y, H0 H; o) q+ ]% P6 Y
    : @, ^9 H+ J) S; Gdef factorial(n):) o0 M. x% J9 z  o* q
        # Base case
    : s  E! h. s2 \* Y8 Z& S    if n == 0:: n: f1 \8 B( @" j/ U
            return 1. S% n3 n* X( J; Q
        # Recursive case/ B. U" j2 N) {& l+ j$ e- m7 ?2 x
        else:$ o: r" u& p5 s! w: k
            return n * factorial(n - 1)) U& \( R: C4 F. }( d

    # e' t$ R5 m# X: {. z+ K3 g" c! k; l# Example usage! c* y/ b; E  R# e/ U8 T9 }9 L
    print(factorial(5))  # Output: 1208 P1 ?4 o+ [  c' S0 R: h
    / B& c: z: J' a# {; `& T
    How Recursion Works
    - a: [0 x0 G7 J7 }1 A
    4 f& c; [, D! K6 Y    The function keeps calling itself with smaller inputs until it reaches the base case.4 {) \3 E2 u. a8 w  ^

    0 w7 Q/ M& _0 G, o. Z    Once the base case is reached, the function starts returning values back up the call stack.) _) Y2 I9 K4 _7 T% `+ S

    8 f, @  `3 o' |0 O5 z/ L    These returned values are combined to produce the final result.
    / `+ [+ r% A# o1 o8 t. ^+ j+ l% j2 V) r" n5 v7 Y3 |( j/ ~
    For factorial(5):. R( X0 q$ V! j: `( @4 E

    2 L! A' y4 K- g& Z& y$ c5 e: e  B/ c6 R# F. ^' }6 ]# ?
    factorial(5) = 5 * factorial(4)
    - B3 D+ W" Q& T, p9 U2 Vfactorial(4) = 4 * factorial(3)
    6 l4 x, K8 a5 ^. p+ ~7 k) Wfactorial(3) = 3 * factorial(2)+ {) B  Y( ^3 L  a; O
    factorial(2) = 2 * factorial(1)5 d1 Z0 g0 ^9 k3 n* D
    factorial(1) = 1 * factorial(0)
      I! p" p( ?& j+ e$ E0 cfactorial(0) = 1  # Base case% D: q! W, v- i; w6 Z3 u

    ' t) Q: a6 A+ I3 Z; h. I% Y( KThen, the results are combined:
    3 F/ K! T  V+ J" W( X/ `& u$ r* e9 `* B8 R( H5 U

    9 r9 Z( V: b  ?factorial(1) = 1 * 1 = 1
    9 M% H) t1 k+ J( Q. s+ N, Q% Ufactorial(2) = 2 * 1 = 2$ g7 H3 J8 Z/ Z( C
    factorial(3) = 3 * 2 = 6( |; e! P* \5 m
    factorial(4) = 4 * 6 = 24: s2 y1 h  ~! W" b$ B
    factorial(5) = 5 * 24 = 120. v/ P& g5 H. v4 _
    * P2 f' y& A5 r/ Y) d3 c8 R
    Advantages of Recursion& V/ J; O, b# Y3 _7 j5 g$ \
    + _# z" s9 L+ c/ ~2 h
        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).) O, m, U  L0 x# S8 ^

    0 t; s' T" f$ K    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    & z/ _9 N, V8 L; U' |* p; Y
    ' l; n- V  w: BDisadvantages of Recursion6 |/ ^; |9 a6 r

    + d1 I& }- u) a) k; N    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.# a+ h$ ?+ Q. M% t* w! e

    2 [6 z1 ^5 _- h    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    / S. G$ N7 @5 M6 V. G- E. H3 s0 S. x3 L( |' V1 a4 p; c
    When to Use Recursion
    % ]! a, n% m; {- H& s" r; A! T+ H/ _( V" @; ~
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    1 X; c& z$ L: D5 b% [( m4 H1 ]( ?$ n  l% ]" ?: u9 a6 j
        Problems with a clear base case and recursive case.( _$ c% ?9 T4 X
    3 A4 N6 [* W0 k3 m- x9 S0 G
    Example: Fibonacci Sequence
    ( {0 W0 d7 O' @6 N; t
    : {. O0 d+ X  L/ TThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:; G2 r6 }4 ?/ |! \

    & `. G; I: z9 I    Base case: fib(0) = 0, fib(1) = 17 r+ `3 W4 ^. C
    ) A5 D& G% ~; ?/ P9 X( q! K. }9 G
        Recursive case: fib(n) = fib(n-1) + fib(n-2)* `* a7 m0 P' J0 ^0 z& y" U
    7 a: V6 i" V4 x  C
    python
    0 X! M- G. U0 k* c. N: ]
    # s, c5 |' J: ?* |* k: L% Y" T9 S! P' o4 @8 G
    def fibonacci(n):2 ?( E9 t% f( X0 G
        # Base cases8 G4 n( K- T  B' y: N) v+ X
        if n == 0:% T4 Q, P# f1 x
            return 0/ e4 B  V- s' Q/ l# S
        elif n == 1:
    - B* \2 D* |8 Z& J% w        return 1
    1 A! C! \8 [+ i( N5 R8 n5 s    # Recursive case
    0 U( x- Y# E) _0 |    else:
    8 {9 k, f  m& H- _" ]7 g        return fibonacci(n - 1) + fibonacci(n - 2)
    1 ~9 R$ [; Y: o7 h( h" W; ^- }4 \( k' R2 |1 T
    # Example usage. j: S* x! H- ]5 R0 |% O3 E
    print(fibonacci(6))  # Output: 8! f7 o9 U( D  s4 u

    ; A1 z. r7 z5 s9 rTail Recursion" h! c) i* m  T$ D; o+ G
      R# L& g* ^# _/ y
    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).( N) q$ F8 y+ B
    8 ]# \5 l3 r4 [( Q( 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, 2026-3-8 06:56 , Processed in 0.063318 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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