设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 , N1 T4 i/ v7 _" ^4 |  q

    6 g5 z& r1 U7 C- r1 E" \  Y解释的不错
    ( p0 v$ p% o1 S
    $ i" ^& `$ v* t1 }( Y+ v' i: U# h递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    # @) Y1 S1 Y4 M) X" T4 w  N/ f' t1 P% B7 W# L/ S9 H' u5 l( C" I; _
    关键要素( |  l% Y& k6 a, c3 m6 `9 y
    1. **基线条件(Base Case)**3 {7 S7 B6 H. U" K9 F  n
       - 递归终止的条件,防止无限循环
    % G0 F( `8 `1 ^: R1 R; Y. {   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 14 U* o6 D4 J' F8 s( G
    # Q; a) u# h4 m6 |- B' O
    2. **递归条件(Recursive Case)**
    $ d( L5 [& h/ h- J& ?6 l5 e! w   - 将原问题分解为更小的子问题
    & a; ]! n+ k  y; \   - 例如:n! = n × (n-1)!4 }# _0 A: q( ?3 Z9 \' S
    ; D8 n5 Q, e$ A! ]% x2 P
    经典示例:计算阶乘/ c4 ?! a# m: ?; c$ s
    python
    / p3 w' {0 ^2 i# Zdef factorial(n):1 _2 E# P8 u, D9 i& a
        if n == 0:        # 基线条件
    4 D( w0 L4 {1 }3 X6 U        return 1
    6 {8 ?8 ~1 ?, H9 I3 E5 q0 I8 j$ p& p    else:             # 递归条件
      F4 z1 Q+ E( G: I7 p* l* o        return n * factorial(n-1)7 |- E# d, w& c
    执行过程(以计算 3! 为例):
    4 `$ p$ g6 f  Z, `' r  ofactorial(3)! e* A/ o% m2 C8 j; q: o
    3 * factorial(2)
    ) _' M+ n" U/ x6 c" Z$ D3 * (2 * factorial(1))) c- T# M: ?" P
    3 * (2 * (1 * factorial(0)))
    3 l, M" ~' U. o/ ~& f3 * (2 * (1 * 1)) = 6
    5 l9 V' h! V$ O* p4 J
    1 Q) c' s3 R: `* @ 递归思维要点, p, \: t2 _0 f: K# R1 @
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑' U, t9 c2 @* u  [
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    0 ~' P& ?  Z6 A6 a, g, G3. **递推过程**:不断向下分解问题(递)" w4 U1 U9 c" t6 W8 _4 ~
    4. **回溯过程**:组合子问题结果返回(归)% ]* G$ f0 P5 l
    3 D1 s! ~7 e0 t' u5 o$ x/ T
    注意事项$ o5 d' L. U- N# n5 z9 C1 Q
    必须要有终止条件4 l' k; M; n8 }* U( j
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ) g  s7 W2 N, r: U某些问题用递归更直观(如树遍历),但效率可能不如迭代
    1 z9 ~: I+ X- Z- f, a1 X尾递归优化可以提升效率(但Python不支持)
    , _7 V$ r8 \# b- U1 [, W$ s" S- H6 {1 Q$ @5 ^; {7 ?- B
    递归 vs 迭代' P9 w! h& ^9 f+ z, g  z% A8 m
    |          | 递归                          | 迭代               |  Z' S, h" `6 g8 I6 N. E" U! w
    |----------|-----------------------------|------------------|- b+ M# _' D9 b/ E, J
    | 实现方式    | 函数自调用                        | 循环结构            |
    " Q! k+ ^  D; J: L1 y| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |! Q' a( _1 _3 q3 T2 x
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    3 Y4 Z5 s9 i1 M; A% f" L0 |5 h| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |9 F" `; _  o/ z# ~1 {: x: s

    , j7 X: w+ M# p 经典递归应用场景) j$ V4 ~+ j! K( o4 f( n0 Y1 l& n
    1. 文件系统遍历(目录树结构)
    ! B% t9 ~; P" p$ @7 ?2. 快速排序/归并排序算法; n* v* n: |8 b' S" i% M
    3. 汉诺塔问题. k/ n. C. W9 v
    4. 二叉树遍历(前序/中序/后序)
    9 f; E/ p! I1 l2 K$ O- b7 a5. 生成所有可能的组合(回溯算法)# h8 T' X' H1 e* T

    7 n8 T. _6 m% U试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    昨天 08:50
  • 签到天数: 3109 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,6 ~. @8 M, i$ x0 ]7 U+ `0 C
    我推理机的核心算法应该是二叉树遍历的变种。
    ( K8 m8 f: Q4 P( @& b另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:: m7 H: w! l+ s! \* r
    Key Idea of Recursion2 G7 A# f3 v4 m( m1 x. Y+ u

    " p: \5 c& ^% {" j  _A recursive function solves a problem by:# W; `$ R+ x! @
    " H0 `+ o' c5 O# a' V- c: ~& j
        Breaking the problem into smaller instances of the same problem./ m; U4 X( i# m
    ) V- G5 K( {, B9 R( @  ^/ h) X
        Solving the smallest instance directly (base case).
    1 V! K4 q+ d, d
    % x5 }" Z: r, G2 ?; M7 ]& A; j    Combining the results of smaller instances to solve the larger problem.
    : p  {& |  d0 Q  W1 i7 J( o7 E& y& b
    Components of a Recursive Function, J. V4 J2 c% d- @* `- Y

    % H" z0 [' H7 x+ z    Base Case:
    0 c' f$ C6 }2 Y# Z' ~/ @% t2 M; @' @! u- j$ U; ^
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.. |+ G6 ~& M: q# j
    , O% _& _; |3 t" Z' G0 @% K/ y
            It acts as the stopping condition to prevent infinite recursion.
    0 \9 v! ^* `/ Y: |6 y* S3 f" e6 N6 i( b  _0 w; ?
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    3 c! @+ q  K$ ~/ Z3 g9 S5 L: \1 r% J6 r
        Recursive Case:; L3 a8 a7 g1 D
    " Z0 O! L3 P- Y5 ]! E- r! P
            This is where the function calls itself with a smaller or simpler version of the problem.
    " Z; z7 a- f# F; t$ [
    5 L( D0 n' w* a8 L3 X6 [        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ( T1 n  x) w) j5 R8 f4 G0 M( Y
    2 R* D& X3 A# c0 V0 t; `% X  RExample: Factorial Calculation
    ; I1 D6 z2 n" D
    , c' g. A2 `3 d* F& Q/ O, qThe 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:9 C3 b) \% y. ^: b% v

    : C$ `2 i' Z9 Y0 q; ~* m  H' T) `    Base case: 0! = 17 j7 k; }8 h% i' F% I

    3 D* c2 r: X0 |* L    Recursive case: n! = n * (n-1)!3 l0 ], j9 P& e8 s% G! U

    7 [$ N, V$ E" Y: X* ?, {- O- LHere’s how it looks in code (Python):
    ) X5 [/ `. y" u& ?0 rpython
    8 [, ]+ y5 i  _5 @* [0 y( S' K6 m9 p9 `
    1 ^/ {2 V, ?+ O! w. u! G
    def factorial(n):
    8 \; h' l" G: B3 P& ~7 k0 M    # Base case
    , u  r% N, ]  g, r+ }9 M2 f) @, ?    if n == 0:
    5 V; s: o7 q. Z$ ~        return 1
    8 l! |! z" W: l( _1 Y2 H- Y    # Recursive case9 F% T% ~9 ], U; B& h
        else:
    & |5 @, A+ W5 B* U1 F; J        return n * factorial(n - 1): M, p- [. \; w1 h

    6 q" q$ M: k) V* {3 @# Example usage5 V) q1 b' h, j, r. E$ |
    print(factorial(5))  # Output: 120$ C) ^! o6 b" j6 `# A( o  h
    - L% i8 H/ z. `1 a! ^6 d
    How Recursion Works
    & b3 J3 m* d% o. N% G! I
    ) T. l& Y( {: o. v. c+ u. `3 @% a    The function keeps calling itself with smaller inputs until it reaches the base case.
    3 Y9 U! T# t) Y  x* L: x+ j9 H; B( N7 F" Z' ?
        Once the base case is reached, the function starts returning values back up the call stack.
    2 P* g3 E/ ~: _% H2 Q* w( A. i0 p5 X+ d  |
        These returned values are combined to produce the final result.+ Z6 C( f. w1 ]( F9 C" W% A2 [  i+ {
    3 E, L) K! c2 U/ c" {% m. \
    For factorial(5):4 I  s* h. [; b" ~" f
    ( O" X! R* r% n' X. j2 }; ?& \, w
    & H# Z2 L5 K( S# B& c' W
    factorial(5) = 5 * factorial(4)8 l0 K9 e( R9 d+ S% r' X
    factorial(4) = 4 * factorial(3)  ~+ ?; c! i% M5 K
    factorial(3) = 3 * factorial(2)8 X9 a" T* N6 X+ v( [
    factorial(2) = 2 * factorial(1)6 E8 E* ?% A$ D! u# a( N
    factorial(1) = 1 * factorial(0)
    3 R& l4 R) T, H- Kfactorial(0) = 1  # Base case
    8 z/ r) ^9 g( m9 m7 a9 [- B9 U
    ' o5 t) Z; p9 m( f( b( |& ?Then, the results are combined:6 g% z5 U3 I% K) r# C1 K7 L( t

    ; r* I9 L, B, R& C3 @) l
    + @9 `  m0 k$ Q" V& P& G" D6 gfactorial(1) = 1 * 1 = 1' X7 E, ?7 F2 ^" g+ L) Y$ e' O: k. ]
    factorial(2) = 2 * 1 = 2
    4 Y( S" \0 |/ {% }factorial(3) = 3 * 2 = 6; x* j: s" f* ~- o4 }- |# D$ |
    factorial(4) = 4 * 6 = 24
    / T# d6 n* \+ y3 Jfactorial(5) = 5 * 24 = 120
    ; [9 I8 O: T7 w$ }" G8 E% ]6 }* a" l6 Y) v+ @
    Advantages of Recursion; ]# d0 y0 f9 k6 z5 O+ G0 o
    ) F0 x$ m' ~  Y9 s) o  X( w
        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)./ h! Y/ S5 n0 |

    7 _1 b4 I$ |& R7 g    Readability: Recursive code can be more readable and concise compared to iterative solutions.* E- ]9 E9 U7 n, T

    6 i4 X1 U: h0 H6 o/ u$ e- ^2 dDisadvantages of Recursion
    * w7 ^; Y: ~  ~9 c. ^" K0 S5 c# {' H1 W) `% u+ t0 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." j4 Z, s! Z3 P# q6 q6 o3 B' T7 i
    , P  v5 V. [' d6 Z4 @# Q! R1 w
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ( `9 H- E* @& z/ j$ c* g
    . `4 L1 N. A& ^- y0 `When to Use Recursion
    / C' o6 A3 V6 D  e0 z- i6 [( B/ O* g  t1 l7 T, }" N
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).; u2 H9 ^. ~) G$ i5 t- R
    8 @( ?6 c( S2 A: d0 G
        Problems with a clear base case and recursive case.2 w* [, b# _/ U3 b+ V  F

    9 e" s  A! A" N. KExample: Fibonacci Sequence8 K' M' P0 t! k/ R1 v* @

    % D) M% t7 C3 I' H+ \The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, \8 Q" ?1 f2 A; T
    ! p4 y; M9 V0 G
        Base case: fib(0) = 0, fib(1) = 1- z  T, p* [  l3 }

    ! U) W" m' R: E8 w, }    Recursive case: fib(n) = fib(n-1) + fib(n-2)& T2 t! g2 G) _* h! D' C, l  K  @
    0 E3 V2 q7 ~2 n7 `* f7 K  V& H
    python7 k! h* d" C& P7 j$ I7 O

    ! A: g4 z% w8 I0 u$ X9 p8 J. {% P' }
    def fibonacci(n):
    2 ^% A3 s7 H  x; n% q: x    # Base cases
    - o; ^6 |( ]: J# S    if n == 0:
    - m6 L7 r4 T' ^$ S/ z. j, @        return 0
    9 E8 C# i; l# \8 {    elif n == 1:9 Z9 l1 X, v" z+ {6 l
            return 1
    " ^7 {& S% E  [* ]) {4 p" c2 N0 {    # Recursive case3 {1 z) n9 @% b1 J" J4 \
        else:% m' T) h$ {- S! |+ v
            return fibonacci(n - 1) + fibonacci(n - 2)& w; @  v$ O, c5 l

    . q6 x/ N7 @7 K1 s# Example usage
    " |+ v  N# {: J$ Bprint(fibonacci(6))  # Output: 80 B+ y4 K4 ]; P; O1 L9 k$ O
    5 ?, ~, q( V% S5 Q9 @, D9 w
    Tail Recursion
    ' A5 _, r/ S" f- v4 V, e9 L: `* L
    + A5 M3 f2 ?7 R" |& eTail 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).
    * |9 J) N( W! M* `$ J/ r: C  U' |) Q- Q% B/ X# 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, 2025-12-6 04:59 , Processed in 0.034746 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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