设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    2 X7 M6 I1 T5 S8 l+ w* U5 ?6 Y2 ]
    + v$ P3 D8 C7 w% H解释的不错* L" X2 f$ `2 l$ @" G+ }7 L

    : m  H- ~6 X8 N5 ^+ |递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。1 [/ K7 V! S+ }/ E  j
    " Y" f% h; A4 L  L1 C; b  E
    关键要素: S5 I% @/ {& b* c/ S* Z
    1. **基线条件(Base Case)**9 }9 v' ?1 v7 I, ]$ [6 u$ g% F8 R: R
       - 递归终止的条件,防止无限循环
    0 d, l7 |0 R: d4 g) f   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    5 V( ]2 p: D" x% B0 h, o: v# S! i( R) f4 ?' V" u, z
    2. **递归条件(Recursive Case)**5 }9 J4 M; \" z% ^/ }: H7 U
       - 将原问题分解为更小的子问题
    # ]! x9 a# {7 f; c   - 例如:n! = n × (n-1)!0 h7 Y, D3 }' Y2 i! E- ^+ p
    7 U, |( \1 f. b: A5 k& A
    经典示例:计算阶乘# g# V" t3 ?0 q/ f6 R0 R
    python  ^. Y$ }1 w9 a# @% Q) v
    def factorial(n):
    3 Y2 j" d5 f$ d& ]/ y5 Q- t/ _# o    if n == 0:        # 基线条件
    - y9 e( o# {$ \3 X$ p! T) \" c        return 1
    1 v; j1 ]/ ^- U. t. @    else:             # 递归条件
    ; k; }) [) I0 m0 ?9 T        return n * factorial(n-1)
    + H8 w: S, z- r执行过程(以计算 3! 为例):
    # _/ X9 f! O* `, @' B8 y: \5 \2 sfactorial(3)  H9 I. }6 w% C$ j- m7 d' \7 M
    3 * factorial(2). A, n; j1 K% e: F4 q4 P( D
    3 * (2 * factorial(1))
    5 N& I& v7 b+ c# p8 Z7 `3 * (2 * (1 * factorial(0)))# i1 w6 d" m$ R  [2 v; U
    3 * (2 * (1 * 1)) = 6
    / x9 N0 r' k. T5 \$ W; y' R' h5 q
    递归思维要点
    ' N5 A( t3 {+ m, \7 K1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    " {) }+ z! v9 l& ?2. **栈结构**:每次调用都会创建新的栈帧(内存空间)6 d7 k" T- {; f/ _' y! _9 u- P
    3. **递推过程**:不断向下分解问题(递)0 Y' l( {9 l2 e" T
    4. **回溯过程**:组合子问题结果返回(归)
    4 j( R5 g% N4 O( Y
    8 n: S" f. Z6 M5 f  U 注意事项
    3 @5 p! C7 A! z- |' t& U必须要有终止条件
    7 r5 v. N2 f" P! c4 z4 k递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    2 K! h0 G0 E' l' U某些问题用递归更直观(如树遍历),但效率可能不如迭代: K1 `' A1 W- Q8 W' l; a8 t6 r
    尾递归优化可以提升效率(但Python不支持)0 J) s/ {' y! m  C" r" o3 B

    $ @% ]! w3 M- u 递归 vs 迭代+ x" p# D) C. }: w+ u
    |          | 递归                          | 迭代               |
    7 L/ N. D1 Y+ m|----------|-----------------------------|------------------|
    " ^" |' t/ ^. X. E8 z1 z% u, r| 实现方式    | 函数自调用                        | 循环结构            |
    ) w* F' s9 l7 o4 t9 g* k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |* Z: `2 D( t( j% h
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    $ E4 W: t( }9 e" j$ H6 @2 L- ?| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |" M5 [, c! q) {, {5 p& c3 |

    * N+ g! |' ^- B1 b: D 经典递归应用场景, z7 U! @* R1 h7 S- [
    1. 文件系统遍历(目录树结构)8 p1 X* K* V8 p( G  @
    2. 快速排序/归并排序算法
    + B% B4 o8 E4 Z: M8 A3. 汉诺塔问题
    - P2 g2 U- y% Q, A) q  I, b6 @' G" |4. 二叉树遍历(前序/中序/后序)
    3 w! M: y: o' v$ t+ y# P0 z9 \2 @5. 生成所有可能的组合(回溯算法). z$ K! f. l  [* ~  x* z6 T2 N: a

    7 v+ v, ^; o  O5 g* j( L试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    14 小时前
  • 签到天数: 3101 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 m7 V8 t" }9 w& w  b9 c
    我推理机的核心算法应该是二叉树遍历的变种。
    * p% }3 ?9 v2 |另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    ! G0 Q/ k. ~7 }- YKey Idea of Recursion
    - Q/ ?: r" @# v/ j- U- K2 N3 c3 Y' g( Z+ h5 D
    A recursive function solves a problem by:- D: r! }/ U2 L9 B+ [# Q

    / j; \5 A8 H( t. D6 a. M* o    Breaking the problem into smaller instances of the same problem.: k9 \5 E# d8 ^. D3 y0 R

    , N! j* e1 K1 E    Solving the smallest instance directly (base case).( b4 b9 L$ c) I2 U4 c
    0 v( {5 |5 A0 C, N9 }$ A0 @* J) ^
        Combining the results of smaller instances to solve the larger problem.! _! k: Q: p$ [- \) |

    $ \- T/ F' A, |3 H6 Y+ R9 w3 XComponents of a Recursive Function: C. r+ F/ H9 a: r- M' G
    4 ~& m3 `7 `& B* h* }5 y' W! M
        Base Case:7 G+ y- J% ]$ P2 F) Z  \7 |7 B
    0 O, @- {6 o7 X! q, m
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    0 w5 y6 R1 v/ L* a7 v
    9 r7 B$ h2 C1 J" W5 Z* L, g3 c        It acts as the stopping condition to prevent infinite recursion.
    ; f5 V5 b& k+ r
    ! H' f5 B; S# _( n, ]9 Y/ _( i8 q  D        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.) i6 Y/ \5 z0 d" q: e- ^, j

    4 E: h  G4 W7 _    Recursive Case:  f2 \. q1 F6 {$ T
    , G. ]8 f1 p! w, i/ d
            This is where the function calls itself with a smaller or simpler version of the problem.
    7 `9 I5 ?$ ~7 Z) m9 k+ b
    * I  T' ^& s7 B4 W' v( Y* Q        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    " D8 i( s5 |; N! ?: I7 \' J3 g
    ) [  [% `, p1 x3 S8 c5 }Example: Factorial Calculation( s: O, Y, q8 x, x2 x# R% V

    9 K" v& w$ }$ W, c' XThe 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:& L* A. v% i7 V0 y& Q2 P

    . J8 V% m' i; N- q, D# l+ S    Base case: 0! = 1
    & ]/ \! R4 e$ s' E; s( Z6 V; E+ h( {0 M9 M5 P
        Recursive case: n! = n * (n-1)!* r: Y5 A2 @9 c+ Y4 u) X
    ; _5 _+ d: P+ n
    Here’s how it looks in code (Python):! s& y) ]+ y* \
    python
    * S) E, Z. ]5 H  T! R0 {' n% z
    # S$ O# K' A; W6 q) N4 g2 o1 {
    4 ?" r  C8 r8 n, Ydef factorial(n):
    ( ^( z6 h( n6 {. B" D& P    # Base case
    ' M( l' ]( e% P    if n == 0:
    , g" J. u4 [$ ~/ ^' M! A) m        return 1
    ! B9 C% q* ^! J; a    # Recursive case
    0 h+ O- X" T% @& N    else:
    1 F& X5 p/ T* }  Q- S" f        return n * factorial(n - 1)" q; r! |  R8 v0 O
    " a( u+ V5 z: U2 X& g+ v4 _! V) k9 C
    # Example usage/ J: ~. p( b6 R7 [  D
    print(factorial(5))  # Output: 120  i8 n6 z* A6 \; z$ t
    / u6 o5 C7 V, k9 t: i! _1 o
    How Recursion Works$ H2 [+ }& V  J* w% C8 |. D1 L1 I

    / T. U' b: N, r/ s6 ^  Z    The function keeps calling itself with smaller inputs until it reaches the base case.- @' @9 a1 X) l( z

    & p! C. ^4 A1 H3 c; w7 s    Once the base case is reached, the function starts returning values back up the call stack.
    1 G5 n9 p! h& \  k7 x' b' ]& {; _3 e4 w
        These returned values are combined to produce the final result./ P$ e3 ~/ @2 }' }5 s' i8 B" [
    . z7 z1 k% s. G! m6 |! C
    For factorial(5):
    - E5 A) K. B/ d; i% W/ j, b' N' r$ s

    " }3 Z/ n7 P+ U8 v% Y' Lfactorial(5) = 5 * factorial(4)1 S: s) _& r: Y' Y  p. l$ f
    factorial(4) = 4 * factorial(3)
    4 ?* M+ S7 d0 ~8 T3 ^7 E5 b$ Kfactorial(3) = 3 * factorial(2)/ r2 `# `6 ]# _+ K& w4 R
    factorial(2) = 2 * factorial(1)
    $ C7 s+ |; e" p/ a7 o1 U* N) ofactorial(1) = 1 * factorial(0)
    " H: h- a  r0 o4 N1 h9 H7 y! M. _factorial(0) = 1  # Base case+ a# Y$ P. K3 Z5 Y

    3 e( W% B! ?) _9 CThen, the results are combined:8 d; _* @/ Z  r- y1 _' t; i1 `! e/ X
    $ j$ b  [1 z- s1 S, s: [) P% M
    6 Y- E6 X' V* ^
    factorial(1) = 1 * 1 = 18 f7 \; y: m. r& r- T
    factorial(2) = 2 * 1 = 2
    # d# n* B0 P; ^9 i6 Cfactorial(3) = 3 * 2 = 6
    7 U) w% ?3 y+ Afactorial(4) = 4 * 6 = 24
    1 }3 V' N6 ]* q! z& D8 Kfactorial(5) = 5 * 24 = 120
    - e) N2 B3 I( p5 g& r: K0 P, f, f0 ]. ~( h
    Advantages of Recursion# ]/ r' n. P9 i+ T- Y0 d
    ' |; l7 @8 p+ L. v% K$ T  E& M$ ]
        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).* D( L6 f. s5 c% z. F* t2 n
    & I2 Z5 B, L, J% y7 |7 U. v
        Readability: Recursive code can be more readable and concise compared to iterative solutions." s; b; `/ ^. [8 ^% X8 B" B4 r) d
    4 `7 ?! ^7 f# U% M9 ?
    Disadvantages of Recursion
    % Z$ N: G' D+ t+ N6 A' y# n( O6 n4 w4 r: j2 x" v+ n& `0 `
        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.7 X; V8 Z* |. b, W/ b
    - d- e' l1 `" y
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).# X- ?# u1 Z. l4 P/ f
    / s" n! A3 q7 n& M6 g
    When to Use Recursion
    4 v/ `6 S/ S- ?. f. ~. E) o* |" J( e; X( F; k# F
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    0 k5 V9 F8 w* b8 T5 _$ o
    ! s: |/ {; L4 w3 D$ t    Problems with a clear base case and recursive case./ r$ n7 p' S& n( X6 m  p( Z! Y
    7 h( X6 |) x6 T8 n# k
    Example: Fibonacci Sequence
    ) e1 G. [9 y' v  C6 l/ B( }
    ( s! t. }) g4 N# t7 e5 J2 J3 RThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:: v9 j6 h! Q. L% k% L) L8 t) G$ E5 m
    2 j$ y+ h' j5 j- x, g7 a
        Base case: fib(0) = 0, fib(1) = 17 Q3 c2 C' o  G' X! q) C) s, W
    9 \: K9 ]/ f) }5 o8 O
        Recursive case: fib(n) = fib(n-1) + fib(n-2)' P  O( H: ?2 W! S
    + }) s: p$ v. Q2 K
    python
    5 U( }) G! b( X& Z% w. S) I( J: b1 Q  |5 y9 U; ~/ w% v- p

    9 V8 h1 E1 y+ S2 ~! vdef fibonacci(n):
    4 E9 a- s6 w- F8 K    # Base cases% e' A' e- V* g! k7 f" l: `6 Q
        if n == 0:
    # }( x* {; G: U        return 0
    ) O* [; z5 y8 I7 ?    elif n == 1:
    ) j* K2 H) ?8 ?, y        return 1
    7 J! o& S+ j( S    # Recursive case& ?; \; C) W; ^3 \3 Z; ?
        else:
    2 X! g& o7 Q6 D% R: {4 N+ n        return fibonacci(n - 1) + fibonacci(n - 2); m# `, ~4 l: J. X  S. g* @6 H
    ) P6 M+ ?* u  P& _& c: z- v
    # Example usage8 j3 M' b! T( D6 c2 h3 B
    print(fibonacci(6))  # Output: 8$ v" X8 a" ?" L9 `! ]6 r

    1 V, K+ V7 ]" sTail Recursion
    : r8 O% R# B0 N( i. G, S9 ^, q% u) I/ E! p8 a: q3 |
    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).
    * l; z9 T/ s0 {7 U5 `  V- O9 u3 E/ H) k3 g' K% \' l
    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-11-24 21:32 , Processed in 0.031263 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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