设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 , S6 o; P, ~5 F" p7 T: c: }/ h* d2 l
    8 h( R  _8 G2 v. @( A6 U0 X- q
    解释的不错
    2 Y9 h' e1 |* ]; v
    . I% J. Z1 X" i$ Z0 U: ^递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。% c* j; ?+ {: O3 R& ^# g$ k

    : Y- B# ]9 `! [" b2 h3 {$ u: n 关键要素9 b1 g# e* {: V+ C- Q. e" @& C" g( C. X
    1. **基线条件(Base Case)*** |2 G) M/ |* x& C9 Y3 x
       - 递归终止的条件,防止无限循环5 E  w3 h3 U- H* a" l: O
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1# J0 ]& [: w4 }. @
    3 g: W) H# ]# a& s
    2. **递归条件(Recursive Case)**
    + I, Z# O2 q1 u5 q9 l: y1 S  F3 y9 d   - 将原问题分解为更小的子问题
    1 s; G- ]2 k( Y$ V* e8 _# Y   - 例如:n! = n × (n-1)!
    9 q$ p7 r/ N% g/ I, V  I
    * b5 ~% E* @9 s; R  g 经典示例:计算阶乘
    3 G  c& Z, {0 Fpython, U, t. B+ Z  {. u6 q# X: }+ s
    def factorial(n):- z" k1 E# K2 H  j; A9 Q' }# a
        if n == 0:        # 基线条件4 z+ f1 r* p( @2 \7 `. Z
            return 1
    + [- F* x  E& m5 Y* K/ ]& C3 D    else:             # 递归条件
    * M& p' D# M: |$ o) m        return n * factorial(n-1)
    ) M0 H( ^5 ]$ [! m; v执行过程(以计算 3! 为例):
    6 j# D8 ^7 R# m2 B2 [' @factorial(3)
    1 J$ l4 r* o: c+ \0 U3 * factorial(2)
    9 t' {2 e$ m2 e" f6 Y+ x3 * (2 * factorial(1))
    / f) i( J- p+ I2 G  ^5 a3 * (2 * (1 * factorial(0)))
    ( u3 E/ [. b( I6 @3 * (2 * (1 * 1)) = 6
    2 i$ P8 c4 |# n( N  W1 L3 R
    # Z& o! h" H# K3 X' F1 g/ e, n/ W 递归思维要点
    + Y: b9 K2 u, p- }1 m- Z" F, C1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    - g7 @( c$ d9 K3 N9 N6 Z2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    8 G8 ?; y0 q  a# f% p# ^3. **递推过程**:不断向下分解问题(递)
    , t  D5 E; K: r) G0 L- H4. **回溯过程**:组合子问题结果返回(归)% Y3 `5 [# t* Y

    5 H9 F* B  f, j+ r4 P, c) w 注意事项
    : ^$ u9 e" V* [: @+ a* Q) i必须要有终止条件
    ( i/ c& h1 l$ k0 z  u" K$ x递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    3 d( g2 P7 ?% C: ?7 V. k某些问题用递归更直观(如树遍历),但效率可能不如迭代/ X9 C  ]' O8 t2 z
    尾递归优化可以提升效率(但Python不支持)1 R7 z5 O0 y6 W  f; A5 @- a
    6 R, }3 }! O% R/ `
    递归 vs 迭代
    - e+ F0 b! Q/ s7 i1 @0 x4 M|          | 递归                          | 迭代               |6 z6 `0 T) q: C* r3 b. X
    |----------|-----------------------------|------------------|3 }( P% Y3 }6 `$ W+ C) K$ a5 `: _0 ^
    | 实现方式    | 函数自调用                        | 循环结构            |
    - \8 h- F7 s- V/ k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |% U! I& S. L/ Q7 L: F) B3 Q' y4 u
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |! I' x) A0 g! k0 t" U; y
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    # w2 E8 K# ~  K4 Y" G5 J2 L! v- E* Y4 i7 O. |
    经典递归应用场景
    & v  X7 q( Y4 N, |; R: w1. 文件系统遍历(目录树结构)9 G. k8 p! B! U" G" v- ^
    2. 快速排序/归并排序算法
    6 C" C/ w* E% j- \3. 汉诺塔问题% g$ V3 |+ A" w' K. v
    4. 二叉树遍历(前序/中序/后序)/ B/ o- e% ~2 j6 U
    5. 生成所有可能的组合(回溯算法)* V; ]% `6 o$ z% D

    ! w. N/ Q9 |; q$ [6 N* V试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    昨天 09:20
  • 签到天数: 3234 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 M4 d4 Y0 I3 s, J/ O- R% ~
    我推理机的核心算法应该是二叉树遍历的变种。
    5 d4 D  [6 }8 W- L另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    & o; ~9 N- d* e8 P2 C5 e  zKey Idea of Recursion( Q9 t' H0 O% f3 `8 B* ~8 y( G
    ; q, k' H: o, c0 U) p* ^) j
    A recursive function solves a problem by:
    $ ^) l# a/ F- Y# B8 {0 O& J! ^- v2 \5 g2 q9 R8 P" O( A5 A: s
        Breaking the problem into smaller instances of the same problem.
    + h# i/ ^9 T+ D1 ?
    0 x9 y# Y% `. i    Solving the smallest instance directly (base case).& E  j* d- G9 b4 J  V& q7 F% _+ N

    $ q6 X% _0 W! ]( g! W    Combining the results of smaller instances to solve the larger problem.( L: t* {. Z& e# O* P" e

    2 m) @$ A3 X' X& mComponents of a Recursive Function6 ]7 b7 t3 t+ a, P1 t: |$ x1 d

    ' s: y' Q1 u1 ?+ Q$ X2 ^. Y    Base Case:' S& X) T' b5 L8 u) Q; r) N
    % I$ i  A4 I- s( }' u
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ( u& {2 |% o9 _! X; P1 u/ F# [
    * J: Z7 x/ {6 ]) z6 m. T8 `        It acts as the stopping condition to prevent infinite recursion.- m- I/ l3 ]! ]* E0 n
    + p4 F' {* h& j% N" T& V" }3 `8 ?
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    4 n% |8 S0 d3 J7 l
    : L0 k& C/ G& k6 J8 D! t1 r1 Y- v- E    Recursive Case:
    % j% N/ j* y- l5 l- Z( G% u" }2 j: ?; T. f# m) w
            This is where the function calls itself with a smaller or simpler version of the problem.
    , ^8 G4 S% L6 n9 v/ S4 x7 {+ M  W  p" I3 F$ z: E' b
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).& f" _2 I# s% l* T7 j1 T& N

    , M; o2 M# H" Y+ M0 gExample: Factorial Calculation
    ; O* N7 L' K! C0 _# x) x! w9 M# |0 h
    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:8 @! P, F/ f! {# [, @2 X

    1 t0 K& Z2 b- H. f" Y8 [    Base case: 0! = 1
    3 M4 t6 @+ B! a4 j. R4 R; v
    . t+ r7 _, U7 R8 x1 O    Recursive case: n! = n * (n-1)!7 [% v7 Q" t0 o( A" l. L4 c' i
    3 K6 M1 ]0 ~5 ^
    Here’s how it looks in code (Python):
      i9 w3 e- ~6 ?2 ?! j* x  G: Wpython- z- A1 p  G3 G) e: M
    ) ~; f$ m0 e' M2 L. S, i* [  `1 E5 s
    $ j  P* q1 v9 M5 S* ?# o3 X8 Q
    def factorial(n):
      V3 P  F" |% e! y/ K& g    # Base case# ~0 Q( R6 R  b$ n& J: i# U6 s
        if n == 0:
    4 z7 n  j; K% X& F5 h6 ^7 H( Q        return 10 W0 u! I% v: F" m
        # Recursive case
    # K# v6 s& H: B! B. r    else:
    2 o5 B. r5 g3 E7 x6 R        return n * factorial(n - 1)
    # \4 Z' h2 `8 _7 A! @7 ], s! r# s, g
    # Example usage3 @3 b. p5 n' v* S" [
    print(factorial(5))  # Output: 120
    9 o5 W( [- q$ E0 i9 ]- i
    ( q: `( j  e* S  d5 K/ }% e) [How Recursion Works2 k+ i  M- Q  e3 R5 F4 ~

    + G1 V8 r0 F8 E# x    The function keeps calling itself with smaller inputs until it reaches the base case.
    * |2 p6 U$ N9 I, a' Y/ w" O% A( ]7 S+ O$ j1 W
        Once the base case is reached, the function starts returning values back up the call stack.
    ! P% S5 j3 ?* k1 E% O( q! v! l3 n7 {; ]
        These returned values are combined to produce the final result.
    : k* N8 L+ }4 W/ a9 f  |+ B. n9 f; Y* h% Q5 t" Q: n9 I
    For factorial(5):
    6 Y, V, P, c3 ?$ U
    6 e4 k4 k( f9 H( O! f" p/ v) J2 l
    factorial(5) = 5 * factorial(4)
    4 p; s% U" {' X# |factorial(4) = 4 * factorial(3)0 v% K  Q7 p8 G+ s- ?' `6 ]2 `& t2 X
    factorial(3) = 3 * factorial(2)
    * e/ S3 Z. H2 ?6 l6 y9 g7 D0 Z) ~2 Ofactorial(2) = 2 * factorial(1)
    ) f- I& }6 ], g8 i, O) w/ Vfactorial(1) = 1 * factorial(0)7 ]' x$ g6 {0 c! _4 r2 C
    factorial(0) = 1  # Base case  J! l* f* }" G. z; c  X" |* H
      ^$ R9 l& Q" @' g/ g  Z2 }
    Then, the results are combined:
    9 N% F& p1 |1 Z; i: k( D5 q. l3 c

    9 Y/ d; K! X9 X5 a1 Y( b- W5 \9 |factorial(1) = 1 * 1 = 1
    3 i& g- D# M/ f9 A7 w+ b& Xfactorial(2) = 2 * 1 = 2' |' M* E) L/ s6 z$ V
    factorial(3) = 3 * 2 = 6" ]7 Q$ F3 T7 A) X# n' J
    factorial(4) = 4 * 6 = 24& S# I1 i4 Y, G& k) P
    factorial(5) = 5 * 24 = 120
    # M+ ?% H1 [; ~8 |' T
    5 z; P4 L9 }4 }$ ]: C% j( TAdvantages of Recursion
    % P7 ?- V  Q$ t  ^; W2 @
    4 v$ k) K! _' e8 K# V  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).5 K! ?1 W. {" }
    # s9 ^' n/ u. K# C7 [& w
        Readability: Recursive code can be more readable and concise compared to iterative solutions.9 t# Z  i; C$ C# Q& D1 O6 v

    2 w4 }8 o& ]2 x, t4 Y1 {# bDisadvantages of Recursion
    * ]& a6 |0 [6 f1 i  V
    5 }8 e* O0 f+ C9 u8 F    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.
    0 E9 B2 y8 _. V, _2 w/ N% I$ R, X  z, I& W# ~& G# \
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    , v8 |+ R' e/ ~3 W
    + m' T  D# p! e) {- a& zWhen to Use Recursion" P; `+ L+ [$ |! x2 w6 ~9 C; T! H
    ( \, }& d% P! X/ J+ n, t
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    3 j$ N, U; q5 E, S5 Z: ~( \7 W- c/ n* b7 a
        Problems with a clear base case and recursive case.
    % l5 [& A) {) ]
    ' T! ]* U+ P+ i# y" aExample: Fibonacci Sequence
    - w1 C# x$ |# h8 s, p) b
    # ~- t1 {/ p/ ^/ u% Z! m# ZThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    + w7 U* f& P; ?4 ~7 E  ~5 c  w% B7 H* d' b; w/ u" f; m: E/ x
        Base case: fib(0) = 0, fib(1) = 1
    ) k7 E  A7 D' O  C# s9 j5 s
    3 N  I5 J. |+ X    Recursive case: fib(n) = fib(n-1) + fib(n-2)8 R% f% U  m( W8 {- ^

    # F' y* I# y4 _" c3 bpython4 z. _, J# ~- @9 _7 c, x
      e9 x  H. t& w
    ' ]+ }( n) c' U) Q
    def fibonacci(n):
    0 L% z& m6 }. Y/ n0 ]4 G$ S. S    # Base cases; _* s) ~! H: s9 E7 ^6 b
        if n == 0:
    ' k& p0 ^6 m: k# Z6 f" A        return 0) W# R8 W2 |- [* W+ K. H4 x  S
        elif n == 1:
    & e+ v" k9 z5 z1 k7 u! E' m; H        return 1
    ; F3 G$ U9 e1 D+ u    # Recursive case
    8 A5 L; q' H& Y4 R/ _% f0 _6 t    else:
    + j5 ^% W8 V& t, X7 W* g  @        return fibonacci(n - 1) + fibonacci(n - 2)
    - {* v# I& B( P+ g
    7 U6 g+ ~: p4 z$ ^0 ]9 T5 I# Example usage
    % j$ D  v, {$ k: B- p- ?print(fibonacci(6))  # Output: 8- a% a/ H% e# J

    + ]: {: {8 s" h+ l- N& w6 yTail Recursion
    6 g% h! f* g8 a* s. i. u( y! n" ^* W3 D  l- z0 R9 v7 ^) P
    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).
    ; }! V9 ]" j8 ?# y4 h# b6 f+ {& Z# [' q3 Q) U
    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-5-9 12:20 , Processed in 0.056471 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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