设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 H+ V# |/ p% ?
    : z1 E9 O6 N/ g- S# _! g0 z( W! p解释的不错6 ~: i' ~. h: }, _# @. Q

    8 z7 W% N) N8 ~递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    . l2 l: S4 V# _5 a  n
    2 P( C* Q2 C6 H 关键要素
    % l3 t' j) X3 D+ B) }1. **基线条件(Base Case)**
    : b" i& c$ Y, @, p   - 递归终止的条件,防止无限循环
    ! k" s! A& g! R# i& g3 e   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    & z8 w9 ?0 p' S2 U. m
    ) o1 @/ D5 \- A$ I3 S; X  B- S8 Z2. **递归条件(Recursive Case)**7 d7 V7 F$ B" r' C5 e0 s
       - 将原问题分解为更小的子问题+ X( J& n9 X% o4 i
       - 例如:n! = n × (n-1)!
    ! c  f! ~/ M# a+ y9 R) o
    . N: Y# B, ~! w$ c7 S8 _5 Y4 W 经典示例:计算阶乘
    - N- Y4 J, \) _0 x6 ?/ vpython- m8 y% \3 ~) d' ]1 P
    def factorial(n):
    & T: l) m+ ]# S- k. `3 Z9 ]    if n == 0:        # 基线条件0 w7 j, ~2 Q& W) }) ^' R7 t
            return 1/ J( O# I: ^# I& R) @7 p' Z; T# G
        else:             # 递归条件/ H: V. o+ U, p
            return n * factorial(n-1)
    ' k* a1 I" p& J8 F- s, r执行过程(以计算 3! 为例):
    % m+ R) n; H. S/ `& Kfactorial(3)' Y6 w" n2 M! ?" E% a* L& m0 p
    3 * factorial(2)
    , M( }5 n) s. Y# I2 L1 I3 * (2 * factorial(1))
    & |3 p0 e+ B+ D. e3 * (2 * (1 * factorial(0)))
    ' x, d& O2 J, u1 w4 N3 * (2 * (1 * 1)) = 69 _/ e: |+ U2 U1 x6 `7 J: x( ^
    9 C7 {- Q+ ~0 A$ f! N9 Z1 b) j9 v' k& v
    递归思维要点% P* S' w9 U6 f0 Z; m6 e- W: s
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑" o; D; O; y3 a1 A7 y$ E% E" E
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    0 d' P4 }' _2 A3. **递推过程**:不断向下分解问题(递)
    ' L# R: _1 ]; i1 B" K4. **回溯过程**:组合子问题结果返回(归)
    ) r, h( y3 E2 p: P; E: A
    0 o( h1 K7 ?+ l! o' J& u3 F+ w 注意事项
    ' w; C  K& U: B必须要有终止条件
    , A$ q& J8 T; _! ?( w+ L递归深度过大可能导致栈溢出(Python默认递归深度约1000层)  U! J: b- K% I7 j
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
      v$ l/ p; V- t6 o尾递归优化可以提升效率(但Python不支持)4 U: ^" ]! \- H  N: E" `5 s! F
    3 G5 I+ c+ K! l: y! q
    递归 vs 迭代9 s! H- y- z4 a) b/ @1 N& Y
    |          | 递归                          | 迭代               |
    3 o( q* f8 `) Q8 O& |0 I|----------|-----------------------------|------------------|
    / ]/ C3 H' Q0 @4 P( t| 实现方式    | 函数自调用                        | 循环结构            |
    ! k; H, X( \8 s| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |; N1 t3 v/ d% w/ `; a
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |; m. w! t4 ]- |3 T
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    5 F2 L6 H% g: P5 Z- f
      Q- A: C: d1 p0 l! Z, y8 m 经典递归应用场景4 z# M) J5 Q9 n2 I
    1. 文件系统遍历(目录树结构), P/ H& |9 p: T* a: o& `
    2. 快速排序/归并排序算法; `0 s. L  o) [0 E
    3. 汉诺塔问题
    ; l8 S9 b( c" p% j4. 二叉树遍历(前序/中序/后序)
    9 M; o& z) e9 i& M  i) ~+ E! c5. 生成所有可能的组合(回溯算法)& V. F  O9 E  n$ T/ G0 P
    ( K* d. N0 j$ W
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 11:23
  • 签到天数: 3108 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    , l. h' `5 y6 B# X3 j4 E# U我推理机的核心算法应该是二叉树遍历的变种。
    1 X  }2 ^( J; o; X6 M" q8 A另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    7 y. o; E7 F7 B4 g9 [9 NKey Idea of Recursion3 Y5 z6 \" R1 W* S! A

    ' u, `' \% }/ c3 H! o+ IA recursive function solves a problem by:
    5 x( R& Q2 I, V( o
    ' S6 y6 D# d% [    Breaking the problem into smaller instances of the same problem.
    + s& `  i+ t3 _8 y3 ]0 m/ V1 I+ u2 O8 u: v
        Solving the smallest instance directly (base case).
      [7 z4 f6 S7 S; k0 W! y- \& O/ o
    * c: v2 C6 m2 q. a6 W; V    Combining the results of smaller instances to solve the larger problem.
    4 ], l' [7 Y* Y7 k2 M8 J, x6 O1 R3 l2 ?0 v/ X1 E# P3 _% p
    Components of a Recursive Function
    + J/ P" u9 r* E/ R" R; E) D
    9 l+ V/ B6 t( }# R# k4 o6 l" L7 C    Base Case:
    * P7 g/ }5 Y" t" a8 c* p/ Q: t8 t0 ]6 P. U
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.$ n  S; u  D6 C, l

    3 s7 ]: E5 \( i. G! Y        It acts as the stopping condition to prevent infinite recursion.) U1 Z5 V1 M  L  o

    6 l- z/ X' _1 y. f- v3 g        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    4 n8 F( o8 C; ~$ h& O. R0 g- |( l* E  m' q' x2 a
        Recursive Case:
    ; Z  b  w: Y/ Y/ F/ _- B8 I. _9 w; m/ s, c: N7 |
            This is where the function calls itself with a smaller or simpler version of the problem.4 |  O0 v) P8 `8 y

    ) u( x" L- R5 W) u        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).0 z& B. G. P: M* v+ P* _: E# y

    # a' V: }% @5 h3 I6 f' bExample: Factorial Calculation, E7 i% O' H; P" l9 M4 H8 |
    % K" A' O7 z/ [2 g0 u
    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:
    3 Z1 Z$ l# {0 }
    : U: E4 V; V) Q7 X1 T$ n    Base case: 0! = 1
    ; {0 l, b: R4 [# z! Q- G1 H- t8 d9 K, X% i0 l7 {9 B
        Recursive case: n! = n * (n-1)!* r+ x( I2 P& P& T

    . J) e9 d7 K/ OHere’s how it looks in code (Python):
    6 c( h+ f3 i7 D: N4 Vpython) ?! c. Z+ a! R4 e
    / ~$ o) I: ^1 Z  h! Z7 X7 R

    ) r8 X( B/ Q5 U3 B. ]def factorial(n):0 \6 }/ S" ]+ i% s: ^0 {7 T2 g% t0 \
        # Base case
    9 e. D: }$ x& H. _" {    if n == 0:
    $ b: V1 ]+ \+ l* Z9 N        return 1- z& ~# p4 r& V
        # Recursive case
    . w3 H0 a  n' w/ m5 n4 p    else:& X4 p) i- k6 |, y2 V# N! U
            return n * factorial(n - 1)# }, w: ^. z# G3 S
    . \8 N7 ]% k/ v, a2 K$ ?  O3 Y# |+ K0 t
    # Example usage% Q. Z% I' ]8 T
    print(factorial(5))  # Output: 120
    ; V2 n) W; A/ I
    ) m# S" V6 w; s4 O% U7 O5 wHow Recursion Works
    , z* l4 N; |7 L( e( S/ D% h* [! J& y2 h/ v3 y
        The function keeps calling itself with smaller inputs until it reaches the base case.  e# @7 t( _1 D7 h8 X: U$ w
      ]) I( }- I7 M# h: \7 Y
        Once the base case is reached, the function starts returning values back up the call stack.
    + Z) d- c/ q* Z: ]% _' r" `4 i  P1 i% N+ ?8 \! ]: Y
        These returned values are combined to produce the final result.! B1 W4 T4 r/ @2 L4 B

    4 ]  ?: A" H. ]' @/ Y- m, GFor factorial(5):
    % M  x/ j8 x) F
    6 r7 Y' F4 g+ o3 l6 D1 b0 H9 v
    4 P( A# X( m9 M/ F$ Rfactorial(5) = 5 * factorial(4)# V$ [( }( P2 |# W! x* C- B$ ^$ w
    factorial(4) = 4 * factorial(3)" |+ T' v  I+ j6 `$ c( D
    factorial(3) = 3 * factorial(2)  P5 C& a& C) k& r# o6 s: Z( _
    factorial(2) = 2 * factorial(1)' ~3 I/ V! M( f5 h8 k) j
    factorial(1) = 1 * factorial(0)
    , }& v+ w0 p, d, _& Xfactorial(0) = 1  # Base case2 N6 m! u  ^/ \5 K) M- Q

      z! c# I3 d0 aThen, the results are combined:. @- l; [) Z7 E+ b4 h! c$ @8 {& Q
    5 l1 {& f  @) z4 B3 H2 G
    % Z; ]! ?  h; }( h, V2 z% }
    factorial(1) = 1 * 1 = 1
    ! u/ r( c. l, m- f( S* ?factorial(2) = 2 * 1 = 23 j! o; T0 E! I8 R. ?/ r
    factorial(3) = 3 * 2 = 6
    9 B2 n. `, o4 Z7 Z9 Ofactorial(4) = 4 * 6 = 24
    ; l3 r4 l: u. b8 |4 p( b* Hfactorial(5) = 5 * 24 = 120; M% k( k$ K0 g
    1 k8 b. V# }( c: D
    Advantages of Recursion
    8 k0 r3 j0 t8 e, Q4 N) G) p) \8 K8 b) f# A' i
        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+ A: l1 ?; w# W1 z/ I

    ; P+ K# Z, w( W, H/ \, K    Readability: Recursive code can be more readable and concise compared to iterative solutions.0 i: m" p2 z5 ~  I4 F0 t

    3 w+ m! _  u: K, }2 sDisadvantages of Recursion$ [: A1 h3 Y. N% ~4 N" P
    : Q; y* X! O: o
        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.
    * B: {6 e* K! Z
    % ]; b  d4 z8 H, x! F( G    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    * H4 K; q: P. \% Z: m- i) k
    . B( ?5 U' P% K4 zWhen to Use Recursion: y6 G" `- L! F: Z5 l7 P* n+ J
      U8 ^- }- [! a- K' ]' L+ d! ]! Y
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ) J: E- K4 s1 O8 \4 o$ w
    - f2 Z5 O, S* ]1 ^    Problems with a clear base case and recursive case.. F8 X  h0 B. d. F. R

    . z4 n3 C0 ^& X' |0 xExample: Fibonacci Sequence# q9 L  F7 t8 m9 ^) P( p
    + }, X, r( D% w- \% ]1 p. [
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    * A  {  J% c( z, F; T7 [% ~$ R& E  l; c5 h' N" |% h
        Base case: fib(0) = 0, fib(1) = 1
    ; p; s( ?" G  H' s
    & q6 W0 ]9 |5 D% ^    Recursive case: fib(n) = fib(n-1) + fib(n-2); b. @7 ^0 y& _* H
    ; Q& I. ~2 x( D' A) h
    python& f! Y2 A# _. Z1 g1 c' L
    ; d, y2 T% J& m. g: o% J- }# [+ c0 q
    6 V. g! _# I: ^+ c
    def fibonacci(n):
    5 e/ ~! z- [* `5 _    # Base cases% j8 t* K& r. r+ u
        if n == 0:
    ( c# h; r$ w  i5 C5 e        return 07 |& J5 v: R; F4 I
        elif n == 1:
    ( R$ \( S) c6 ?0 s& T: p& z/ D$ C7 Z        return 1  q2 E0 D4 s& c& [) w
        # Recursive case: B, f7 b% y2 C, g0 [  e" a
        else:
    & b% [2 f5 ]4 x3 x( s- W        return fibonacci(n - 1) + fibonacci(n - 2)) A$ r+ a( c+ e' f
    ( Y/ F3 O! q7 G; A
    # Example usage
    6 f; o3 s4 v' T% k& D- Z7 p8 r+ p6 gprint(fibonacci(6))  # Output: 8
    3 Z% ~6 p4 M& ?; u8 g" z8 Q: G: I" S6 m$ U1 S. g6 l- u8 f5 z
    Tail Recursion; o8 z( }0 D0 A. ]. h- w" X
    * p, k# u! G6 N  z8 U5 s5 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).9 q5 E2 i$ T8 ^- j0 v
    % M& \, j! L, f0 n( B0 T# ?% w( y
    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 05:36 , Processed in 0.032956 second(s), 21 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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