设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 O+ E# ]! x0 t9 U" s- X0 J" S- E7 m3 N
    解释的不错
    + ?* w0 ?/ a9 `  d6 Y9 {' r  y3 m% ]; ]; D1 E; y  w
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。' p" R4 u, ?7 Q& V2 @' m
    + j0 h! \& y5 |& ]2 o2 Y
    关键要素$ [7 z5 w; Y+ z1 u. a
    1. **基线条件(Base Case)**
    - N  c0 U  D; }) o   - 递归终止的条件,防止无限循环
    + I- y6 y8 O+ i% }# @   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - M* i4 a# A! p. U
    ( P+ `. i1 \+ l9 e3 c  n* j3 y; D! L9 W" ~2. **递归条件(Recursive Case)**3 Y7 t. g! m1 Y* D6 S
       - 将原问题分解为更小的子问题  T4 q  E- f! Z; N$ w
       - 例如:n! = n × (n-1)!
    3 |* ~* [* H% \) o
    # c5 P, R; H" j; o' M' a 经典示例:计算阶乘
    8 ]4 M) Y; S1 w& Y( ~, o& Hpython
    9 d2 T9 X0 s0 ^def factorial(n):
    # _( e4 h5 F. ?: j7 j4 [6 @    if n == 0:        # 基线条件' S  U! ~* c7 p' k
            return 1
    " u7 E! X5 t, _7 _    else:             # 递归条件* y. T. d( e, h  e9 E2 C
            return n * factorial(n-1)4 w# o4 F. D: G& ^* k
    执行过程(以计算 3! 为例):' F5 U' ^3 s% h; Z' ~
    factorial(3)
    - g1 V# J4 `. p& v4 t" m5 @3 * factorial(2): C0 J2 f$ L: o4 ~- S( Q
    3 * (2 * factorial(1))  V" |: `8 k, w/ F1 m7 D
    3 * (2 * (1 * factorial(0)))0 W/ i1 B- j" h! J3 }: J  V8 q
    3 * (2 * (1 * 1)) = 6
    % U1 j  s9 y  n) C* \
    ) V* I: t- p# s2 t" X% F/ M 递归思维要点
    , E  u; c4 q1 ]! h1. **信任递归**:假设子问题已经解决,专注当前层逻辑( q! Y; T0 G- L6 L' ~- b* C
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    1 Z3 O0 E$ ?4 ~( O* ]3. **递推过程**:不断向下分解问题(递)- z# h. J- m2 A/ b$ }
    4. **回溯过程**:组合子问题结果返回(归)
    / N8 @+ H) D% N, A' x  g8 J+ }! ~& Q) N2 `
    注意事项
    0 S. I7 @7 ~# e  {必须要有终止条件
    3 Y" o! S* C6 Z4 G6 l2 B6 ^递归深度过大可能导致栈溢出(Python默认递归深度约1000层)7 i  t$ Y7 M  |- N0 m5 e3 }7 {: M
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    8 e9 t$ o. y+ t$ Q0 w# X尾递归优化可以提升效率(但Python不支持)
    % R( a9 G- L% G- [
    : a: Z; Q6 w# H! u8 W4 j' k 递归 vs 迭代
    # m; `2 r( b  b) s|          | 递归                          | 迭代               |
    4 M: W$ u) g5 w$ |( E- ?|----------|-----------------------------|------------------|. ]- }6 t' m; C# o( F: z7 i7 C
    | 实现方式    | 函数自调用                        | 循环结构            |
    * X7 G2 v4 q4 A- c| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ' |1 n: _+ _/ ~* s! ^' ~  K| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    7 W4 [5 m+ k3 T: J# l| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |, E2 `8 h" N/ f. D+ F
    , I" i7 V3 x+ {7 E& Y* _. d4 Z
    经典递归应用场景9 x3 |+ J6 b; x* U( z) }& T
    1. 文件系统遍历(目录树结构)' o2 S& x) {* J. i# J
    2. 快速排序/归并排序算法3 y& I, H& W- o5 F  c
    3. 汉诺塔问题1 s$ V; y" R" G5 g' Y, e1 j) S
    4. 二叉树遍历(前序/中序/后序)
    ! D2 n0 C8 T$ J% S4 G5. 生成所有可能的组合(回溯算法)" X) |3 T6 z0 E/ S1 _* f

    & M0 ^- h, g/ Y3 m试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 04:31
  • 签到天数: 3155 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,  E" j% ]" G5 [+ P! [! D
    我推理机的核心算法应该是二叉树遍历的变种。
    " }1 }+ V6 G3 @  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:
    3 o; G7 |& D0 kKey Idea of Recursion' a, Y3 o& u+ [. W

    ! o/ C% t" J9 P+ {A recursive function solves a problem by:
    ) m' {; o2 M/ B5 b( \6 T
    7 c2 j& @% v, s* r0 b# m7 d    Breaking the problem into smaller instances of the same problem.
    ) `' l* N5 t- u/ `: O  B2 S: l( f% S9 w$ ^
        Solving the smallest instance directly (base case)." ~3 A% L. q  Y

    ) p' T  H( d% e' k' T9 H/ P    Combining the results of smaller instances to solve the larger problem.# ^6 Q8 ?8 G2 q# y$ M. a1 C% _# T0 M

      `' i! I" z* o  dComponents of a Recursive Function
    ' p3 O* T* t  f1 L5 ~5 Z- P! X* e  ]) E0 @" ~' ?  Q5 |; N1 v9 O
        Base Case:
    ; u, v* D% i3 I7 b/ j- w8 ?3 m2 O$ l3 G3 T2 F4 g
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.7 b: R9 z! _. b$ d
    4 k" y0 i  `6 A# I' x5 k
            It acts as the stopping condition to prevent infinite recursion.
    3 _- Q9 o; e9 }1 W$ z0 \$ w8 O5 P; ]' W. q; Q) r  L
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    % F* w. |  c- b! F; Q) b8 U# G
    8 r5 A+ M7 C" d2 [* v    Recursive Case:; u! e0 [# w1 `  r1 c) B) W- [

    # a2 V& V) L; @' V. k1 ^" ^3 h        This is where the function calls itself with a smaller or simpler version of the problem.
    4 u1 ?1 T3 B' n( ~
    " C. N+ p$ f9 N        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    " z6 W& u1 a4 R
    % x8 N2 ^9 s! V) m, G% aExample: Factorial Calculation
    9 M. ]' ?% Q" [' W
    : v% n, K& P5 H& V* R7 R& d* P% RThe 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:) U% H* c# e2 r2 i

    8 i* U. O; P; `% ]  a. Y& {2 x    Base case: 0! = 1! B5 h+ A: \0 u
    9 _0 F2 A2 N  f0 [2 ~$ Z& Q
        Recursive case: n! = n * (n-1)!
    % R" f+ I. ?/ u2 }) U. h
    $ `' [/ d* m# u( m9 aHere’s how it looks in code (Python):$ p4 q7 L1 h; ]3 s5 ^/ ?% B
    python. r) O+ y. u# g3 u$ ?% q
    ( \, P( y1 @, ]% K
    4 y5 }4 s6 `# D) [: g+ U6 c' N: {
    def factorial(n):7 D/ V8 W8 B6 T' I. U1 w/ O+ r6 j& i8 O
        # Base case
    2 X$ }0 ^5 J/ Y7 |* ?  e    if n == 0:
    8 g1 K% ]* D& K+ {3 K1 g: g        return 1
    6 r/ N+ c. f1 P: y9 e0 d    # Recursive case
    ; R7 U6 Z5 W* ^1 W+ K1 e: l# d$ e    else:7 U6 P+ d5 @* Q8 L# Z( z& G! K
            return n * factorial(n - 1)
    + R+ q: w$ c' `! E( q) m$ B, K5 R7 B* E! @! g3 {
    # Example usage- s7 j9 ]7 y( S% {' q# ]- |
    print(factorial(5))  # Output: 120
    2 s' I- k$ ?& W. `' y
    / U, ?$ h# D  R# a7 HHow Recursion Works
    2 K& x$ H$ O% S- v) N2 O! g- ]/ J- {( _* T6 x( h% x- z' X3 I) N& v
        The function keeps calling itself with smaller inputs until it reaches the base case.
    + a" y3 Q# z# M
    1 ?2 ~! d0 P) G! G7 Q    Once the base case is reached, the function starts returning values back up the call stack., x* B: I4 _9 P1 o+ V8 z( @

    % c% Z  a, u, E8 `    These returned values are combined to produce the final result.! F/ L& w1 z. Z0 H
    9 o7 y% C! w/ l2 J0 H9 ?' P8 d
    For factorial(5):; Y, _  i0 C0 E5 {& N3 I& S+ Q

    ; @/ M% C; a1 j& @2 `8 A9 M
    . g# r% Y( v, ?4 r" `( z% Xfactorial(5) = 5 * factorial(4)
    * n' |+ `+ E3 h$ s  W% \9 _factorial(4) = 4 * factorial(3)/ o, |- {& {3 D7 H7 u) t
    factorial(3) = 3 * factorial(2), o( A8 B* k/ f2 n2 L" ~, C
    factorial(2) = 2 * factorial(1)- j2 m6 q/ c( r
    factorial(1) = 1 * factorial(0)5 g2 n+ E+ z/ p/ z+ o1 ^
    factorial(0) = 1  # Base case9 H7 o: ?; n( [' r1 o

    2 U0 I$ Y9 T; l7 eThen, the results are combined:( ~) X  ^, F) @, S
    8 U2 t6 g, U6 }$ O7 d8 {4 V; ~/ X
    ( \: T' v/ {) v( A  O
    factorial(1) = 1 * 1 = 1
    ( W& F1 |) {! t+ v/ s0 j/ wfactorial(2) = 2 * 1 = 2
    4 k! p4 z; Q( |0 _, f& L* d" Z9 ~factorial(3) = 3 * 2 = 6/ d% I" x$ ?* X$ y& n+ {5 ~
    factorial(4) = 4 * 6 = 24
    9 b3 ]( x* L! O. m' w' Rfactorial(5) = 5 * 24 = 120  R: |9 S2 ^- [+ f# b

    6 R1 f5 M* i- {3 z4 {# xAdvantages of Recursion9 Z* _# Z  B( o; R( K

    : s4 G( B6 J4 @0 p7 h7 ~& O    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).0 C1 R& ^8 x3 Z3 t$ z4 x# `

    0 y, g! K. R, h4 g) r3 Z6 z    Readability: Recursive code can be more readable and concise compared to iterative solutions.( C, I5 A  j) n% S  }0 q; V9 p
    $ N) Z; m; I% c) d' M8 _
    Disadvantages of Recursion
    ( l. e. K9 r4 V0 ~; ~3 }2 N/ k
    0 G. i" x! c5 X3 `# v$ N    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.
    ! }+ U, C: n4 \) E, R
    + R- D4 f( B' d    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ( C  o# z$ U" d: a
    ( R* B+ B( g, z* h  B$ h0 _When to Use Recursion+ R; [7 y4 H/ N' O

    + s0 \; D2 Z5 K0 ^; q' y    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ; {" h3 f0 ]/ L4 J# f+ {* ~* s# u6 H1 Z# y3 A5 _
        Problems with a clear base case and recursive case.  _: H" r! a- m* K
    ' b( X, ?1 T4 h" Y
    Example: Fibonacci Sequence; z+ h1 J5 T: E7 x( y# p$ z

    ! n3 z% f, i* mThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    % b" p' m4 I7 N2 k; N! }5 @* i! w, I3 ]. B5 _. G; u/ o
        Base case: fib(0) = 0, fib(1) = 1
    ( H( r- U/ P0 R& _+ ~1 _
    1 f8 I/ j0 n* J5 A    Recursive case: fib(n) = fib(n-1) + fib(n-2)$ l$ w  N" Y' j- |$ C

    7 W5 S$ t9 c6 I! {. O5 l! i6 T  }  q. Vpython
    " ^: ~& O/ n  U, `2 ^3 p) F) }1 U* }6 O4 ~) d. F# x  P
    * i8 A% |0 X4 B
    def fibonacci(n):; ~" D7 y6 h. x* C+ P4 U7 a
        # Base cases+ M2 T7 `, |# p* u
        if n == 0:8 V/ a) ^& g& F0 R% v! O
            return 0
    , R, j, b0 l2 v; n' |7 [$ M    elif n == 1:
    ( C* l8 R5 A; Z% |. k( h! Y        return 1
    8 I1 M' j8 z$ O6 z    # Recursive case
    ; F/ b) B5 t3 x3 ?* H& N* N    else:
    $ X  T2 t9 V; W+ d: `5 I        return fibonacci(n - 1) + fibonacci(n - 2), Z5 T- j) E. O5 N
    , l/ e2 a. g4 b" e/ V
    # Example usage; O# U- Q, F+ |! }' T; E5 v# b3 T" \
    print(fibonacci(6))  # Output: 8
    0 k, n, G7 T/ Q
    ! d0 o' ]5 j+ f, RTail Recursion2 x6 E: W0 l3 I5 L, {% S9 b
    ( W+ j7 \* p0 @
    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).
    , f) b1 s5 g* o: R7 ~+ p' c1 `$ y: {- ~9 z/ O3 R
    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-1-28 06:52 , Processed in 0.054775 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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