设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    , _7 p, |/ Y, M2 @, d* `# g! c0 K
    % s" U; P2 t  k# c$ n) b3 k2 U$ Q解释的不错2 k6 ]2 B8 V) ?2 ]3 H
    $ D4 Z. ]- E6 Q* o/ Z( T2 U
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。3 l9 b4 L9 V. U5 s) A% t1 t' F. ^
    ) `  H6 x  }6 V* Q- o  I( X9 G3 L
    关键要素- w7 S$ {; L0 X/ p% X
    1. **基线条件(Base Case)**3 o/ @% Z  O$ F. X9 G; h
       - 递归终止的条件,防止无限循环, A/ f4 R/ ]$ ]5 A2 O' h
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    0 Z7 _+ `) d, f# ^8 u- y7 n$ |/ U' H% ?7 b+ B9 Y
    2. **递归条件(Recursive Case)**
    7 G( w+ Y  y" [5 H/ M9 J   - 将原问题分解为更小的子问题9 _; [2 \5 b$ A. }
       - 例如:n! = n × (n-1)!, D6 T! ]" r: @
    2 Y' k  Y$ v( i, J5 s6 o6 ^: O: t' \
    经典示例:计算阶乘& i7 _1 O# I  E; D! V
    python9 J8 I- W7 E) S
    def factorial(n):7 X4 F6 i* C' ]
        if n == 0:        # 基线条件
    4 p/ u+ ^/ D0 T        return 1
    " R* e! V# w: S6 F    else:             # 递归条件
    * r6 A% r& r3 B# x        return n * factorial(n-1)
      O4 F6 g  q8 |执行过程(以计算 3! 为例):" \5 g4 h4 [; _7 N3 o
    factorial(3)
    : o9 Q! T5 m9 i0 `9 e5 D3 * factorial(2)
    - U$ K, @1 n, b3 * (2 * factorial(1))3 r3 R( J" ?6 V1 |& `
    3 * (2 * (1 * factorial(0)))
    2 c* l# _; q0 Y2 ~8 V/ q3 * (2 * (1 * 1)) = 66 M( W, R& Z2 b3 D1 h9 w0 B

    ( G! }( h3 v" H 递归思维要点
    % g! D% K3 m" o, k6 {) o1. **信任递归**:假设子问题已经解决,专注当前层逻辑( s% O3 [8 |3 L8 t
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    - w6 U8 d: A1 {* K3. **递推过程**:不断向下分解问题(递)4 a8 R6 s! d( S- b+ o& d: P
    4. **回溯过程**:组合子问题结果返回(归); s8 L( W" ^; T# `$ [, ~
    & U0 ~; F% C7 [" ~8 X( P! i2 u! B
    注意事项
    0 B6 Y3 c# Z2 T! P) [! K8 R. {2 q/ K必须要有终止条件
    . q4 v) E9 y. q: g递归深度过大可能导致栈溢出(Python默认递归深度约1000层)) H2 |/ H" T2 M4 [* Y  {; W' x
    某些问题用递归更直观(如树遍历),但效率可能不如迭代" j( D3 f! s7 U/ K( u$ h% Z
    尾递归优化可以提升效率(但Python不支持)  V3 t  _$ q/ u
    - n3 Z2 v' O  \( b
    递归 vs 迭代
    9 z( u# K8 x. S+ O" }6 c& x, l|          | 递归                          | 迭代               |
    : s. A; d1 B, S- I( z|----------|-----------------------------|------------------|
    9 U3 D& \) Z" Z/ U  n" F| 实现方式    | 函数自调用                        | 循环结构            |
    % J, M+ n6 |( k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
      ]4 F, M$ @4 t: o+ b* ?# i8 g| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |( V4 o, U, e2 c
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    6 @! f5 w% M& L  E  ]& j3 m2 E# u/ z$ ~$ d& C4 p* P
    经典递归应用场景4 I8 @8 v" N/ T0 G! v( T) r
    1. 文件系统遍历(目录树结构)
    1 c6 U8 o0 c) U+ _2. 快速排序/归并排序算法
    9 l" ?- @" q0 ^, Q6 q3. 汉诺塔问题" v6 e. O5 z3 U6 \. D" P: ~! n
    4. 二叉树遍历(前序/中序/后序); `5 d3 w0 G' o& A$ f$ }$ w( @' v
    5. 生成所有可能的组合(回溯算法)2 G7 e5 p, t0 R+ C% g! K5 [  s
    4 b) C6 x! o/ B9 U% Z5 K! k$ c9 f  y/ g
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ! U# p( k2 I$ f  Q$ x, c' c我推理机的核心算法应该是二叉树遍历的变种。
    : V1 U( D0 v7 T0 q+ W0 Q6 c& v* F另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    . C  ?+ o; a! {5 l! p: z$ N( MKey Idea of Recursion
    . M* R4 l/ V8 K& a2 @  O  W
    0 E& O. |3 m. }A recursive function solves a problem by:3 A& Z" A7 c0 N$ S
    : T6 Y0 v* G9 U2 `& T3 Y# x9 c
        Breaking the problem into smaller instances of the same problem.
    ) C: p9 L( _" a4 S; I8 R6 V! c/ W( }( b
        Solving the smallest instance directly (base case).# o/ t- V: R' w" e
    - p9 }" U/ [. @4 v) u
        Combining the results of smaller instances to solve the larger problem.5 V4 o5 A* d' D, \1 H' v6 H

    6 v6 D7 r8 y6 c3 [2 TComponents of a Recursive Function
    0 E6 k2 h0 f' J1 B& C, E; L7 X3 Z; r2 D% k8 n6 S
        Base Case:/ i: J, t) q$ q7 T2 J0 _% v
    2 S) C1 x9 f: G+ g# T& u% V7 M
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    8 r  `9 Z! S, f& z4 Y
    ! Q' }/ h" J" d- l" m6 j9 U# w        It acts as the stopping condition to prevent infinite recursion.
    3 T, k. V3 s, @. `6 \: n/ y' [1 `; C7 @9 I3 H3 T+ h5 w8 w
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / X. {) X& P* U4 L# |
    ' l* H) C) w$ u& h7 L8 q- L    Recursive Case:
    % r% G& Y( N. _& _* Y9 v
      F$ Z5 o7 k) C        This is where the function calls itself with a smaller or simpler version of the problem.5 J0 J2 ]8 X; @

    . |7 a8 R6 N2 k8 T4 y        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).0 S8 q  b/ p; n, ]/ r/ E/ i* j$ o

    " b( m. s9 R* L; qExample: Factorial Calculation( N" @  j; c/ ~8 l' o
    8 t' e, O6 s  D- ]
    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:; n- W+ k3 [, g5 x8 y  L
    4 @. b# e7 I! c9 o$ g8 P; Z
        Base case: 0! = 10 ]2 K0 [: r& C4 j4 X
    2 J. W. b! V& q* [2 q
        Recursive case: n! = n * (n-1)!
    # d, ~# C3 s' `
    9 {! f5 b1 a, s, lHere’s how it looks in code (Python):9 D& m6 `2 Z9 x8 K) \
    python/ Y4 o' S' U4 A" F$ Q- ]
    $ ?( s- y& S7 L( X. Y7 P" p

    4 U2 R8 Q& [- L) ]4 Q, P' xdef factorial(n):; }+ f$ s! K+ t) O  H
        # Base case( }# k& n% s' ?
        if n == 0:& q8 u& }1 Q- K
            return 12 I* u- w, [- [- b( |
        # Recursive case
    ; i8 S6 V' p2 }/ p0 v& M7 l    else:* K0 j5 a  b$ n' S. C7 c
            return n * factorial(n - 1)
    & W. A9 k2 E7 C. L! Z$ [" M8 ^6 x3 H* d6 z$ c
    # Example usage" O: F9 V6 e7 _- L7 K
    print(factorial(5))  # Output: 120
    6 [0 D. V8 T7 b8 T) ~4 A( O1 p+ X' p: z; Q
    How Recursion Works
    0 p$ O( p! n0 s6 x& T+ O4 e' R9 ^! t2 P. h1 n: X
        The function keeps calling itself with smaller inputs until it reaches the base case.
    " S# `  ~6 q- ?) \6 f. A* K7 p' |1 t
        Once the base case is reached, the function starts returning values back up the call stack.  b8 C4 A/ F$ [5 V1 N% Y2 @; z; f. @
    7 C$ Q8 m6 D( n% m+ Y
        These returned values are combined to produce the final result./ t) m9 H) K; i+ O
    6 U% p; ~4 D4 Y) S2 m
    For factorial(5):" ~2 @, J6 c$ g8 ], p# a

    9 M. e! ?9 }( p5 e0 s. X& _* H
    3 C/ u6 K& G: Hfactorial(5) = 5 * factorial(4)% l6 W) l# n, \% v% D3 ~) B) H& v
    factorial(4) = 4 * factorial(3)
    2 J1 P" }; |6 Y3 G, q/ e' Y' kfactorial(3) = 3 * factorial(2)
    0 P' K' ]( o6 e$ Q. V7 jfactorial(2) = 2 * factorial(1)
    . E5 @" a* K( {/ L- ]9 W6 efactorial(1) = 1 * factorial(0)
    + G- x# M$ j' Z- z; afactorial(0) = 1  # Base case2 k, }$ k# @; H4 b5 c* c1 E2 r5 e5 L
      j9 e7 r# X+ H) h# _. e/ S
    Then, the results are combined:
    3 o4 L& G1 X: c8 @) ~- s+ d, H) O. v; A/ h& v

    . l- Z4 c7 w' j7 V8 d2 qfactorial(1) = 1 * 1 = 1
    . q  N5 q& g& Q3 ~) ffactorial(2) = 2 * 1 = 2# P) u( Q8 L3 W* `) K7 `
    factorial(3) = 3 * 2 = 6
    . n4 w/ f' H6 ^factorial(4) = 4 * 6 = 248 p; k5 u) ?. b: }; F4 q- m
    factorial(5) = 5 * 24 = 120
    - n& Q2 m6 R6 g( F6 n( Q  m1 R# }7 I7 ?  O  r' `- e
    Advantages of Recursion
    - a. F$ j  j4 N' a: O
    1 e7 p/ D) x1 Z' k( f    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).9 W; N3 v/ p4 W) v8 g3 e) Z

    # {6 y* J5 d, c6 i" X1 s7 d    Readability: Recursive code can be more readable and concise compared to iterative solutions.8 Y( [7 b1 `  @9 a/ p# I, ~
    " u% e# o: m8 c+ k( @* Z
    Disadvantages of Recursion
    ; n8 t  u) A* k, B( U  {
    * }& z9 r2 I+ w6 q    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./ x9 A6 C! M" o% I+ w

    5 ~6 f$ D- j) o4 C7 h1 d- r  n    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).+ ?, C4 P2 Q, N
    % N* \- [) U- b: f/ k4 @! |
    When to Use Recursion) _& R# X5 H3 ~3 ?
    , E% p, {0 D5 r, c! ?" C. a
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ) v7 j# ]% _4 n4 O8 k( x4 {. ~; o; y6 o' j. m
        Problems with a clear base case and recursive case.; U* a6 F' N3 H# c2 E- Y  y# Z

    & ~. z( U" a- R$ ?2 X; EExample: Fibonacci Sequence' Z2 ^& e0 T  E$ K- ^

    - u- q- F( q4 P! MThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    5 B5 f0 h, W; H5 B0 P1 f; H
    ! O8 U* C% a$ r) j# K' M    Base case: fib(0) = 0, fib(1) = 1) T! x$ q5 S  @( F0 w2 k5 I8 l

    6 \; K7 q9 |' w4 J2 w& n/ ^    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    6 M! r3 ]# w) C- C+ Q
    / W: }3 u8 Q* m' ^  Wpython
    " @$ T% j1 H  ~. A
    & |2 _) D3 w4 W- J* i+ L' X6 u: ?. S6 R1 t; S. H) W( F0 i
    def fibonacci(n):' n# l" |. @% @1 x8 A
        # Base cases
    4 i8 u( ~" i$ |$ _4 m; d    if n == 0:
    & h2 C5 o5 n9 t" M( g# K        return 07 S. o: U2 q. P3 J0 j, Q8 }
        elif n == 1:# I9 U' y0 {+ M5 R* O! ?
            return 1
      r2 t6 a8 A4 E. S2 ~, d    # Recursive case9 C- Y. P3 E, G  O; R
        else:
    ( R) j. p4 A6 j$ n' C0 D        return fibonacci(n - 1) + fibonacci(n - 2)* y9 i) Y) w  }8 ~5 b% c1 [2 I) C

    5 ]$ O# c; e8 L$ d5 U# Example usage
    : m1 W; z) R% [; jprint(fibonacci(6))  # Output: 8
    0 n. j5 P: D+ w0 F) m7 S2 [% R* ]9 Q! v$ @" U/ s  H
    Tail Recursion* s4 b* {: V. a3 D0 E' b

      a; t( z8 y- yTail 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).
    % C6 G4 G: k6 G- c. E7 C
    + I5 R  M6 ^8 D- QIn 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-1-13 12:44 , Processed in 0.029303 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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