设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑   h  i( t) W9 @
    ! \: Z8 G* _. C
    解释的不错
    9 @3 Q" S7 e1 p6 b+ @" e8 u: g. B7 `  {' ^
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ( h( ?& m( C# d8 t0 h
    ) t) K0 L9 k% ?: ` 关键要素) a2 l' w0 K5 D4 I2 R! B( y. K
    1. **基线条件(Base Case)**
    * h- T9 ?! s" a/ l8 u# m   - 递归终止的条件,防止无限循环
    8 x$ p9 S- w8 K; x6 ]: U! @1 S   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1' s$ g# r/ |  k# X( ?' j

    * `" n5 |* h/ u+ R  L* \8 i2. **递归条件(Recursive Case)**
    ( \, E, Z$ u# ?   - 将原问题分解为更小的子问题. ^0 t1 A8 ^  f6 v( F7 l
       - 例如:n! = n × (n-1)!2 K) w# k9 `$ J% [% \4 L1 F" |

    0 y% ]. P2 c* n% q) {! J 经典示例:计算阶乘
    : i) y$ k  W0 J& apython% U5 i7 t, l  W7 z4 O3 U7 f7 J
    def factorial(n):' p8 I" d& C9 a% N4 y" y) n
        if n == 0:        # 基线条件  Q6 A$ R' G7 d, D
            return 11 Y$ T/ {1 q+ x$ ~* V
        else:             # 递归条件
    & o- N. P) `! U7 S# `6 H        return n * factorial(n-1): d4 e. M0 B! R8 z' T! U
    执行过程(以计算 3! 为例):
    , `  R' k; M) [0 K( v/ \factorial(3)" s# n7 l3 H1 k& d% i7 M
    3 * factorial(2)
    , M. d9 d# T4 W, F: d0 L1 @" B3 * (2 * factorial(1))
    1 ^: e0 E$ P5 z: j, ~4 N  g3 * (2 * (1 * factorial(0)))0 r' g& O& G8 g4 j  k
    3 * (2 * (1 * 1)) = 6( I8 ?$ s( S* l' d1 V# @
    + g# G  W- ?( O/ q2 v8 q
    递归思维要点
    ' [  m: }. C+ c) J; g1. **信任递归**:假设子问题已经解决,专注当前层逻辑: [! G1 }& W0 k& v" ?
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    1 o& \2 A. I" M5 ?3. **递推过程**:不断向下分解问题(递)
    & w- u) D/ s5 H, O% [4. **回溯过程**:组合子问题结果返回(归)) X5 X& r$ M4 N, ^
    6 {/ b6 k6 R( M  h
    注意事项3 m6 V7 C( j1 n6 C1 ~; ~
    必须要有终止条件6 h: j5 Q- ~8 @
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 z$ e: S2 F* A% T5 {! c7 D/ \
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    : g: z+ z2 `/ x( Y' u3 s$ @尾递归优化可以提升效率(但Python不支持)  d- C7 J5 q/ z" e  Y- l! A1 M: j

    3 y, m# y8 ]) l6 G6 \- _6 B 递归 vs 迭代. J3 F/ K8 S9 o# P: F
    |          | 递归                          | 迭代               |
    ; n- Y1 ?5 j" V8 ]|----------|-----------------------------|------------------|0 ?7 T; \; Z8 X9 k
    | 实现方式    | 函数自调用                        | 循环结构            |
    : B8 g! H5 M% I" ~" s| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |9 E2 x* v& F4 v5 O4 P) v$ A; G
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ( T+ \# E8 ^% u' I1 U9 n| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    $ Q4 E$ t" ~) D4 j/ w/ }; R0 i
    ' ~6 g: S# w2 ?0 Y& n 经典递归应用场景" r0 N3 z' [( Q
    1. 文件系统遍历(目录树结构)
    8 X8 d5 r* R7 q5 q1 Y8 J) g! j+ t2. 快速排序/归并排序算法
    / ?% k* ]+ @( o8 B, c3. 汉诺塔问题
    $ T% Y/ b' y0 _  q4 ^4. 二叉树遍历(前序/中序/后序)
    * e, b, g* Q) e: U- ^5. 生成所有可能的组合(回溯算法)
    $ P' K" E5 S5 n  ]/ H( {1 @2 j) k7 H( ?( x0 U- a, F9 }
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    10 小时前
  • 签到天数: 3197 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    4 {- c: D0 @3 z" y8 q9 h" P* F我推理机的核心算法应该是二叉树遍历的变种。! b- I  r5 H2 E& p# R( Y+ t* {
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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, K/ @6 u. B4 l
    Key Idea of Recursion3 T- \2 W. c5 P4 f6 Q) q
    " c7 j5 z6 H2 x3 w: O4 G6 W! M  X$ I4 t
    A recursive function solves a problem by:
    / Q, t/ T/ ]+ h3 d
    3 u4 d; s; |3 \+ Z' G% J" |    Breaking the problem into smaller instances of the same problem.: @9 `9 m( a3 w: e

    # x/ ]$ n: ~3 A. U$ l    Solving the smallest instance directly (base case).
    1 c' Y* x' l9 B
      ]* c' E, |. ~' M2 J# @; t* I+ \    Combining the results of smaller instances to solve the larger problem.2 a4 r4 Z' f6 a' n, B  b
    ( f1 p+ V( J; v- X% r4 T9 d( |
    Components of a Recursive Function
    % n: ^* Z( l, @4 Z- C+ t. Q
    - _: Q  d" O1 O2 n. O    Base Case:! C2 \1 [) Z: D8 `1 F9 A& o0 [

    ' t4 J" d/ L! y. d% Y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ; @' k* \1 P' D/ `( F3 M4 I4 n
    $ \( a4 X" m4 n6 m        It acts as the stopping condition to prevent infinite recursion.
    ( Z$ r& _0 C' l7 [5 {- j4 U9 [0 S
    6 U2 |0 V7 H5 M( H        Example: In calculating the factorial of a number, the base case is factorial(0) = 1." U$ b* y6 o3 [" {8 O
    . X+ R/ t8 _* p- |
        Recursive Case:" C/ m& N8 n( _, l  c) P: T- v
    ) ]5 H  F* b" U; K: [
            This is where the function calls itself with a smaller or simpler version of the problem.
    ; m7 Y$ p6 E% O+ ]0 T
    5 ]5 {: c1 |+ z( C        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).6 M, @' K! t$ X' {5 P4 U( t7 g) E

    ; t8 c. I* l3 B2 w- a6 P" R8 Q: T, RExample: Factorial Calculation5 y* ?' y) w  y
    2 z! R% ^6 w9 K- P( C
    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:: G6 P' l' Y  U+ g, a5 q
    - X+ f8 _. y. K! Q" m7 c6 q
        Base case: 0! = 1
    # o2 `# Y; E8 D$ z8 }3 C% o
      R3 p+ I2 }& e, U* p    Recursive case: n! = n * (n-1)!1 b, n! E/ ?0 g3 N- a" i
    3 y# L6 ?+ O0 |" k3 l
    Here’s how it looks in code (Python):7 ^  C; d8 T0 k4 }
    python
    2 @8 f0 [, i* i; Q& \; k' N( C' T( r) }  m3 G6 j8 C. A
    ! h% n% t5 U) a. F' x1 A9 c
    def factorial(n):3 M/ n2 W: C: k# P
        # Base case
    # J! G. {+ T# j  A/ L    if n == 0:. i, {" ^, N, x7 c
            return 1
      X+ S5 n! S. X: d4 e, G    # Recursive case; U: `& Y& |; q5 F0 b
        else:
    7 M$ \* j4 O5 }8 V. [4 R% T        return n * factorial(n - 1)
    2 z. Y. p) T! O$ m9 i$ |, u# v& e% L
    # Example usage$ g7 J. R! k) A9 W$ g
    print(factorial(5))  # Output: 120
    1 @. d) y6 s+ c/ k  o
    / M8 ?$ q$ f& F" n1 BHow Recursion Works' i; q( ?; B4 ^6 Q! s' `

    . E* D2 J  w" |9 N7 E    The function keeps calling itself with smaller inputs until it reaches the base case.
    * R, p6 L3 e4 R9 @1 ?+ I+ c* j0 f. Q: ]! V1 q0 X2 ~+ U) {
        Once the base case is reached, the function starts returning values back up the call stack.
    " K# t8 b3 `6 c
    , \0 }1 t# d6 r4 s" |7 l' h    These returned values are combined to produce the final result.
    0 ]/ `0 I- {8 }0 C6 m5 k1 B1 I# R
    For factorial(5):' F5 Z' E8 f7 T; V1 C

    3 d; f% j* w& s4 \; o/ f$ _4 x5 \; @. j
    factorial(5) = 5 * factorial(4)
    : k9 e; x% n" Y4 z2 }factorial(4) = 4 * factorial(3)
    2 Q5 A' G4 e$ b( t7 [: }4 tfactorial(3) = 3 * factorial(2)
    2 [8 |  d2 {$ }/ v0 B6 ifactorial(2) = 2 * factorial(1)3 F: I6 `6 L% E$ t& k) R+ m
    factorial(1) = 1 * factorial(0)
    4 V  M3 r* e% t) Pfactorial(0) = 1  # Base case
    8 r/ J' ^* k, q1 z$ C0 ], a
    8 q* X$ K( N. I$ M& c" e  LThen, the results are combined:
    1 F5 B1 M+ U, K. Z: J
    7 M* J1 N! m$ Y1 e1 ]9 `6 {- [9 r0 R% K8 ]
    factorial(1) = 1 * 1 = 11 H& [. j# [8 q
    factorial(2) = 2 * 1 = 22 |8 p. q+ Y: ~+ k& r! ~- [4 O
    factorial(3) = 3 * 2 = 6( \0 M) Z: `5 d% e( W
    factorial(4) = 4 * 6 = 247 Q% @/ p: N" o; [$ Y
    factorial(5) = 5 * 24 = 120
    3 L2 ^* B1 n4 b! z' A# K( X6 t& q
    6 g- d8 f7 w& E: \0 zAdvantages of Recursion
    ; v# X" H6 ^; r- i& L$ i, ?' ?# P" z" v7 Q8 M4 l: Q2 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).
    ) G% o8 F: ~: ~$ o# B+ r: ?% m2 }  @7 _% W' z/ r8 c! e
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    3 }/ V6 a  L4 U' s( r5 o
    5 r' t( y- y3 s& n; ^' D: V1 JDisadvantages of Recursion
    - R$ b; A, N) l3 Y+ Z
    & O- X8 i3 o0 a0 @5 }    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.5 J/ d0 z. r/ q& {0 A
    ; u; s9 |) J8 w& j6 K0 y
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ s8 z. a2 h& k" D% n+ o

    * c1 L1 p) |+ @When to Use Recursion
      Q+ Y- ~4 ]% T) N7 s- T2 c; b# A. `2 N" v: o
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    3 s( W2 c& W: Q% ?& m+ Q( R0 N1 X3 C  c) r  i0 e6 w
        Problems with a clear base case and recursive case.1 c& A( i1 H5 ~! t0 B! p! t- _8 g) Q% g
    ! m( u4 O) P/ R3 b  W4 s
    Example: Fibonacci Sequence) `3 K: i# b0 d  d5 X# P

    : R4 d+ j; ?* T- L( k7 `The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ' @. s3 a0 [" o: n
    " I' Q1 M' Q( ^5 C/ e    Base case: fib(0) = 0, fib(1) = 1
    & e/ n, B7 i/ ^5 f7 T3 w6 l0 n; w/ ~# `5 d6 ]: J
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ! W' o# j4 {% \% S  r8 |6 T+ r. @  ?, z. Z2 l8 I. F$ Z% a
    python
    3 q+ s( W' i  W- Z( s  U5 ^: V4 F4 I8 ~) G( i5 L% n% q
    - o8 E3 U: s: ^5 u' M' E
    def fibonacci(n):
      ?  J: K9 M! ~    # Base cases
    # B0 R0 K3 M0 ^- k% i    if n == 0:8 A: {) O, P+ O, ~$ a
            return 0  P; m8 d: A# z9 w- a/ ]
        elif n == 1:8 D, ?( W9 v) J, M! L2 x$ `
            return 1, {% _9 T& f8 F& H/ V; {
        # Recursive case/ N+ {5 w1 i: _7 a
        else:
    5 K; D. }, g( T% u        return fibonacci(n - 1) + fibonacci(n - 2), [' ^6 f2 m1 L$ N% Q+ G* D

    - F6 _1 ?& h* E: ~# Example usage
    + s1 M6 E: ^. xprint(fibonacci(6))  # Output: 8
    3 V0 j$ w* E. E
    7 M& {0 N3 V0 b5 ^/ A5 WTail Recursion
    ; N6 y9 U; D, B4 r* F
    . x- ~% u8 S7 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).
    6 O5 y: d! {: U/ m2 ^* X* C2 x  |1 L0 s0 f  c- D: H: E( u$ Q
    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, 2026-3-10 19:16 , Processed in 0.059369 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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