设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    $ c( [- P# K( v& ~  c0 Z2 Q3 B6 M) l4 o
    解释的不错
    % J& {5 F, z. K) C, [7 D5 u5 H. Z
      b9 r1 b5 p; y- Y2 D9 x% q* o递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    3 Y, L: V/ `+ P/ F& C# b- P8 |, Y( \3 T# n. P7 Q& ^
    关键要素2 d* j, H4 v' L; {% R7 W7 H
    1. **基线条件(Base Case)**
    ) b, {0 y  a+ ~, _' t) T   - 递归终止的条件,防止无限循环4 f1 z. g7 j' r
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 14 m* T2 z# y! [/ d0 W, G- x/ U/ B
    1 a2 j! s6 N8 h; C
    2. **递归条件(Recursive Case)**/ ~* p. \( m8 _% ]: i2 w
       - 将原问题分解为更小的子问题  l6 U2 G  A# }& H3 }8 c
       - 例如:n! = n × (n-1)!
    5 N$ W( B( j( Z) d  g. t8 X; k6 E& X  X4 h% {7 n& ?8 k
    经典示例:计算阶乘
    / c5 X9 _1 |7 N4 N/ {2 p; |* D% `python
    9 x) z! {2 Q4 {' `+ V* Q3 Ydef factorial(n):: A- D# V8 ?1 w( _- W1 w! j# Y! o
        if n == 0:        # 基线条件
    ; x9 l; s- ?6 b$ g3 }        return 11 A# M% d; B+ L
        else:             # 递归条件7 Y4 o/ p* [! P( M& d0 z
            return n * factorial(n-1)
    & J8 b+ Y  L3 c1 v执行过程(以计算 3! 为例):1 h& d1 h- [3 g8 k' P$ o* g5 @+ ?
    factorial(3), D0 u+ K4 [+ G2 k
    3 * factorial(2)" T# A  p2 r! y
    3 * (2 * factorial(1)), ^- r* n& v8 V& {6 O
    3 * (2 * (1 * factorial(0)))! d$ Z5 i5 D# F" d/ L% K% R
    3 * (2 * (1 * 1)) = 6
    1 Z! J3 Q8 {+ K6 ?" y2 M  j/ s
    0 m6 c8 ~2 R" ^! E9 s# m+ y$ e& f 递归思维要点6 q4 P( W, n' }; T+ p; g
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑# m, ?1 P3 g# V; x1 ?5 i
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    4 m4 `% G, D4 d. W3. **递推过程**:不断向下分解问题(递)
    0 f& q# j, V, u/ K' l4. **回溯过程**:组合子问题结果返回(归)$ s% e$ j( h; D' K% U* @

    # L7 ~  I  Q3 s3 p3 X 注意事项
    9 v7 c, f9 x* |2 ?, g2 Q; ?必须要有终止条件  W7 F+ k' R5 r3 Z
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    2 V$ v  Q8 Q5 w6 J9 ]# Z: I某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / W& }2 A9 ~. E6 c: s; Q尾递归优化可以提升效率(但Python不支持)
    1 [( w* z$ h! v1 h2 d: A- a2 [. X" D, l' l8 x$ o4 y2 j
    递归 vs 迭代
    7 b1 P6 _: A, F5 ^|          | 递归                          | 迭代               |. b& M/ z; ~6 p( v: p3 G
    |----------|-----------------------------|------------------|
      m# s& N; k/ r  {8 ~. D4 q| 实现方式    | 函数自调用                        | 循环结构            |7 G+ O$ Q$ T! s$ {
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    5 F# p, a& r0 @4 N0 w| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |  h1 }) _% K' u* h3 Q8 i, G! a
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    - S$ O( Z( U# \' t8 g7 d/ H5 W3 n+ k3 _! T" Y2 l0 R9 Q
    经典递归应用场景
    1 u7 z2 O0 q9 F! u$ R1. 文件系统遍历(目录树结构): h4 X3 m5 C; ^5 j
    2. 快速排序/归并排序算法
    6 e. r4 m3 L8 b% S, e3. 汉诺塔问题
    ! t) ^* b" _7 T2 V/ G4. 二叉树遍历(前序/中序/后序)
    ; J3 I/ h& x: D! X! V& Y5. 生成所有可能的组合(回溯算法)
    - o* R2 I" u- W9 K0 c$ @1 `' K
    6 A& S+ y, F3 z( o0 o9 y# E试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    半小时前
  • 签到天数: 3174 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,- O7 J5 V: p" |# D+ b) A; c
    我推理机的核心算法应该是二叉树遍历的变种。8 T# y3 [2 b. ~* B1 z8 k
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:& @6 x8 i& b; B8 K7 k/ w
    Key Idea of Recursion
    & q: X1 @* M: X1 Y
    * d, N' K" T, H/ B1 \0 P# rA recursive function solves a problem by:% y9 h% r0 r) m  r5 f% C. _

    + k1 c; X9 C; W4 q! C    Breaking the problem into smaller instances of the same problem.4 u$ R; a: T; o2 a4 e' h1 o
    + R' |5 z- T/ P
        Solving the smallest instance directly (base case).- O  m8 B' G( D4 G# p  ]
    : c" g+ f; f- ?# D
        Combining the results of smaller instances to solve the larger problem.
    5 P: H+ y5 V0 j( }9 ^" J- o2 \
    8 R$ g/ r* f. \* C! \Components of a Recursive Function7 ^+ Z- t; N0 D1 O7 Z

    ' M9 D) d" ^9 ~( q    Base Case:
    " O: E! b$ f$ ]3 o
    : {% v  u1 g" \        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ) o+ c5 q9 T" \$ a5 {* @  \- T8 e! @2 d2 E
            It acts as the stopping condition to prevent infinite recursion., G. y3 r5 ?6 Q6 C$ B
    / ]& Q" R$ l( _) R9 N: {6 m4 k; x
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    - w, \# t, P* M" f3 f! U( T2 p" M% c" I( q) l. K
        Recursive Case:2 v1 h# o: H' c$ \2 D4 e: P

    - \% A" Y$ V1 R% I% H, [. `        This is where the function calls itself with a smaller or simpler version of the problem.& \6 D" L5 r6 N( k5 K
    & W; f% C% c* R9 d0 V& T
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. G8 k3 v" m  i4 q; A" G8 C

    4 ?% s( p; y; aExample: Factorial Calculation
    4 s0 Z/ n0 Y$ q  [. ^% ~4 S$ c
    7 O: d( w9 ^( v& Q1 x  w+ vThe 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:
    / z" a3 f: B+ R7 L* Y# _) S+ h" \' L' I+ A2 D/ p1 l; J$ M7 l# O
        Base case: 0! = 1
    / @& _; k7 r" o5 F
    ; F# ?0 U# C; n) V* s    Recursive case: n! = n * (n-1)!
    + ^! u" X$ S4 c% j5 Z( L! Z7 T3 N
    Here’s how it looks in code (Python):
    - Q  E" ~' p. C/ H# v& ypython
    2 w, M- d; A# y( h  u( w( J1 Z) U0 M, d! G3 B" P# c

    " ?, D5 y- b" Y! ^$ R9 Xdef factorial(n):7 v4 N5 M, I- I5 x! H9 g3 K- r! [
        # Base case
    ! l; C7 \; m" l* V3 S+ F    if n == 0:
    0 t1 @6 S8 ~3 @" o        return 1
    & P  ?% Z" c' l& V4 f! W    # Recursive case9 Q+ y, d9 f" j7 e( Q, M
        else:  M% w4 e# k: B" _. v! F$ J* P
            return n * factorial(n - 1)- s1 _7 u8 Z3 `$ a6 h

    2 @( j9 J1 y7 T1 |& m* b0 y# Example usage3 N+ W9 _- m8 J  L
    print(factorial(5))  # Output: 120
    % i/ J' k* h! ~4 d, X1 f3 z8 [2 u, u
    How Recursion Works$ o& C  D4 R4 m! u# l7 f( g
    8 D( t, z+ P3 D; Z; _
        The function keeps calling itself with smaller inputs until it reaches the base case.
    % O* h* G$ f! f" w
    " {+ m2 W8 R) F& F: [' J    Once the base case is reached, the function starts returning values back up the call stack.4 p' L5 M! v4 X2 d# a

    0 ]" T: W! {" r" w# l    These returned values are combined to produce the final result.8 b8 s( B, O7 P

    $ j7 y7 H! I9 {! H' v( l% MFor factorial(5):" k  j" |" i( E7 o0 B9 y% `
    ' G( c6 Q9 d  L- G' H+ s7 U
    8 F8 y- q1 J2 D( S0 y& O! Q
    factorial(5) = 5 * factorial(4)
    2 z& H+ E4 `7 I# Pfactorial(4) = 4 * factorial(3)
    ) l) F! G2 k) ffactorial(3) = 3 * factorial(2)! u  O: u0 [- z
    factorial(2) = 2 * factorial(1)
    2 h$ K# h  u/ @4 r2 B7 k* J8 rfactorial(1) = 1 * factorial(0)
    - d3 e7 V* W5 O5 ofactorial(0) = 1  # Base case& i# L1 W3 }) P7 _+ \! K8 z

    , X: p$ Q# w) @  A5 x. R7 KThen, the results are combined:* r8 Y* y; q- p
    " A- k+ M$ J" ?* o

    ; f% ]5 H/ o% ~" Xfactorial(1) = 1 * 1 = 1
    / o0 n( `$ b2 h, u! [' yfactorial(2) = 2 * 1 = 20 X& r3 c3 ^' _2 v$ V9 s7 q
    factorial(3) = 3 * 2 = 6
    * ^3 y9 \$ _2 l$ w" s% I+ Cfactorial(4) = 4 * 6 = 24* h) N' q8 w/ R8 {+ F
    factorial(5) = 5 * 24 = 120  T5 l' B! J8 G% M  n6 r1 T0 L
    " X0 b$ M+ }% E% M
    Advantages of Recursion" h1 a; O. r4 P4 m" f# v3 K" \+ `
    / Z3 z$ W/ [0 g+ Z$ C. V
        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).
    - f: S# p. O/ L7 R& B  b" a: a' Z
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    - _, W" e% o6 O3 h) \$ z, w4 w5 J0 Q+ g' h  }5 ?# z
    Disadvantages of Recursion5 B+ U: w2 e5 B% @6 b7 H8 m
    . Q8 D  J7 a. T# R/ l
        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.
    8 w" {! B) v# z- |+ L: G
    $ i5 {8 [4 j8 e; }* L3 o! x    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ; W( S$ X3 L0 k' w1 a+ [+ V
    # J  f1 z& K& S2 l/ p1 }# lWhen to Use Recursion( o* ?% E% o9 d/ c
    ! X% ~: g; Y8 t8 ]$ o1 [- x
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).7 D+ j3 X6 B: \( P( T

    . p5 I* [% `! [8 c0 @* Z! {    Problems with a clear base case and recursive case.
    0 t  ^+ X9 d! h; t0 X3 L: N9 f$ z7 _, u6 P& ^4 X
    Example: Fibonacci Sequence
    ; l( @# _3 j& q/ |) q0 Q6 w- [9 a# b3 s
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:9 u# i. L) ?/ O+ j

    + Q- S, q1 A2 u# i. U; a/ |    Base case: fib(0) = 0, fib(1) = 1. c; V. K$ [: Y3 P3 V

    7 q) ?- T  A7 P" n- h) r/ t3 ?! E    Recursive case: fib(n) = fib(n-1) + fib(n-2)* r7 a6 c2 v7 F' y
    7 l/ m& f' P% S# E8 {: o7 O) [1 z
    python
    ' k. y, e5 N" z) z5 W
    . S1 @4 q* c" u
    : J* o. i" Q2 D( |; C0 Tdef fibonacci(n):" p/ t4 k9 _! Y: Y, m" V$ I+ y* f
        # Base cases+ U- c' G2 J& x
        if n == 0:8 m) S& ^7 ]- S" s( v: \5 a4 L: R
            return 0# b* z4 U9 S5 m+ h! g* P
        elif n == 1:
    8 J2 ^# w$ m* a$ E* j- |' Z' l" H        return 1
    ( j2 e3 m: Y! `( g2 ~' x    # Recursive case- F  `, _8 |7 x0 f/ E1 Z
        else:( C! F7 E. i. ?% }/ V$ R( B1 n/ K
            return fibonacci(n - 1) + fibonacci(n - 2)
    % w% S  H/ \: N. Q
    4 Q0 [8 n( N5 c# Example usage; r3 X6 z: \" S: i) R8 q: Q$ E
    print(fibonacci(6))  # Output: 87 |. e  G9 G2 R$ X$ A

    . b5 Z# b9 S. F4 FTail Recursion# B# n9 M7 ]. f
    # m+ W9 L3 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).. ?" I0 X2 K5 |
    9 z1 e9 l& i, X' K4 ]
    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-2-15 10:22 , Processed in 0.057337 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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