设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * F. {- k5 R) M! G0 Q

    $ k6 R7 O4 P2 S) F; J' |解释的不错5 A7 j$ u" @: f
    - Q$ Q1 J; x1 K0 o# Y" G$ Q6 w9 @
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。, F0 {, [5 E+ p# z4 @

    & j0 K$ u$ _/ P/ q( ` 关键要素1 t8 B7 |2 }& q! t/ Q# M: R9 o
    1. **基线条件(Base Case)**- a5 t, [7 H. f) i. m
       - 递归终止的条件,防止无限循环
    / O9 m7 b9 z1 s+ z! ]/ k3 F   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1  z# q9 f: Z# D, C+ b/ N8 |$ O
    ) R5 y) t% \2 D5 g3 z
    2. **递归条件(Recursive Case)**; Q; y: M, x! |1 H9 ?
       - 将原问题分解为更小的子问题3 P$ ~3 P% a# d
       - 例如:n! = n × (n-1)!0 s! I% Y- j' n- N4 A) d. R: G# h$ ~
      h  J) W: p; z
    经典示例:计算阶乘) F) I6 t' i+ w2 P
    python
    , G# e5 ^$ b6 m. X4 a& ydef factorial(n):
    5 t2 x! g8 c+ [% e. _2 g    if n == 0:        # 基线条件
    7 p2 d8 b, b. l' X- n* `+ y        return 1
    ) H+ _& m  w; o" F0 Q2 e! X    else:             # 递归条件! Q' f) A( X1 l! E5 y- Q
            return n * factorial(n-1)2 z' Z( |' }, M* |- W- q; i
    执行过程(以计算 3! 为例):
    6 f) |6 J; C5 {3 Q( J7 E0 `+ `2 _factorial(3)
    * c. D1 h# x* E$ Z! ]* ^  n3 q3 * factorial(2)
      ]# V& t4 e, Q8 d3 * (2 * factorial(1))" O  t( E- E) L$ d( z/ ]
    3 * (2 * (1 * factorial(0)))  [! w5 u! c6 E+ E! e
    3 * (2 * (1 * 1)) = 6
    ! \; F- i& j, }& ^2 F" s5 W1 h% e: f9 u& @4 g
    递归思维要点1 ~. C) g8 x) }
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑( ?% Q6 F) R; x# e- h& E! U
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    0 p- r% p' s9 y: a  w( ?3. **递推过程**:不断向下分解问题(递)
    9 v) }% t% J( W# k8 m4. **回溯过程**:组合子问题结果返回(归)0 m  \$ `  g* a% _9 I" q; U. r3 y
    ) @0 H: p* e7 \7 K5 I2 ~
    注意事项( t5 k  A( F# l/ K( }/ G/ |4 Y
    必须要有终止条件
    * E% D/ G& g2 g" U7 U递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    * z0 S$ P* d, B' u某些问题用递归更直观(如树遍历),但效率可能不如迭代
    0 a0 d$ A+ L% @尾递归优化可以提升效率(但Python不支持)7 ^9 H8 y, E" B; H( V* ^5 n

    ( \5 I* X* Y* t" ?, h/ H 递归 vs 迭代- Q) B, ]4 i3 _4 K' B
    |          | 递归                          | 迭代               |2 Z' p! t% [5 v5 o2 ?1 H. S
    |----------|-----------------------------|------------------|
    2 ~# m/ M. \& m! A* [2 N| 实现方式    | 函数自调用                        | 循环结构            |, y! B" C4 f. |& }1 c; h+ P
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    4 v* c, w7 {1 M7 m" N| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    " @" y+ w& Q: G* _  c3 y  e* s| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |* {: I2 C9 X8 A) l% S
    . \8 \7 d% s  H$ G+ w/ {. r
    经典递归应用场景
    ' Z( m0 ~. l( }8 Y) ^( K7 w1. 文件系统遍历(目录树结构)
    1 W# K  {2 m: E& p4 L+ `" p2. 快速排序/归并排序算法- G2 r5 T; W) K4 p; m& @
    3. 汉诺塔问题* z4 J3 b2 q% s6 Z
    4. 二叉树遍历(前序/中序/后序)
    8 z/ H0 S) |' W+ c" a5. 生成所有可能的组合(回溯算法)" F: O9 p( O5 Y( E: ]5 {

    / C- y4 k9 H+ r, `试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 06:39
  • 签到天数: 3105 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    9 }! E: c3 W1 u; f* @1 m我推理机的核心算法应该是二叉树遍历的变种。
    7 E+ Z7 m! h& w8 V- a8 D另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:% q: O/ [+ l" @8 H
    Key Idea of Recursion
    $ s2 N4 [4 P- v' e! f9 o- L9 ]" x' w( U: Y
    A recursive function solves a problem by:! ?6 R0 Y  H- C7 _- z; Y

    3 `: @' E' I/ C1 ]2 @    Breaking the problem into smaller instances of the same problem.
    4 |& z. g+ |* M) r# L8 F, r- n" q. [7 I4 b$ |! N" h2 N0 b
        Solving the smallest instance directly (base case).
    2 [5 d4 Y/ x( @5 }3 [  q/ \$ G; s  X0 {- \$ @: H( t
        Combining the results of smaller instances to solve the larger problem.
    9 l2 I- j0 ^( Q: @$ ^0 L
    , w$ b5 `3 ~$ W, G; WComponents of a Recursive Function) m) }" i1 O! y% S
    7 l) w' E- G. n
        Base Case:
    . t" y- B0 D4 y, u3 f- K( w0 a
    5 O' }' G5 |7 W% j6 {6 H        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    4 ^- |) Z! o' k% O0 L* V( D) f
    ' R. ?$ d  e; c; z8 {5 L% `/ p        It acts as the stopping condition to prevent infinite recursion.0 o  Z9 Y" R' }% M0 I

    : b2 W+ I; Y" g" p% Y5 v2 Z        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.% p0 ?; g0 j6 Y+ j/ B( Z4 d
    , n# B7 n7 }6 U/ |
        Recursive Case:6 e. C$ {0 B8 L. r( y0 X3 @- i' Z; f% v
    9 j+ h- V9 K/ n
            This is where the function calls itself with a smaller or simpler version of the problem.
    4 _* k; f1 Z) ]1 |4 P5 A' _. ?/ q1 X0 l/ z; l7 J- u0 _1 v- {3 Y
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
      Y% w1 p) |9 S2 q
    $ b! c0 V/ c/ U0 MExample: Factorial Calculation
    1 S0 o0 Y$ ?; h- z
    6 O( I% \3 ~0 M5 T/ ]# [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:
    4 o! B& H! l4 W, t" Y  `6 S2 a& Y. {
        Base case: 0! = 1
    9 }9 j/ s# S* t* @& j3 e7 ^2 e8 [8 v, y1 u& x5 K
        Recursive case: n! = n * (n-1)!* O4 w, n/ @* v1 p: w

    0 z' c& I) u4 S' G( p5 [$ }9 u8 yHere’s how it looks in code (Python):+ X- N: T4 {  r# p% ~: v
    python* @  l! c; F; v: d  B. `5 ], ?

    * D2 L/ X7 a0 @1 v) R" M  S1 O
    def factorial(n):' D1 y; u! c* _8 f! |. o
        # Base case* }% L- `  C+ I+ [+ t
        if n == 0:  l. r0 m0 {9 K; _
            return 1
    . a: H' }. n. F5 d0 F, F- }    # Recursive case
    ) i9 J2 W9 x( q, ]( L# J, ~    else:
    - t, P+ A/ }) u: }        return n * factorial(n - 1)
    . r) M$ I; h/ l2 h! k% W7 K& b
    6 @+ g7 C- a  H6 I; Y; s# Example usage# r7 H; q7 y2 m' G! m
    print(factorial(5))  # Output: 120
    & v: O- q7 h& D! Q2 ~6 n: W/ p3 z7 q5 k/ d/ O) i6 n) ]/ X
    How Recursion Works4 G2 E+ ^% j: C0 q. z0 e1 E7 O

    ' V( u. g$ x3 I; }) S& D2 M: }! f    The function keeps calling itself with smaller inputs until it reaches the base case.
    ; w  k" k3 c0 R, _
    0 j3 p' T8 [  r$ g    Once the base case is reached, the function starts returning values back up the call stack.
    ( G, p+ O* R1 B  K
    : y4 w' ~) ~$ R* g    These returned values are combined to produce the final result.' {$ U7 M0 R8 _/ z8 H: z+ j
    $ m# A2 @. ], L$ M
    For factorial(5):4 R8 \2 t2 ~2 n; w. k( w

    0 S. |& q5 K9 j1 H
    . ]1 s% g. A" i5 L- S* v! ?7 |factorial(5) = 5 * factorial(4)0 R9 p! A! _3 _- _9 X* u4 c, A- L
    factorial(4) = 4 * factorial(3)7 |6 A. }4 n* v0 K% t; @
    factorial(3) = 3 * factorial(2)
    0 _, H. `* R8 E& p% |* Q% s- Ofactorial(2) = 2 * factorial(1)
    5 z( R# x7 s/ f/ e1 t$ T" Cfactorial(1) = 1 * factorial(0)
    ; Z9 f! E+ c2 c( T- F1 Tfactorial(0) = 1  # Base case7 z# q$ x( h5 V! h" N2 O
    ) W7 n, N0 e9 y; ?+ f8 R
    Then, the results are combined:
    $ Q5 ^% f+ ]6 U; U
    1 r) e- d# i" ^$ ?. P# s
    6 v# W' K" d9 a8 A; o  Pfactorial(1) = 1 * 1 = 1
    3 ~! o' Q& t; Y. J/ ^1 Efactorial(2) = 2 * 1 = 2" Q+ A( g+ [$ L1 l$ ]
    factorial(3) = 3 * 2 = 6# y/ M/ K7 j4 l, q0 k2 y) p
    factorial(4) = 4 * 6 = 24
    ; i7 }/ h$ u! I& O- Y& F* f6 a, Zfactorial(5) = 5 * 24 = 120
    % [4 C" V$ a+ H+ f- D( R: j9 c+ z( {3 K' M, G8 \6 V+ z) x" ^" q
    Advantages of Recursion
    ' n- w0 g* n( f  r4 ^2 e% e: Q3 t" z4 M* Z8 n( ?
        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).. J8 w2 H+ [3 u9 ~+ x1 K

    2 b* J1 Z* ], v/ r" J6 ?    Readability: Recursive code can be more readable and concise compared to iterative solutions.; m  U, S- z& M* U  s* `  A5 F) \
    ) W$ o/ F7 N1 y. G8 O' t
    Disadvantages of Recursion
    ' w+ o9 s3 \6 X& e4 v, r) T$ c9 B3 b) F8 L$ m/ @
        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.9 u8 `8 ~+ \, ^

    1 t0 [' r& c! T  v" T5 e    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).- `7 V( ~2 ~* ^

    : T' b+ x! f/ k, XWhen to Use Recursion6 H' T5 {- o; d! ~
    # G; B& s3 S6 `, f$ S
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ' Z1 L( R2 {8 o4 p' D4 |
    . X+ _1 q/ _$ F    Problems with a clear base case and recursive case.
    ( W2 M$ }. f$ P4 B9 k
    # M+ j- C& U) D4 L1 `2 GExample: Fibonacci Sequence
    " Q6 B; z& n. m1 `& X- i* V& X# p; n: P+ M/ f
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    - Z1 I& b2 a: T1 a! f4 S0 U
    - ?, Q4 O; }' j4 E, p    Base case: fib(0) = 0, fib(1) = 1
    7 E7 ?' i3 {% u
    : z4 z) m4 k, G/ L5 W( z& Z    Recursive case: fib(n) = fib(n-1) + fib(n-2)3 ^/ u* s) n" F+ d

    6 D* ?" ~* [$ ]5 a+ Y& Spython
    8 M. W  t1 J0 U: k, W+ f# q9 j
    ! ~3 ^: U( H: i
    8 z  b( d, O* @$ _# E) Wdef fibonacci(n):
    / g2 d' ~2 a/ Y, G( a    # Base cases
    5 |0 i! ^' x1 \& b# N; P: _- S    if n == 0:
    " Z" {3 t! W# Q7 p        return 0
    : w9 \: h# E! l. F- d    elif n == 1:
    * ?. n7 b9 D* D6 \% ~* R# Q# \        return 15 R5 r4 F6 b' W- t$ \/ K$ h
        # Recursive case5 |8 h7 z9 Y- S9 O/ w/ D! y$ L
        else:9 B; L) U, ?" w7 W, C; k4 p
            return fibonacci(n - 1) + fibonacci(n - 2)
    1 Z2 }8 _6 }8 I. n5 y& l4 [2 l
    9 M! B$ N! n/ N# D# e# Example usage& O9 }1 _2 i: e" b0 ]2 P5 }. ~
    print(fibonacci(6))  # Output: 8! j% K$ j" K' j3 V; K' U' O
    ( L9 E' z' n7 f7 s
    Tail Recursion: i) j7 P8 @0 a3 z3 k

    ; `% f! s& v+ r/ k( p$ o- bTail 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).
    - u# z/ ?& _# B! s$ A, `5 y2 p2 j8 }3 F! q/ Q5 s
    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-1 04:11 , Processed in 0.032402 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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