设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ( W( A" g4 p) a6 g. |* q* G* t8 T

    1 ~/ {* u0 G5 z. v! x解释的不错( j3 \6 z1 L* V& K( k

    8 f4 P5 b+ {$ ^% M  t' @递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 E% v/ [( ~# ?: X) |' l

    ! a. E1 }& D- N- h( k" c  E$ o 关键要素2 _6 L+ W3 a$ c8 Q
    1. **基线条件(Base Case)**; o6 v+ h0 ?. h' Q3 ]
       - 递归终止的条件,防止无限循环% |! _; i8 K% p9 A" e. r
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1! }& N, W. G/ `: @
    8 ]& T5 q+ q- t
    2. **递归条件(Recursive Case)**
    / K4 P9 i/ E6 d2 d- U   - 将原问题分解为更小的子问题
    2 G/ X+ C8 s) ^, Q/ ?5 I# u9 ?   - 例如:n! = n × (n-1)!
    ) f8 r, j2 L- o( G8 t4 i: {0 z) U  r( @* c
    经典示例:计算阶乘
    7 L7 Z3 L) O1 r6 ]6 S6 n; rpython' J- k2 a2 B/ Y% j
    def factorial(n):
    - c( R" W- ^" ~8 C/ m    if n == 0:        # 基线条件! R' Y1 V0 |7 L6 W; {3 [7 \  |% ]
            return 17 m& k+ Y+ G/ v' }
        else:             # 递归条件
    ; U  E5 ?8 x- h: @        return n * factorial(n-1)
      f8 `( M; w3 A# C' c1 ^3 g4 L执行过程(以计算 3! 为例):
    : o. M3 @- [9 W) B" pfactorial(3)
    - L/ |( g6 [; F! w) ]3 * factorial(2): e. ^# s3 K( P
    3 * (2 * factorial(1))( o7 x" c- O0 M# d6 d. [! D* D( q
    3 * (2 * (1 * factorial(0)))4 i" q5 }9 n2 Q/ v% H- y2 j
    3 * (2 * (1 * 1)) = 6: X. F  {1 T5 m

    6 c$ |( j/ Q! M- p% t7 m 递归思维要点. R& s; {4 ], K+ G
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    4 L# H, o3 ?8 k$ k2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    8 o! c& ^( q& \* d6 ?! ?( H3. **递推过程**:不断向下分解问题(递)5 c' |# H' f0 U% `1 w
    4. **回溯过程**:组合子问题结果返回(归)
    & ?7 I- m% r6 G( f3 \1 p3 c+ D' {! _8 o
    注意事项
    3 N4 ]4 L8 s2 ^# o# t3 n4 b必须要有终止条件) @/ Y2 B7 A; s( p) A% T/ M
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)# }3 s7 V8 z) b& k5 w
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ! x; x  c% R! n9 m1 v5 F尾递归优化可以提升效率(但Python不支持)# ]$ B( ?3 U1 X) K0 K

    . o- R2 u- ]( ^ 递归 vs 迭代$ F5 F: a( x, x& ], x) o/ T
    |          | 递归                          | 迭代               |
    , L1 r' C0 D) A  V7 q|----------|-----------------------------|------------------|7 M" [! `9 L  |  ]8 V, _; }
    | 实现方式    | 函数自调用                        | 循环结构            |! j9 N6 t' w9 X. Z( A
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    : a' t3 H3 r$ u0 {1 C, u# s| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |/ X) W, Y; j! n6 ~$ |0 w, `  z0 }
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ; t; ]3 S6 s# \8 R2 Y
    * y6 r( P2 x7 [3 y: d 经典递归应用场景& }" }/ U' m, {
    1. 文件系统遍历(目录树结构)
    6 T  f% r% @8 z' X' O3 \2. 快速排序/归并排序算法, c- O5 \8 B! U6 j' @
    3. 汉诺塔问题! \2 P; P3 d3 g% ^6 {1 z
    4. 二叉树遍历(前序/中序/后序)* e* }, J, Y/ H% X+ g
    5. 生成所有可能的组合(回溯算法)
    4 U4 O4 `4 H. E5 `9 R
    ) U" p% I! @: k: a' [' u试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    7 小时前
  • 签到天数: 3190 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    , c2 N( t8 `# w9 g& L我推理机的核心算法应该是二叉树遍历的变种。
    7 U1 m2 V* D" V: t另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    6 l; ]2 n  q. ?9 y5 E: wKey Idea of Recursion  X; I$ o, Q- Y( t# c. v, ?

    * I! {) K2 A1 @5 |/ X2 ^! Z% rA recursive function solves a problem by:
    3 \# o+ V+ Y/ S. W% a! R0 `9 p- w* h, t) D: [' ]7 ?  t8 Z) J
        Breaking the problem into smaller instances of the same problem.
    " y$ Y7 `8 i! a$ A1 c; O; I/ x9 A- X- y
        Solving the smallest instance directly (base case).
    : u( T' Y8 U5 D% T7 Q1 D4 r! R) B. \+ y; e) N, {6 R  O/ g
        Combining the results of smaller instances to solve the larger problem.: J. a5 i- |# S3 |8 q  i" `
    ) [* W) _1 N$ V8 |' S* [% N) s1 Y
    Components of a Recursive Function
    . ~' Q: O" Z. @0 H* U! ]6 ?
    8 z6 j) {5 j- [  y$ t' p8 c    Base Case:+ f) V; c, x5 `) L

    / G. z, _, l# e- ~5 `* F; @        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    7 ~: y6 h% K" W2 j5 H/ B9 v9 u/ M5 g
            It acts as the stopping condition to prevent infinite recursion.
    + k6 B3 p; K( l# W- _
    % a; U( X/ J4 |6 E  w0 k0 t; T        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.) U0 e& h# ?) X0 m
    2 y  ]3 o0 @! l; o, z, t
        Recursive Case:9 i; V" ~$ f+ H  g

    2 K3 A; N; `+ A1 Z& B: W8 b9 y        This is where the function calls itself with a smaller or simpler version of the problem., O; S: A" Z. n. z* f# E5 [1 w; s

    " s; X8 z! _- F, S6 j6 O- k2 k        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).4 I4 H6 R5 v8 \) g+ m# l8 _

    7 P! ~) P" K! O' `Example: Factorial Calculation
    6 `/ j" Q6 X6 l% p# j3 o( _3 N/ g) g
    0 e/ t) s/ U( HThe 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:
    : ?! c8 Q' K1 m) S4 r2 w9 {' U; g/ G/ Z" _3 p
        Base case: 0! = 1" T- r2 y/ V4 I, t6 l- s2 |
    , L: N6 B- Q/ a# `/ M: Q" ^
        Recursive case: n! = n * (n-1)!! u) F7 a/ _9 w! [: ]; U
    3 l+ ?$ z7 p( n& b) W5 q
    Here’s how it looks in code (Python):
    ( P4 u- V2 X  X& r" c4 bpython1 i) w4 ]+ [6 i- @; B! T# x
    9 P7 T  x9 J% }
    9 r1 [' @; N# P2 W
    def factorial(n):6 U. e9 I  ^+ m+ [* E3 m: T' l
        # Base case) ?4 C# I0 n1 T3 ], N0 m6 Y: k
        if n == 0:9 i% [# W9 O* P5 C3 N
            return 1
    - S# Y& _$ q' z) c2 v6 R* K    # Recursive case
    ' e8 t! {. v5 D+ _9 v7 L    else:
    ( Y+ \/ K5 q% Y' J+ \  T/ N# R. m        return n * factorial(n - 1)6 c( `5 x8 x' G

    2 l& E$ C4 ^9 @, A- R# Example usage/ b& Q  m6 c  t$ w+ u$ H( Z
    print(factorial(5))  # Output: 120
    & W* {! N0 t5 N- J( Z2 L, S
    4 j" S0 \; ^( dHow Recursion Works
    % v; g2 n6 f5 E6 n" v, L) d8 \! Z  G& p/ t1 h# j" Q+ v9 D
        The function keeps calling itself with smaller inputs until it reaches the base case.0 I8 _. E7 a0 p( b
    5 D* Y( B( B( S) G+ {4 C
        Once the base case is reached, the function starts returning values back up the call stack.
    " K$ O  D: {/ p$ t1 M5 A! d( n% V6 x! P* }$ B/ U6 \) p3 {9 g4 {6 J
        These returned values are combined to produce the final result.4 @8 e3 Q$ |, c& M2 M+ Q& W! S6 q
    6 ^. [* x" v+ E; j0 Z# S
    For factorial(5):
    : H0 [% v3 O; t( ]+ C* n
    + u$ B5 G$ `9 h/ I# w
    7 m/ T& s# Q) g: o, @& F( Pfactorial(5) = 5 * factorial(4)
    # c: D% }# c# ]0 Wfactorial(4) = 4 * factorial(3)
    ) i0 X( l5 |6 y! _- P: Efactorial(3) = 3 * factorial(2)/ m8 f, Y; ?. e2 z  d
    factorial(2) = 2 * factorial(1)/ S8 E' h8 g4 ^+ H6 [
    factorial(1) = 1 * factorial(0)% c0 z0 t! r8 G! J- `8 q( x
    factorial(0) = 1  # Base case# [0 y5 V+ D$ X: A( O* a
    $ U! v% w; \4 z6 b# A
    Then, the results are combined:
    " g* H+ K' d6 H2 V! O+ ?- ^: N* N5 x5 |

    9 }. f9 O* ~; U8 G3 H7 V; A2 jfactorial(1) = 1 * 1 = 1
    " [) [* O& [! V* U0 Y( U. o0 Kfactorial(2) = 2 * 1 = 2
    0 v7 B( N, d" y6 Rfactorial(3) = 3 * 2 = 6% `5 i4 t( `. `  ^8 c) a; E
    factorial(4) = 4 * 6 = 24
    * i0 g) e/ F8 @factorial(5) = 5 * 24 = 120
    " ~; Y8 `5 L2 W' ?7 `3 u+ f% x5 Q5 c0 l0 r
    Advantages of Recursion3 e: U& v, O( Q! v0 ?$ d) j( D: U

    : ^+ M' R- d. O1 f0 }) ~: r    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).
      U1 c; f* |8 d, x; {1 r4 S& E0 K$ L2 q+ C+ g2 ]6 Q6 z0 D: k
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ' T& q( n1 C" _" P" y
    ( L. k- A3 S0 n0 I$ kDisadvantages of Recursion( p; J) I  s, B4 c- r

    ) [- ^& l) x" n+ q: I. K4 e    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.
    2 T- ^% G. n1 E! R- S5 ?7 o4 X/ ^6 o: R9 h) V3 Z! y% `
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).- `( Q- I4 X( g! y3 i

    - N4 w- L+ O. GWhen to Use Recursion% I" C1 X9 p: X3 P5 ^; Y

    0 e) C' C$ Q# \6 v! H    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ; R5 U  |9 I( U, g3 S2 d9 D. N9 {9 v7 A6 u# n6 a# ]
        Problems with a clear base case and recursive case.
    + W9 u$ v! L1 ]3 p! o! w; z2 d& a2 [
    Example: Fibonacci Sequence$ v3 N* L' r  N' ]& \8 q

    0 ~# L# R5 s: ~" `8 W9 AThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:5 Z# k1 M. V. P3 f& S3 i( R

    8 m4 [4 |: x. c1 K+ d) N    Base case: fib(0) = 0, fib(1) = 1
    5 h% A$ ]+ K; X+ O& y9 x( f5 {& @. Y6 ~
        Recursive case: fib(n) = fib(n-1) + fib(n-2)& G* k% z! H4 A4 b( f

    ; C% }$ D( u4 p- P3 Xpython
    7 B9 j9 [7 ]) o% G9 M: p
    * m7 d2 _8 |7 F8 V8 T: _  f0 ^9 D* B; \: o7 }. m7 a
    def fibonacci(n):
    ; [2 |4 [; H& Z* m! I5 m2 _& o    # Base cases
      G* K+ I0 G8 O! ?: o- I) l    if n == 0:
    , C3 |% e" Y; M5 \/ s        return 0
    % K; A; N4 e1 D& i9 W    elif n == 1:
    ; ]4 W* p3 `7 y% E. u        return 17 K$ g6 a$ d8 o$ R
        # Recursive case
    ) U, D2 T1 D# y: i5 Y% i$ D    else:
    & w7 `/ c7 r3 Y) ?# m$ i) m! I4 \        return fibonacci(n - 1) + fibonacci(n - 2)0 X# n% B' a* ^3 x
    8 S, ]7 Y$ D; F# T4 W: i' f. c! a) c
    # Example usage
    4 |* p/ y/ L9 Y( zprint(fibonacci(6))  # Output: 8
    / ~! i! g) a7 O- G
    ( w& e8 [; i8 E0 qTail Recursion
    ' U, B0 V  Y/ r0 S8 u7 N: M- Y/ r3 U4 u/ I) I
    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).1 y' e3 @' h, x5 O- O5 O! u$ i& C
    " C9 B! d5 m$ r0 K0 C
    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-3-3 15:18 , Processed in 0.066882 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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