设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * u- R3 L" g0 N! d$ j/ R$ x
    ' @) m) e7 q, A+ z, W
    解释的不错9 k2 y  _, t# C4 T# W: K( Y

    7 a% Z' X. r: }$ ~递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。) M' G" s! C  J3 S$ k4 C
    / P+ _5 p8 e, A
    关键要素
    2 N* N( n$ a4 ~% ]- g- o$ f1. **基线条件(Base Case)**8 C  ?7 J9 m4 ]3 d% x0 L
       - 递归终止的条件,防止无限循环& I, S, u  W( T
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    6 o: a8 x7 K6 W2 c& W* A  i0 A0 x$ k2 d
    2. **递归条件(Recursive Case)**# d. R: L! J* O
       - 将原问题分解为更小的子问题% ]5 u9 K! w( S& P: T8 `
       - 例如:n! = n × (n-1)!2 c( J2 k- H! E$ l6 F

    " K" z+ ^7 x$ C. q 经典示例:计算阶乘
    ' j1 Y. d& B# K; ~python
    ' k; W; W) x! N, zdef factorial(n):& e4 v3 U+ Q/ U! ?( ~! i' O; X
        if n == 0:        # 基线条件
    / A) f- o/ x1 \) s( I1 L        return 1& _2 L4 P# |' y; V$ w' ]- j
        else:             # 递归条件1 X  @5 L& J7 h0 J: C: g: U3 {, H
            return n * factorial(n-1)  u+ y0 v* ?  s  e" [
    执行过程(以计算 3! 为例):+ l$ d: k7 A5 k5 p" I' h" E* S" W
    factorial(3)
    ' j+ W; Q$ p$ r9 i3 * factorial(2)
    $ n. s2 ?* h2 S; d# p% P, c4 s3 * (2 * factorial(1))
    ) r6 _  {6 s. ?% \5 l: D% \2 P3 * (2 * (1 * factorial(0)))  e0 W9 U7 h; @2 O& Y
    3 * (2 * (1 * 1)) = 6  e, H% X1 m. I9 l7 l2 v: x

    1 ]6 k& X5 }3 C/ y 递归思维要点
    4 q# `. u  U) A- C. e1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    : p% \  c. Y: d* h2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 ^  l$ F. h& W' _$ I
    3. **递推过程**:不断向下分解问题(递)
    ! P" K) C* n& R3 _: @; ~4. **回溯过程**:组合子问题结果返回(归); ~' g1 L' s0 G5 ~4 K

    + S+ A9 S* J: ]0 A  }9 f7 W 注意事项. q, o( ~5 s) c/ d9 ^
    必须要有终止条件
    7 f* ], B2 K1 M$ j递归深度过大可能导致栈溢出(Python默认递归深度约1000层)- S* e/ J9 B4 `) }! p- B8 C
    某些问题用递归更直观(如树遍历),但效率可能不如迭代  X4 b% G6 p2 Y
    尾递归优化可以提升效率(但Python不支持), R% X1 t# B% F5 R0 J' R. ~
    . }' A+ Y9 d8 f9 i1 ?; P, [& L
    递归 vs 迭代3 Z" q6 {# }! g+ d
    |          | 递归                          | 迭代               |
    2 Z( _+ [2 n; x|----------|-----------------------------|------------------|, f, e8 ?: t, ]1 H8 l, f) ?
    | 实现方式    | 函数自调用                        | 循环结构            |. u0 s( I8 W+ V! D1 A# {% e3 [' f
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |9 f: |" ?* V- u9 H# J3 P) x
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    4 ~" j, n& r9 n# i8 a| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    # }* N( [: U; k1 Y8 c" r& s% X8 l" k2 G
    ; Z2 E" c+ Y1 [/ g1 S 经典递归应用场景4 O- q" o' `; {3 J  ?* Q
    1. 文件系统遍历(目录树结构)  ~* ?( h& r  k: I* B! `
    2. 快速排序/归并排序算法8 c: {) r* V! N1 O
    3. 汉诺塔问题
    * `1 S" j: h% V% f, h4. 二叉树遍历(前序/中序/后序)+ d6 G5 `- P( l5 L# x7 I  l# _
    5. 生成所有可能的组合(回溯算法)% x( `/ K' g6 d

    & i6 D$ |0 c5 K" D5 Y' F- o3 j试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    10 小时前
  • 签到天数: 3104 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    & l6 s6 V9 T( i* O0 ?  o我推理机的核心算法应该是二叉树遍历的变种。; m$ n2 j& ~& ?. @: U
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    4 i" G2 o0 l9 _6 P! i8 [Key Idea of Recursion; c/ }  @5 Z- z8 i

    ( x8 [- \2 h: oA recursive function solves a problem by:; r- X( M- F) [( c5 I1 l1 u1 N
    8 `/ }$ k$ V- `; E3 Q
        Breaking the problem into smaller instances of the same problem.0 {! Z( C3 b& \( ^1 L' O! ~. G+ I  D

    , ?' L5 G  y/ D: V$ S4 G    Solving the smallest instance directly (base case).
    + F( T) J, X9 a) q6 ?# d; U1 t( ]' F$ O, p6 Y
        Combining the results of smaller instances to solve the larger problem.2 ~4 v: \/ T9 Y

    . }! S" S; k, n& ]4 E2 l8 s2 NComponents of a Recursive Function5 k% Y# j4 ]6 v" h7 L2 k

    & [  @- l+ l5 z% ?. h# V! a0 ^    Base Case:3 J6 O6 b* j' y9 g' f

    ! P  d/ G. G' L' p        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    3 @  s; U) W, t- M
    : p3 h3 ^$ j5 T2 l        It acts as the stopping condition to prevent infinite recursion.5 P. V. ^7 Z1 b
    7 w' D- D& z. z5 }1 h2 y; ?* K
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.0 e  R/ @8 r/ R; a! y4 s
    0 _; I% o* y" Z
        Recursive Case:" \/ K/ D; Q9 @3 p( H

    * u8 Z; O; I8 \3 W, @) U  S4 R( ~        This is where the function calls itself with a smaller or simpler version of the problem.
    ) }7 A. w. J/ n  ]3 M; C1 n$ |+ T+ s( K1 W
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ) x9 O; n( x, T" Q( {
    / t# n4 v: l  F2 H! t0 h' @Example: Factorial Calculation3 S1 W* z7 c+ V) k' ?6 P

    . h9 L# W3 `0 ]# c3 xThe 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 x. w5 W  r% @3 f1 e

    8 F; M$ |, h! P8 X8 v) ~; A    Base case: 0! = 1( A3 _. v% c9 g" D2 P: K
    , R, Q1 r1 J* i4 P" R% R
        Recursive case: n! = n * (n-1)!
    1 ^; H# e$ z! s& S9 _$ L9 J5 T% S  \$ n9 i
    Here’s how it looks in code (Python):; q# {7 a0 {# [
    python" n3 m$ U8 p# I% t" D0 q
    $ \0 ~5 _0 Q  p# q
    & |( x4 z1 @( j+ A! s$ o& `6 X
    def factorial(n):# E  \; Q" i0 q# D
        # Base case
    : s) y! Z/ U: s; \5 H& w, e6 d( n    if n == 0:2 f( J% M4 p; _
            return 1
    + S: c9 [; v; M/ q    # Recursive case
    4 A  [2 L/ @6 v; e    else:) S4 T) I" Y  a6 V
            return n * factorial(n - 1)+ z" N6 K( d; X3 y) h

    " w; k1 C7 m% v6 u' k6 a, T: F, h# Example usage
      l1 D" C4 ?) M$ U6 C) H/ dprint(factorial(5))  # Output: 120% u" Y/ w; R9 h% i4 D6 y

    3 Q4 k; @- w; Y  K' P/ P; hHow Recursion Works% H/ E8 q. L$ x7 p& F# U% g
      N$ L6 l0 w5 ?# z! M  ^
        The function keeps calling itself with smaller inputs until it reaches the base case.1 |4 B- h/ h( ~
    8 G1 z4 T/ |( k/ S8 P6 e
        Once the base case is reached, the function starts returning values back up the call stack.2 ], H# I# \# U+ p1 g& h

      W, L# g% Z& m) o    These returned values are combined to produce the final result.
    # z: F6 G! U5 n  j+ D# d
    6 Y# k) a2 E' z- o+ oFor factorial(5):
    ( i: N1 k; @' L, j# e, S$ ]1 R$ Z) c1 @; @- w
    1 N, ^& `1 \6 D
    factorial(5) = 5 * factorial(4)
    4 Y. y3 _$ ]3 \2 `9 K1 b: K8 @/ sfactorial(4) = 4 * factorial(3)
    # c- I7 K$ `. f  ufactorial(3) = 3 * factorial(2)) ]; u( ]0 ?* N$ Q7 |- F
    factorial(2) = 2 * factorial(1)( h$ @0 D6 n2 h/ B
    factorial(1) = 1 * factorial(0)
    6 q/ M) l/ Q# m5 D9 i; K- mfactorial(0) = 1  # Base case
    , p$ ]5 o, l* e9 [# _" G, o# R' `8 ~1 j' a9 Z* @6 m
    Then, the results are combined:
    9 R: R  F: \; j% U+ z
    ! W: |! y' ?/ K! j6 a# C. O1 n
    9 ^' j6 {* \1 E7 {factorial(1) = 1 * 1 = 1
    ' z! ]: E3 Z, g- \6 Vfactorial(2) = 2 * 1 = 2& i' t4 ~; ?) Z* X4 l) f
    factorial(3) = 3 * 2 = 69 t! S$ P/ ?; e4 S) M. Z: O+ O
    factorial(4) = 4 * 6 = 24
    ' C, }2 N2 H, s+ ?; C) e2 T0 N# efactorial(5) = 5 * 24 = 120
    2 z% V/ ]6 w% T" ]% u% o( [0 ?6 r( |9 T) D0 Y- N( @8 a/ [% H9 G
    Advantages of Recursion
    6 [- g- ]6 D8 l" g% x6 G3 n7 x% V" y
        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).
    . q, d. W" g6 W: [& J8 d& Y! r
    . `6 _. M4 I+ U) [1 J) e5 l    Readability: Recursive code can be more readable and concise compared to iterative solutions.
      @5 L) A& W& r1 {: L7 z  C$ @1 W" b' U% d  ^' M; O) K/ s3 F: T
    Disadvantages of Recursion( E2 J) B1 J* R: f( O' l

    % H+ W0 b3 P9 D    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.
    ( N+ A& h( {: p* x2 T
    3 H# D! Z  p+ }0 B: k3 z: ]    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    5 \9 p, ?5 ?, A2 F9 S! b' ?9 N5 y2 a$ B
    When to Use Recursion3 U8 ?- b4 L; j1 t" I3 [0 k* i* Q

    2 m+ r* ~# Y; j" o: i7 `    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).2 A# H& q7 O- C3 B, y. {/ ~

    , i: _& w) T+ n' q    Problems with a clear base case and recursive case.3 u: _6 `6 @. E% z/ S
    1 c  Y: u% i5 X$ o9 B0 ~
    Example: Fibonacci Sequence
    3 e: g+ s2 J+ T2 B* d; V' {8 |7 C
    + E  U% y. V$ o% @& T0 WThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    8 e7 X( _2 X7 |& d9 b+ [
    2 W( A% U. C1 q    Base case: fib(0) = 0, fib(1) = 1/ Q$ p6 ~: T4 \' u/ B$ V
    9 F% q/ Q1 h# Y1 E2 R1 c
        Recursive case: fib(n) = fib(n-1) + fib(n-2)6 C* _: @! u  r* o# Y

    " g7 B3 c3 I( h. t  l0 Mpython' e. w/ m9 D6 m- b$ f2 ~$ c) N
    , w6 `2 b& \1 ~6 W( p) J! A) T3 P

    * F( J1 w- w/ Z6 odef fibonacci(n):, |, Z3 U$ Q1 b3 K, u
        # Base cases
    9 D! i. n6 G0 f, |! g$ k/ c- W' L    if n == 0:
    2 i( F. ~! [( ?' F- k  l3 Q        return 0
    1 w+ p2 _% U& W/ d' s5 k' ^7 L    elif n == 1:
    " Q, D( M: |' T; h* E' \2 A        return 1
    9 G. Q4 @# V% Y8 [/ x5 t    # Recursive case4 r8 G- W3 p' q& o) L
        else:/ ?7 B; V# r% C; x' |; {2 Y/ ~
            return fibonacci(n - 1) + fibonacci(n - 2)8 e: G: d* ~/ M

    ( B- \3 i* S$ R1 J8 i* k# Example usage
    ! P* C9 z2 P8 [6 fprint(fibonacci(6))  # Output: 87 U3 S, M: P0 w

    & i' C: g2 ]1 M3 RTail Recursion
    " \( G3 q' y/ u3 R8 T. c4 h  }" p9 h6 ~6 b
    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).1 {# Q- e9 T- @' j/ V( W1 X3 d! p

    % [7 \4 ^4 ^7 EIn 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-11-29 17:12 , Processed in 0.049812 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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