设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 9 M8 a' e1 n1 S9 t5 o' |) H

    . T, M8 y, ?! y% j  c7 `5 f* ?解释的不错
    ) q7 B- N. f& K! _+ b) n% _7 m+ F+ w+ k1 I' p" y
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    7 H- \- P; s4 a5 v4 n8 I- i
    . S2 N1 A- ]. |* j 关键要素
    7 P5 b) B( i4 E6 ?" ~$ F1. **基线条件(Base Case)**5 ]2 F% h' S+ B0 b* y) l- N" m
       - 递归终止的条件,防止无限循环
    ; C6 e% F: g$ U' D9 o7 ]: U5 E) Q   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1& |; W! A: D# I1 B6 }6 E% q$ N

    - B9 k# E( W) A2. **递归条件(Recursive Case)**3 e+ L* r8 Q+ J- T8 f
       - 将原问题分解为更小的子问题
    ! m" S6 H3 D  r   - 例如:n! = n × (n-1)!7 g! S( b. Q! b# {: u  |

    4 Y7 s) I9 S7 G. L 经典示例:计算阶乘/ n/ M1 w4 L( M$ a( p+ p7 X
    python3 x$ W0 t# i% z8 {
    def factorial(n):
    2 g3 X" H% |6 h8 @    if n == 0:        # 基线条件0 G# ]2 V( S9 u/ M  \7 @# d3 s' z
            return 1
    / K$ c# }& c/ v5 a    else:             # 递归条件
    # U0 K* L$ g5 U/ q0 Y        return n * factorial(n-1)4 R, X. M) A% D" Y
    执行过程(以计算 3! 为例):: c1 K9 P( z4 B$ [9 P1 U9 x2 @
    factorial(3)
    ! U& k- p  \9 N; |& z3 }# G3 * factorial(2)0 |2 L+ h9 n2 H/ D: ]- L
    3 * (2 * factorial(1))1 z  N9 a7 @- L9 I3 m! C) @
    3 * (2 * (1 * factorial(0)))% P( j, F, S$ Q
    3 * (2 * (1 * 1)) = 6
    ' g) i. o; l! L3 D% T: O6 ~  E+ q7 S+ j. @& E, ]2 W
    递归思维要点" a% x" a, R; N/ X) \6 p
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑. c4 ?3 v& ]! Q& G$ t, C
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)0 K% }$ q: I  E' a  B$ n# T
    3. **递推过程**:不断向下分解问题(递)
    4 {$ ^' z+ l$ r' x4. **回溯过程**:组合子问题结果返回(归)
    - ]3 Z3 J, L, z9 m+ g
    4 `  N8 N. ^( T 注意事项
    4 Y- k1 M  M1 k# h必须要有终止条件
    ! J9 d# @& O& f) n; g$ U. r递归深度过大可能导致栈溢出(Python默认递归深度约1000层)" p# _8 i! E% Q% ?
    某些问题用递归更直观(如树遍历),但效率可能不如迭代9 f7 j. ]9 T/ w! s; T
    尾递归优化可以提升效率(但Python不支持)! G, [: g* T6 `

    ( T# q, {, ^; m( h2 k 递归 vs 迭代
    , t% N4 Z$ L( n- B6 W; K: X4 b|          | 递归                          | 迭代               |
    9 y% q5 b4 M6 u+ q3 d3 h) C|----------|-----------------------------|------------------|% m) C: Y! `  z1 G* q) f; O
    | 实现方式    | 函数自调用                        | 循环结构            |
    , L1 @5 _( ~0 S; f' l5 z| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |( R  G( U7 p9 W3 y
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    6 z/ c, x, K  O+ x1 Q8 N| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |7 `( O, E8 Z, f: V9 h# z: y) y
    & i2 y4 A$ k" X2 N6 I+ Y
    经典递归应用场景
    & h0 R# m9 u0 }' [/ J1. 文件系统遍历(目录树结构)8 e# ^) `9 [8 w' c) @
    2. 快速排序/归并排序算法
    , V" B) X0 G- I1 g- H- [8 n& B; Z3. 汉诺塔问题7 K, `- y5 e! d- F: A& W
    4. 二叉树遍历(前序/中序/后序)1 S; n3 H# i& J) H5 G/ m, w
    5. 生成所有可能的组合(回溯算法)$ S2 K) |# S- N& |! n0 ?! d( d
    ( K( M' S* t: [5 j/ O- G2 M/ J
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    2 小时前
  • 签到天数: 3109 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,& O0 g/ }6 I( s3 j1 z
    我推理机的核心算法应该是二叉树遍历的变种。
    2 X: \, y+ `, O: l2 i% U1 r4 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:
    $ M' d" |: {& ^* OKey Idea of Recursion
    + z0 L  |5 b( u  C. f! Y2 O- W% _& M1 N% w9 k5 {; g
    A recursive function solves a problem by:
    4 g! s5 v2 [% J7 e9 F+ m
    # a' ]- l8 u7 k% `! K    Breaking the problem into smaller instances of the same problem.: D# @, e& y3 T: l- [4 L( `

      `0 J, E+ u% ^9 a0 \% s    Solving the smallest instance directly (base case).
    ) ]6 H  d0 P5 C$ K8 o- W% w+ a
    ) O; G/ c' ?: r! D/ }# r    Combining the results of smaller instances to solve the larger problem.
      `5 |% D# \# [  u" r  H
    5 `  E" |8 Z1 J8 I9 EComponents of a Recursive Function/ W. n9 H. P2 Z( d

    ) B! J1 x* Z+ Z/ A    Base Case:
    7 s- ~4 }6 M" r; L. ~" s* W  H2 S" z2 T( r
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    5 ^1 s8 t) @) J$ ~, p  `
    , l# w1 d, D8 _  b* c% i        It acts as the stopping condition to prevent infinite recursion., Z2 Z, V; u( G- H/ f$ P( g6 z/ A

    ! u8 V% ?3 s  T  }) z2 n* D        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.( k. `2 V. |* b0 h7 G

    2 W( m) z; g; G  n/ z    Recursive Case:
    1 q+ `3 d  ~( q/ k: r- w7 y* T* M' s  U( s; n
            This is where the function calls itself with a smaller or simpler version of the problem.8 N) Q& ?, k% ?; J

    ! b0 M: a/ ]; w4 T- s, h% D- j        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    9 }' p! G9 D+ M% `4 y. e8 z
    8 y% a* h2 C% ~Example: Factorial Calculation3 c" c7 y8 M# R, Z* N: N5 [' R( l. j
    , {2 a  t9 h# l& C+ S. C9 s
    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 _" Z/ e+ A* B1 A

    7 p: S8 {$ s& I3 I    Base case: 0! = 1
    . ]2 N+ H8 O: M! W1 K
    ' m& ?& x6 @5 t: W7 r' A    Recursive case: n! = n * (n-1)!' A9 a3 R# L7 `- T0 B: h1 _

    : u, G( j% @  w2 z9 DHere’s how it looks in code (Python):
    7 s9 O. P  l( ]python
    ' P; p( N( Z7 U2 M  l* q
    2 S+ @' M, Z+ x0 `
    $ ]8 {* H1 a- `, @def factorial(n):* t8 X2 s. t' g: x) _1 j0 a1 E& S$ K
        # Base case, F' l5 V" |/ j7 s" p+ y3 U  f" o
        if n == 0:
    3 G1 ?8 Y: v0 d: W6 B        return 1
    2 ?' E  }: T; {) Y) s    # Recursive case, s1 k! u% t  b) D, k" W7 g- Q
        else:( r( B2 B& ]) b' c/ v5 e
            return n * factorial(n - 1)
    5 b8 L8 ^" M0 f- p* o; |  O/ F& g  L
    # Example usage
    9 @; m0 d8 H, J+ _8 d, e( N4 m1 jprint(factorial(5))  # Output: 120
    # R+ U; Y) O% q7 D$ F( h- C3 K) E
    1 A  ^  r$ {, @. d' PHow Recursion Works' u. `; ^; m) a9 L6 X
    2 m  `4 s& c& G! u3 H. M
        The function keeps calling itself with smaller inputs until it reaches the base case.- l1 I3 j3 G: Q  q% c- X
    ) u  R* k5 N+ F1 ]
        Once the base case is reached, the function starts returning values back up the call stack.
    ) F9 E% P, h$ T  a( G) ?
    2 ]) _4 R4 l  D1 }4 F- v& g    These returned values are combined to produce the final result.5 K4 Y0 o& H. s
      w& T( ]9 R* N2 ?5 P) f* I
    For factorial(5):- @: s# h2 b# A. ~

    1 H; G' R. u( T( ^
    0 M7 |) G8 Y3 t& X) X4 ?factorial(5) = 5 * factorial(4), O6 I# D' V3 A0 c  r
    factorial(4) = 4 * factorial(3)) `; S* E! k# k% O: R6 n& P
    factorial(3) = 3 * factorial(2)/ q* P. l( m# |/ c7 q6 C: @
    factorial(2) = 2 * factorial(1)/ D$ U3 t4 @/ Q3 a, [
    factorial(1) = 1 * factorial(0)* O6 k5 e3 C* q5 j) J
    factorial(0) = 1  # Base case
    + W# R9 }( w1 S* [- e! D( Y0 b& Q: j$ m- ^
    Then, the results are combined:2 g1 V  I0 v( Y+ v' \" ^- n' p6 M# v

    / U# k/ [! U( N0 m/ Q5 [9 Q+ x* p% m, [0 K: Y. Z
    factorial(1) = 1 * 1 = 1! X$ ?' _* Z! K4 R9 t9 K
    factorial(2) = 2 * 1 = 27 x) w  \4 T/ b
    factorial(3) = 3 * 2 = 6
    3 R  f) Q2 H. A4 B2 t5 \# Ffactorial(4) = 4 * 6 = 24  M& D3 q3 z& b" A
    factorial(5) = 5 * 24 = 1209 S. H* E3 u$ V+ Q) A
    8 L. i3 S$ {( [: I+ o) r
    Advantages of Recursion
    9 C4 f3 f9 x' O1 @6 N, @( i
    0 N" F6 ]% B" h0 G' k    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).& u. V  j2 O: u- w5 i

    $ K0 K; p2 _" p/ u! c    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    - a% }! p$ `; Z3 l" L
    1 U0 F) p: ~! Y7 P0 nDisadvantages of Recursion
    1 f5 [2 K) E1 m( m' \
    % O! d- W2 n- |7 {/ o1 V1 t    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.
    $ K$ K+ y* d  u" R- U- K; e8 L+ o7 l
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    9 k: l- y! q% |6 E
    ) T$ v/ N0 g# L9 qWhen to Use Recursion5 w% X. ?! n- l/ u. t

    ; p2 Y( u% g' Y1 o) u6 |    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    7 l+ J& c" G" ~- v$ I% Z( `/ X5 O' J) a( ~0 L1 N( o
        Problems with a clear base case and recursive case.! x9 [6 k; B; C( n5 D+ A4 m
    7 J/ T7 X. y4 O% p
    Example: Fibonacci Sequence
    $ ~) _, K- {3 ?  r, M! [! O, c) z. L  P
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    6 U6 R, p3 W: }- Y8 E% R# N. s5 D2 E/ J" b
        Base case: fib(0) = 0, fib(1) = 1
    % ?3 d: i& K% W5 u& J" n1 w; f7 O+ W& f3 ^; W, s% i
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ) E4 J1 ~; _# y8 O9 g2 x1 \. C
    1 H- Q3 n% `! g0 B9 v6 vpython7 X- m2 X. A; T; O2 k  H+ C

    3 B7 w5 i1 i2 K5 t! F9 u/ p8 n' k9 P5 a0 q
    def fibonacci(n):
    3 B( G6 b4 L- u    # Base cases9 ?- Z! Q4 t; c, P
        if n == 0:9 g" `( e7 r9 a
            return 03 t5 G8 W+ v5 g4 Y$ U7 K3 n" n1 n
        elif n == 1:
    ' M5 a* n" l" ?2 n/ B! w" p; @        return 1
    ( y5 _) _5 p/ B$ L5 {    # Recursive case1 G% F( w) F2 [: j% I
        else:
    ) @5 K. O9 x  x  c        return fibonacci(n - 1) + fibonacci(n - 2)* i( x6 P: e5 @
    6 ~: s0 ^3 ]( p* Y6 p" U
    # Example usage4 c4 w$ u: t" T: N9 @& C; Q, ^
    print(fibonacci(6))  # Output: 8
    8 V# r/ w' F2 L2 B6 o# M9 `8 f7 Z9 }% N3 z! l# }
    Tail Recursion
    ' |. B8 e! Q" `1 S- G$ m& @$ d* ^; q4 [+ q. Q# m
    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).
    : K/ i" ~& Q5 b0 E9 W2 C; B2 k3 R1 X9 _5 |8 a$ G4 v' ^9 u
    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-5 11:41 , Processed in 0.033664 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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