设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    & k. p* R/ H( T: _
    ! T$ j3 [' l! Q4 {6 L. V1 A2 U解释的不错
      A+ K, W, }; P! z) e9 P  E0 N+ |" H- y# `4 v
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    : ?8 e6 X9 z/ Y7 v( B, b4 |5 ?. d& ]0 i' N: f! E/ I
    关键要素
    , r3 T8 _0 q3 r) z1. **基线条件(Base Case)**
    5 {, k0 X' L6 c3 W   - 递归终止的条件,防止无限循环
      d3 ]  o: l, j2 h, d   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    $ g2 ~8 W: ?7 Z* Y7 Y! z+ V9 L4 ?+ [% J* ]# F* U
    2. **递归条件(Recursive Case)**
    : m* K$ Z, k% W0 f* e   - 将原问题分解为更小的子问题; _$ Q( p; H8 @
       - 例如:n! = n × (n-1)!! o. H; b/ @/ ^  w! i& X
    7 R5 y; ^) m8 `& h* J
    经典示例:计算阶乘
    ( ~% D' I9 \* qpython1 |& G2 [! Y( N0 i) P
    def factorial(n):0 i% y! E6 [6 c5 t  P, c7 v
        if n == 0:        # 基线条件7 P5 J% Y; u4 D* {
            return 1. B/ |& R6 h% `
        else:             # 递归条件' h/ p2 X/ E1 e3 s
            return n * factorial(n-1)+ D$ v* u0 f4 K, _  _- ~
    执行过程(以计算 3! 为例):( x! A# r  U0 ]- S; W( h4 x
    factorial(3)
    ' ~5 G# p6 @1 @$ m" [3 * factorial(2)$ {( x/ f2 n/ Y3 o8 {& f0 s
    3 * (2 * factorial(1))
    4 V. \2 B4 \* J3 * (2 * (1 * factorial(0)))
      j! N( G( {; b; X3 O- a3 * (2 * (1 * 1)) = 6# j9 D% z' y( N' c0 W8 X( e2 a

    3 W: [+ ~5 p9 e4 A' B 递归思维要点! s0 S  l8 E( ]
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑" U% G) ]2 w; S3 @4 H! y2 m
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)) a1 Y; L1 @6 M1 O) U# o6 u) L
    3. **递推过程**:不断向下分解问题(递)' `# @; B) H4 y; {
    4. **回溯过程**:组合子问题结果返回(归)4 i7 t, c7 t, g9 b0 Y  c( R6 _1 n! k

    0 k8 j9 |' r" `( ~. ~5 O3 H 注意事项3 O  Z! a% }7 q* |4 g
    必须要有终止条件
    9 |$ J( j9 M( y; L7 S) y; i递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    4 Y. _2 {  c! B" C* j0 ]- v) H某些问题用递归更直观(如树遍历),但效率可能不如迭代
    : g( m& u+ d+ E! B' k" e尾递归优化可以提升效率(但Python不支持): L: A  ]1 O/ W( A" A

    ) N$ ~  v' n$ s 递归 vs 迭代% q( x( n, @9 ~5 f; u6 h1 _
    |          | 递归                          | 迭代               |
    ) M; ?. C% |4 e8 }' X. t|----------|-----------------------------|------------------|2 I% ?) }9 k# a* ?% q
    | 实现方式    | 函数自调用                        | 循环结构            |( {! I. @/ J, ?$ F
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    / K& }) b: i: ?+ I| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    6 o; Q# ~$ r1 g" M3 d) ]| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    $ F5 i1 }0 @$ U+ T$ {/ h- q5 P) C0 A8 p( w% q' Y  q
    经典递归应用场景4 x3 n6 q; k" \" H
    1. 文件系统遍历(目录树结构)
    4 l, t: Y; U0 [' @, n$ w2. 快速排序/归并排序算法
    1 @0 K/ a9 @. ?6 |% G- o; e6 J3. 汉诺塔问题/ B- ~) O$ _" G$ ~; I8 P5 m
    4. 二叉树遍历(前序/中序/后序)
    & M9 Q/ k# G3 L5. 生成所有可能的组合(回溯算法)
    8 C+ n. G2 \3 b7 z( Y$ r9 b, h& y
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    12 小时前
  • 签到天数: 3206 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,9 @& V2 F5 C- o2 ^. f* e, Z4 {
    我推理机的核心算法应该是二叉树遍历的变种。( H! q  d8 z% ?4 W6 W1 t" Z5 e
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * K" Y- w# g- y9 M' jKey Idea of Recursion
    # n; b9 r, @8 Q3 ~) H8 l. N' d8 _3 s0 I
    A recursive function solves a problem by:1 D9 R$ t& [) t* o0 d3 A+ y+ B' b# M

    6 J/ r1 V; E; s$ m$ ], x, ?) U: l    Breaking the problem into smaller instances of the same problem.
    ; h) D0 m1 _' R3 Q' H
    * m. A9 ?- b. r/ Q    Solving the smallest instance directly (base case).1 T3 @9 E$ `) k8 H# V

    8 g+ J  b: P( z( M    Combining the results of smaller instances to solve the larger problem.  q! B8 B) f. j" r: n

    $ Z" [* C, i. M' \7 {Components of a Recursive Function" v/ N  V) D1 ~4 S, O, n
    : Q( u0 v8 c( N' @5 p
        Base Case:2 |) b, J/ h' s8 `% ~, N

    , r; C7 u# L! M7 N2 W$ e        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    % z! o- R& @6 A. O' z4 }4 F3 O, H/ z: @) N4 R
            It acts as the stopping condition to prevent infinite recursion.
    4 p, C0 s$ T: C8 r0 I+ k
      b7 K6 f7 D6 b% j1 o, ]4 P0 r        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.% p2 Z$ ]3 E' I. c2 R9 ]

    * m: j$ q- {. r$ {* a. q    Recursive Case:
      c, ~, `/ M. [" D+ [3 M4 i8 `% g  O; h! t5 b4 ]8 r! G
            This is where the function calls itself with a smaller or simpler version of the problem.4 |: @7 D+ k, r( g6 A+ J

    $ D$ @: F& m; n7 L. F' d        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).' d: c7 w! P. Z+ Z
    $ y1 v% K) k9 J- n% j1 G
    Example: Factorial Calculation
    0 y5 B) }6 E0 l' `; W; l/ i3 x  `; l/ n7 g* R3 P9 |+ y. f' N& o
    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:
    7 C! l2 Q) [! m* j( H$ ?7 E3 V3 M# _8 M- ?4 x
        Base case: 0! = 1! U) G0 ]# ?6 z3 J1 j% e  Q5 `

    7 e  P5 s3 f5 [    Recursive case: n! = n * (n-1)!# s# i3 y) L( D8 J% i: j
    ; |7 h! R" P3 U! P( |, _3 y
    Here’s how it looks in code (Python):
    8 P) W) Q' {% ypython: R0 v2 r7 D# r: g

    5 E. q! o' o# G  w+ c0 L: l# i3 Y; O5 M) [
    def factorial(n):- ?  G# L" D7 D# V( q4 p
        # Base case; a6 C0 |9 E- z9 P4 a7 j* K  _
        if n == 0:7 |  W; u  A. {$ a/ t
            return 1: e1 [, C$ \+ |: {5 I: b
        # Recursive case
    # D! e$ c- Y! o  s+ F2 `( F    else:. {( B4 g/ T2 c9 g$ {0 k" J
            return n * factorial(n - 1)
    9 Z/ @3 i9 P# L6 k7 z4 J
    & H" L! W% i1 N$ Z" L; r: i  }# Example usage+ a0 j( r' G: b' }. w
    print(factorial(5))  # Output: 120. E0 s7 ?$ X2 r: g  B
    0 H- O) A6 m0 k6 d$ v5 ~" R1 J; R
    How Recursion Works" {$ w/ r  M) S

    # v! N: g9 c3 q; {9 H! E    The function keeps calling itself with smaller inputs until it reaches the base case.
    9 ]  A& V+ W+ @5 ~" X8 A, Q) ?/ G, B
        Once the base case is reached, the function starts returning values back up the call stack.
    9 C% y! X3 P$ \; L. u) n6 m2 q2 B
    , x+ d4 d' T- Z& N6 p    These returned values are combined to produce the final result.
    4 _6 Z8 o3 z7 Y- |  P) O; B
    , ?; _; o/ C9 A4 X$ S% D! {For factorial(5):. A& ^9 ~0 u' M/ }
    1 q- Q8 O6 W# w9 I: t& M1 R- O
    2 ]/ K4 b4 T& I2 t. e- p% _: T' W
    factorial(5) = 5 * factorial(4)4 p2 A, ^: X5 R- n4 R
    factorial(4) = 4 * factorial(3)
    " A9 [2 `, d5 ]* d0 M7 s1 i8 m- nfactorial(3) = 3 * factorial(2)
    * C% h; x( R/ n: v9 {2 ]factorial(2) = 2 * factorial(1)& ]* D8 l+ F% ^- D. q( r
    factorial(1) = 1 * factorial(0)
    5 j3 n, J3 Z, {* x  l- G. }" {factorial(0) = 1  # Base case. I" h1 t% b* F9 b+ F; I+ E) m4 ^

    ( S  C$ c1 \+ IThen, the results are combined:; e2 ]4 m/ w- g# j- `
    8 X) g7 k4 O6 H: |
    1 M% I6 Z: V& P
    factorial(1) = 1 * 1 = 1# H. S* b) `- I( U3 ]: r& B
    factorial(2) = 2 * 1 = 2
    8 c, x. K# k" G$ s# ~7 G! P3 Xfactorial(3) = 3 * 2 = 6
    ! @* K8 Z1 M& ]: M& L# L' kfactorial(4) = 4 * 6 = 24
    . G- a2 P$ @' N7 I9 e. yfactorial(5) = 5 * 24 = 120
    2 Z7 o7 B4 x7 L7 h% b7 d9 g. C1 i& j! K
    Advantages of Recursion- U  Q" n9 k8 k: ^3 b

    $ N$ @& {% _1 P    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).
    ; u7 I  ]5 l4 s- o& m% z0 m* \( [8 Q/ h9 h. P
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    $ L0 {) O) Q7 b) M) c2 x
    3 T' R0 @) D* ^- _* T" hDisadvantages of Recursion- {7 j, d  Y! K5 ]5 G; n: S

    ! E& X8 f- q( a" e4 e4 E2 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.9 _$ U2 K2 z5 X: {
    6 F+ \6 J1 e2 k! h8 o2 _$ D2 @
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).2 ?: U4 g" Y' A4 y  [

    . ~1 z# X7 w& WWhen to Use Recursion
    # @% d+ |. I. r8 M) [" ]8 r! d2 h
    : Z$ W8 }. O) I6 j7 D; ^: C- r    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).* s( o3 [* Z$ Y/ ?0 J
    / K2 T/ F. P2 w$ S4 p: B
        Problems with a clear base case and recursive case.9 ]" N5 ~3 g- S& V6 Q3 e: \2 f
    ! F% _! j2 W; m( g$ ^1 S9 p
    Example: Fibonacci Sequence
    $ w( I: p8 y( R+ [9 i8 G) [
    9 |% e: F7 E2 ?% ?( MThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    8 N4 n4 K1 T' d( T( h$ d3 G3 F6 m0 t/ P0 v$ A
        Base case: fib(0) = 0, fib(1) = 1. l8 R& o8 h" C! n4 {8 Q) E
    " ~/ M4 G, d3 x
        Recursive case: fib(n) = fib(n-1) + fib(n-2). x" o3 c& P  [: P0 Z2 q

    3 @9 U& H/ ], g9 Bpython9 M5 d0 j* O% y2 f; y+ c

    ( ^% n% J" @4 u4 J- p( j5 F7 F
    " f2 M- ^1 R' sdef fibonacci(n):1 e$ m4 c# d% K" h" X$ P$ g
        # Base cases
    7 o! d* Y; x/ f    if n == 0:
    # d3 T9 `. b; Z  m) D  E        return 0; e4 m7 l9 X9 Z. p2 I
        elif n == 1:( u! r5 X. d9 p: P; p
            return 14 i  z- {$ \2 q9 z; l7 {; d/ |
        # Recursive case
    6 r1 O7 ~* w1 s+ b# ?. B/ [: X1 V    else:+ \7 A/ y  a. t- Y5 S8 y
            return fibonacci(n - 1) + fibonacci(n - 2)
    : s& h) s# m8 f! f# R+ C/ {* P  G1 D, b( j. q
    # Example usage& y. Z# s5 {. Z9 z2 ]/ X
    print(fibonacci(6))  # Output: 8- [) E8 ]: |2 Z

    $ f1 u4 j. Y9 t# |+ k/ H8 O1 KTail Recursion& A+ K+ h- q1 u! u
    - |% Y. @7 V9 q: Y
    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).2 D* A* i4 u9 l( @% Z* Y  D

    5 n* j' d4 u, NIn 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-3-21 18:14 , Processed in 0.064281 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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