设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ; J. p# U3 a$ o0 V% W8 Q& L# A; Q

    ; A( a2 c' w6 F. |0 N2 @解释的不错) b2 q6 k" |# \7 b7 n
    ! Z/ s2 p9 W, {" T( D% z& w
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    : n6 Y. Z. ]4 F# i' Q, K" S* S
    ; r3 x/ y0 x% s( K0 o, x 关键要素
    5 J& c0 H( _' F) X2 B1. **基线条件(Base Case)**
    8 v4 y+ O; \6 c% s   - 递归终止的条件,防止无限循环) S3 q! C/ F4 X2 E6 E" w+ l$ N
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1; Y: z. W9 W* G+ `2 W+ N6 O2 T! c8 P

    / A3 d1 l9 K, m' \8 s2. **递归条件(Recursive Case)**8 }/ g" U; g( ~% R$ A
       - 将原问题分解为更小的子问题* z5 c5 K0 f9 O* h' c
       - 例如:n! = n × (n-1)!
    5 v& N0 V7 |7 w1 j
    ; I4 T7 w2 ^( u0 A! y: k 经典示例:计算阶乘
    + I7 u. I+ n; t$ Vpython
    ; n' i5 r# W1 ~2 Q, ndef factorial(n):
    8 n3 R1 d1 r" ~+ e, e5 c+ c6 R/ f* J    if n == 0:        # 基线条件* f2 ^0 e! c1 s
            return 12 G5 G, v. {- T" m- C
        else:             # 递归条件
    8 v6 ]: W) U" @: k. m        return n * factorial(n-1)
    6 A0 B" y) u' r8 e, y执行过程(以计算 3! 为例):
    ! e0 C! g, f3 C+ R) R: sfactorial(3)
    , A* y7 t/ T% {# N3 * factorial(2)
    5 m# S3 V' I4 O/ l/ P0 V: p* _3 * (2 * factorial(1))
    # E4 }+ p! \& E; P3 * (2 * (1 * factorial(0)))# p5 \4 O9 C+ [, o; y
    3 * (2 * (1 * 1)) = 6
    ( @$ I  Y9 j! S/ }- v' ?% C; y, w
    ; c/ U: u" r( `. `7 J( S2 A 递归思维要点
    1 e9 f4 H/ R# S' V  c5 o1. **信任递归**:假设子问题已经解决,专注当前层逻辑6 e5 D7 C' h% t5 h! e0 A
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ; _$ w, X6 m" N3. **递推过程**:不断向下分解问题(递)
    9 K" M4 W7 H% f% d9 A0 e1 V+ h$ X4. **回溯过程**:组合子问题结果返回(归)8 H9 k! D% V# X, ?

    " d# U1 v% q4 ?+ Z+ Q 注意事项
    & G- y. n; Z6 ?/ x" E: @必须要有终止条件4 v/ |7 g: w% J) @1 M! @3 b
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)0 X. Z+ [+ |4 |2 p  U) f
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    $ A. E5 Z( ?, c. E5 z. M) Z尾递归优化可以提升效率(但Python不支持)
    , u/ r1 Z1 t$ N
    1 h4 N8 M; v0 @0 \' r 递归 vs 迭代3 y( I. v# @; V$ U) g. A
    |          | 递归                          | 迭代               |( e  C/ Z4 d9 d$ j- ]
    |----------|-----------------------------|------------------|6 Q# y. s% O% H
    | 实现方式    | 函数自调用                        | 循环结构            |
    8 q5 F8 L. [( x5 h* J7 V4 q2 {$ s1 Q8 [* c| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    , i$ T" e; ]/ N) f| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    1 D) H0 S, l; o, Z* w# F4 V| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    . s" r. e7 T/ p6 j
    % d! e! F* U, U9 d7 W  z7 h8 j 经典递归应用场景
    1 W3 @- ]+ X6 M% q; ]- P5 ~# z. A1. 文件系统遍历(目录树结构)8 U2 H0 |5 x# S
    2. 快速排序/归并排序算法+ G2 v. x0 g% I0 r9 S7 y
    3. 汉诺塔问题/ M, X* i8 z: C
    4. 二叉树遍历(前序/中序/后序)
    * a, A5 ~+ m5 @, r& k3 t* k5. 生成所有可能的组合(回溯算法)+ O- C9 G! @- G  T1 ^; P+ w- @

    - l# Q) e4 e3 C2 h0 j: b& p试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    9 小时前
  • 签到天数: 3178 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,: L3 O# v1 I9 d* C- I/ q) g
    我推理机的核心算法应该是二叉树遍历的变种。
    " D% g! N$ Y" w+ z另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    + a8 u" _4 @$ L. r; f+ o1 d) S+ H  ?4 ~Key Idea of Recursion  I/ y. h# x% N6 \0 a
    7 g! Y/ O8 p# v: Z4 C7 j# f
    A recursive function solves a problem by:
    / g: j( c. \8 q! H$ P# p& e1 f. D
    ) P+ j% P* v/ f0 X7 B    Breaking the problem into smaller instances of the same problem.
    + F5 H7 F& ]+ f$ ^
    8 s. a# x" h* b4 r    Solving the smallest instance directly (base case).
    3 M" D2 J/ ?( H! u$ Y; Z$ }: c  y; T6 Z) G( @. u
        Combining the results of smaller instances to solve the larger problem.
      I# P: o  z) I; y: G+ N
    # ~7 W0 n2 F' H' }! a4 T# CComponents of a Recursive Function% m1 w& @6 h4 f

    3 U9 V) A1 c$ H, I' p3 u    Base Case:
    ; W$ J/ Z+ `: p: l' r2 {. z$ R' m  r: u( j- t' g
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    4 @  ~( e+ W; I3 m
    # G& J) F& r1 c9 Y* B: l        It acts as the stopping condition to prevent infinite recursion.9 |4 b0 Z% N- {4 O- T1 d) A
    7 r2 {- s( R3 A) R  N% P
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.- D( r* \& Z5 q2 y0 M
    ( X$ r; F2 l1 G5 D8 j
        Recursive Case:, q. p% E2 _( ?' `+ _

    0 C5 X7 @( s& q& m7 u1 h: A3 q- N. {        This is where the function calls itself with a smaller or simpler version of the problem.9 K3 e- w7 o3 y0 @  B# N6 n" F6 Z

    + U- Q% x+ Q3 Y1 Q7 h% a* ]        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
      ?$ Z5 m5 f/ @! a8 n7 p  ]- z1 v3 q% C$ j, @
    Example: Factorial Calculation  N1 C( w" i4 C" E6 Z! S4 x
    ' R  h# d( e3 Q* }: V% N
    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:
    + g% a+ c  n# H% ?5 Q
    6 K9 k4 A+ {) x* S0 r, B( c    Base case: 0! = 1
    ( ~$ t/ W6 a1 i! f; x3 t% g6 V
    # p( Z2 T& e" \! J: _8 d: U+ y    Recursive case: n! = n * (n-1)!
    # V0 @- h- Q8 v. ~) d- |: J  q% |2 T
    Here’s how it looks in code (Python):
    $ v$ h, k2 d& u; J& hpython
    2 t% U7 y6 w6 ?8 i
    " w  S- c0 _; Q8 I. n! P/ N5 ?4 n4 K/ x8 g6 F1 v8 L5 g
    def factorial(n):( o1 ~; n' L& d. O/ A* |
        # Base case
    # {7 i' N0 ~8 e* p( s1 h* Q    if n == 0:) c/ `# \; `: E) Z# F7 V" l  K; G, l
            return 13 d0 t# W( L* |" Y
        # Recursive case
    : A% y, U3 Z4 m% V    else:# X' q6 p5 {% u7 Z
            return n * factorial(n - 1)
    . ~1 I6 G# {. P' ?* {
    " E, `- K6 a# r, Y0 y: p6 G7 L' k# Example usage
    7 k  `9 @/ `, z5 |: Tprint(factorial(5))  # Output: 120
    0 m3 U9 n% U2 Y0 u, u5 C1 G' ?- K; ^- G9 a7 h4 f: q4 P2 V1 {# Z0 ?+ X
    How Recursion Works8 v3 b1 `) y' E0 ^( `! _; L
    1 b; S: g+ {1 f, N9 X  d. k3 D6 M" r
        The function keeps calling itself with smaller inputs until it reaches the base case.
    + W7 A# `& O6 Q/ M! @; j+ Z. P+ i0 Z' {7 J
        Once the base case is reached, the function starts returning values back up the call stack.8 I6 p% j2 _! `  E& y/ l7 P6 n2 k
    / O! O# {2 n6 O2 |9 |) h- c5 m
        These returned values are combined to produce the final result.2 H5 [' f: W6 n& [

    0 a. Q& z1 E! D+ S# W5 K7 B/ Y  FFor factorial(5):# B6 E. N6 q3 u1 b* ?) E, j( j

    0 b- ~# a. O( y) z& B2 O
    ( j( A1 N$ _; T& T! \* |5 ^factorial(5) = 5 * factorial(4)3 P7 Q, I& g$ S3 q' l
    factorial(4) = 4 * factorial(3)& T' {1 w* |( h2 E
    factorial(3) = 3 * factorial(2)5 k" q! M9 Q# V  \2 f# E' B, ^
    factorial(2) = 2 * factorial(1)
    0 Z7 {+ H4 z- A# M5 _4 Xfactorial(1) = 1 * factorial(0)
    1 k( M! [* Y0 d, rfactorial(0) = 1  # Base case# ?, S) N7 d4 b* d

    , ^4 s; Y/ N5 K0 h5 d* X; KThen, the results are combined:' S, r( C% ~+ t
    5 F8 I; a, c( r- M

    0 w% E" Z% {- H( `factorial(1) = 1 * 1 = 1& G; B8 \9 M4 s0 s/ A6 \- H
    factorial(2) = 2 * 1 = 2
    $ K. a4 ^$ v+ X% z; yfactorial(3) = 3 * 2 = 6
    , {* m% e, b: ?factorial(4) = 4 * 6 = 24
    # {. g: h/ Z0 t4 pfactorial(5) = 5 * 24 = 120
    % X5 P& r3 c" t/ S/ }  F9 Y( }. M1 ^  n" S
    Advantages of Recursion9 Q! X# G* S: A6 ?- {
    ; {7 u; `+ s3 U8 U: t9 |; ~- y
        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).& w% }) D% P+ p  z1 A/ N6 i
    $ W' K% c0 o7 m- r
        Readability: Recursive code can be more readable and concise compared to iterative solutions.- `$ L( p5 v+ D+ c, d

    ' z' ]- F$ N! i& o/ ^, HDisadvantages of Recursion: l2 q& t+ S  h$ J

    $ C' x, Z$ ^  o( R, i    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.
    " n5 T8 A5 v+ I! d+ Y* {
    0 H7 L) S' {- F* ~! \0 Z    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ! |+ a9 H0 x. M. H- q7 [2 U. }  f( L2 t: I  o
    When to Use Recursion3 e) F7 L5 ^5 R- h+ o! h3 J' ~7 R  ?
    1 s* {3 D6 `' h- @0 W7 @! ?: W9 d
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).0 q  \5 |8 E; p0 r# g
    0 i+ n$ i- h5 O0 s9 w
        Problems with a clear base case and recursive case.1 D8 H& U- }- \6 N1 H9 {
    ) g/ O7 u: o5 O
    Example: Fibonacci Sequence9 r( j& x3 R3 U4 x, R& l; l
    4 d) L5 P: K$ L6 T' S" z( [
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    , h6 H) b0 I/ D3 C6 k6 ~; S% \* r
        Base case: fib(0) = 0, fib(1) = 12 W7 u3 s8 p1 E/ D3 O
    ; \9 o3 ~0 C0 t7 l: w3 w  H
        Recursive case: fib(n) = fib(n-1) + fib(n-2)) f0 P1 f  U/ f' S! w  C
    & s% D& u  }2 f" z' @5 ~
    python4 {* m- y5 S: e) V9 b  i

    4 T, X) o. Q1 J+ D" ]( r9 w/ Q
    : I9 D2 z+ x! A' ]def fibonacci(n):
    ; Z+ c# |+ c' u9 }    # Base cases
    / Q6 p7 q" f( T0 a9 y' o3 O    if n == 0:
    4 n! J$ A( ^. |! ]; }" C/ `        return 0
    + t( J' {( Y. \! ]+ A- y* u    elif n == 1:
    1 s, z! m% w4 \2 w        return 18 v! }5 R, O! D3 ?5 y3 G0 b" p
        # Recursive case
    / J0 N- R9 n- _4 j- t    else:
    , V  E4 Y3 ~& S6 f8 g/ h% D        return fibonacci(n - 1) + fibonacci(n - 2)
    % ]. S) P0 M2 B3 }9 r2 {! }+ E) _" _
    # Example usage9 X  b( u( Y% S* b
    print(fibonacci(6))  # Output: 8
    " E2 h; G8 |- n9 l1 l/ Z
    2 u) y9 C1 z' RTail Recursion
    0 s7 R% B' J$ j  j% p
    , T6 n, ~4 \3 P' o5 dTail 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).& R$ c( Z( m+ G: L  C0 F

    5 b  _1 F. q5 x5 pIn 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-2-19 15:56 , Processed in 0.057730 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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