设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 5 A0 K" a* K5 \3 g" J

    6 u3 ^" M3 S4 p6 c1 W解释的不错
    3 L9 ?% X/ {  N8 T. s% o8 G0 w! G
    ( W# w! y1 Z( i3 X0 F递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ; [" c- b8 l8 x: Y
    3 g; U7 ~  z  v" ` 关键要素
    % \+ ]6 A! ?! S( O1. **基线条件(Base Case)**
    ) x0 v6 T  M  M   - 递归终止的条件,防止无限循环( X2 u( o& M  i, a( M* y4 m
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1" y: G' F$ F# g4 Y# T

    " g) N# \  @( H+ O$ i2 Y- P! g2. **递归条件(Recursive Case)**, O0 i; |0 Q) N+ i5 K
       - 将原问题分解为更小的子问题8 @/ T8 ]* |4 K' k" k/ X# q; m
       - 例如:n! = n × (n-1)!
      n* J3 k- e9 I9 V2 {& h; g5 p- \) g+ O, ]: ]! ^
    经典示例:计算阶乘; h+ {; w' P) `& C4 U
    python
    ; M$ i" u: B2 o3 v. w" X; Pdef factorial(n):% z. s( f0 i/ t1 \+ w
        if n == 0:        # 基线条件$ H6 r0 _9 s' a, D4 \5 h9 g
            return 1
    1 _2 Y1 t- h6 z3 C6 e" S0 f    else:             # 递归条件- E5 }! l7 s" e, J. l' o" T
            return n * factorial(n-1)& Y- A3 ~* n, {- _
    执行过程(以计算 3! 为例):
    3 _5 X& [: E5 P# l4 `factorial(3); n+ }( ?2 G4 K
    3 * factorial(2)
    6 k2 \$ ~6 _8 c1 z6 A4 }3 * (2 * factorial(1))9 k5 E, E) T) g  G1 }% C5 O2 ]0 L
    3 * (2 * (1 * factorial(0)))
    ' R; t* e- ?) O1 O+ b3 * (2 * (1 * 1)) = 60 s6 C. T/ [' n

    4 e# [8 q# W* q( B& d 递归思维要点4 q1 H' m9 {+ S* k$ }: ]! {! t
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑7 B' ]9 b0 x# I* K- s
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    , ?) i0 X7 A, m8 U* Q  g3. **递推过程**:不断向下分解问题(递)
      a" v- f2 V# S+ X5 `& K, R4. **回溯过程**:组合子问题结果返回(归)
    ' e3 V" b5 y* f2 v2 `. {: W+ N2 T* h$ [! W" y0 ?9 g
    注意事项
    ' m$ Q' s1 l, d2 j) D/ m$ @必须要有终止条件, D4 I3 X$ V: M5 n; t' Q0 V9 r0 i
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    - o$ H% z: q9 @1 J; O某些问题用递归更直观(如树遍历),但效率可能不如迭代
    " W3 a& S. x2 h3 B: `9 t尾递归优化可以提升效率(但Python不支持)
    7 J) w  g' u$ S) T# S/ \. ]. F* o4 L
    递归 vs 迭代" O/ d3 G, t0 S4 m% K6 k
    |          | 递归                          | 迭代               |( P7 P) h2 m( n6 k6 n" P
    |----------|-----------------------------|------------------|, K5 A! `; N; ^& i9 z7 ?! Y
    | 实现方式    | 函数自调用                        | 循环结构            |
    5 w% \4 X2 u5 T: u, v& f| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    5 }: r* @7 c+ x$ T, E| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |2 C' r/ x8 E1 ^0 z' f$ ?( ~6 \0 c/ r
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |, [$ c" ?. m. H* M8 X

    8 `$ [% q/ |, m) t7 w2 O 经典递归应用场景
    - y3 ~- F) w3 [1. 文件系统遍历(目录树结构)
    1 u4 \" O) S" h0 K1 H2. 快速排序/归并排序算法
    , V- K0 ~' C, {4 ~  t; |1 V3. 汉诺塔问题3 f+ m0 V6 L9 _# f9 x% F) ~" b
    4. 二叉树遍历(前序/中序/后序)
    6 j9 \3 J3 V) Q8 Y5 c5. 生成所有可能的组合(回溯算法)$ E+ [1 ]' k( `% B9 w& G* \4 S: ?/ U
    4 x* t' M" U1 e
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    昨天 12:19
  • 签到天数: 3107 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,2 j& w) R, L8 i. v; ^! i+ P  B
    我推理机的核心算法应该是二叉树遍历的变种。- L6 G9 p2 A4 I' u# N9 ~
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 n0 Q% x: z* b; D' Y  k
    Key Idea of Recursion, o5 L$ W1 x# n5 W, ]/ M

    " C7 N4 v3 k8 X& `% hA recursive function solves a problem by:' C$ @" s1 J8 L' r. }0 H
    0 G: M- {  W, M  V+ n2 N7 c
        Breaking the problem into smaller instances of the same problem./ L) F, Y+ b+ f5 k- o$ V
    , e; }! x1 y3 N3 T  h6 W% E& G; q, J
        Solving the smallest instance directly (base case).. C, M- C$ }! a4 D* z# Y

    8 g" n; Q7 z( A& e    Combining the results of smaller instances to solve the larger problem.
    . \* E' V' y3 A, T9 c2 }+ V; H# `! x
    Components of a Recursive Function
    7 s4 w# O) h" x- w8 ]+ H
    # s1 g. ^4 W( J4 t& ?0 O) Z    Base Case:# b# P$ v9 Q  f/ X; }, t

    ' k9 ~6 b# v3 e2 T) \5 u4 o        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ( q- Y7 C/ h( J6 A! z" B3 r- n) n, ~9 ]/ z
            It acts as the stopping condition to prevent infinite recursion.  P3 |- J& w6 O9 e1 I
    ! ]/ |  L; }# t1 r* L1 Y
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ; Q, D2 s8 h! ^: A/ F! j( c" M& h+ p, k! ]
        Recursive Case:
    ; y; d3 {2 I$ ]& U' S! P! J/ S5 W9 E# W
    6 w- M- y' c( n0 M$ j" G        This is where the function calls itself with a smaller or simpler version of the problem.
    . j% J% j  W' k2 u, U8 x/ G# I( p/ q' a9 w7 c$ r& f- s
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. m; T& P7 Q+ P7 I( J8 b/ a

    % D) B; N- a" \. ^' W/ {  H3 @7 |Example: Factorial Calculation  b9 j7 g, f. v1 p* ~/ ?1 w6 Y: ^3 Z

    9 i4 }: h5 o$ l: J) {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:6 x8 G2 v; m: y
    " V# u) ~6 J' @1 F
        Base case: 0! = 16 A0 l8 K0 n( I* N' C  Z: |+ _# t
    & V4 F7 C! ?5 D, i
        Recursive case: n! = n * (n-1)!$ f9 i: ~( y+ @; H" ^1 s4 ?
    6 X+ m, I, ?: W1 A$ m1 W9 k
    Here’s how it looks in code (Python):1 c' q( U. `; ]# S7 }
    python
    2 V/ L& \( ^5 e" R0 t% ?% S( ]1 I
    8 [9 ~, r6 R( q) ?7 x' N, F2 Z4 e4 E* ~8 g* {# q! S; d: a: D- U
    def factorial(n):  o& B4 M  G% g8 b7 B! R9 n
        # Base case
    + z9 O4 X1 }: q- C7 `    if n == 0:( l4 l9 g7 G; i8 i, I) `
            return 1) A$ _1 G/ F" m3 T, Y8 B3 V- r
        # Recursive case  w( |3 A2 A7 J. m
        else:
    . z2 t3 }9 W& X& j5 n        return n * factorial(n - 1)# b# K" c7 U" U% _, |  ^5 X/ ]
    + n: b6 t5 v8 x
    # Example usage# h- Q  d9 c$ n
    print(factorial(5))  # Output: 120
    " `% `( `( k% G0 m
    & f' x- C0 {+ t( o* B2 KHow Recursion Works
    5 B; V3 g* {, c' Y6 I& _2 R) K$ M3 E* o2 [* f  O2 m
        The function keeps calling itself with smaller inputs until it reaches the base case." L6 ^3 k4 V! o, @1 e% X+ S% v
    # ?5 [& w! J" O4 r9 |( f' Z
        Once the base case is reached, the function starts returning values back up the call stack.' ?  w0 e- d0 K5 T5 C

    2 K4 l* Q6 d) N  Q    These returned values are combined to produce the final result.1 Y6 a* `9 b+ l) I

    : s# f. f+ d; C2 B* dFor factorial(5):
    - R# C/ f. n" v! P& M
    * A7 D& M% ^- C. ]* B* _5 ^3 g+ S; I% z! }
    factorial(5) = 5 * factorial(4)' c% k6 r: V4 \5 {4 t* E! y( K
    factorial(4) = 4 * factorial(3)1 y3 W' s( @5 V7 Q3 Y8 D6 a
    factorial(3) = 3 * factorial(2)
    * c0 m; X, C0 sfactorial(2) = 2 * factorial(1)
    % D5 g  [1 u* s- L. Sfactorial(1) = 1 * factorial(0)
    + m  z( K5 I# {# e' ~factorial(0) = 1  # Base case
    ' U/ z1 a/ [5 E1 C2 \& Y" c9 y3 g2 b' B$ e" g
    Then, the results are combined:" [! h/ i$ p# Y

    8 b* a* A2 y: D* I7 ~2 U7 b0 R# M% s3 l# R' B$ L1 u% Y
    factorial(1) = 1 * 1 = 1
    ! t6 p. r3 A/ n4 A* |' ]factorial(2) = 2 * 1 = 2! D2 `* _, N6 j6 g% M0 u
    factorial(3) = 3 * 2 = 6
    - S2 F- P% b7 \& vfactorial(4) = 4 * 6 = 24& b, t& }4 A! y- N
    factorial(5) = 5 * 24 = 120
    4 r5 ?4 h: S3 W# R6 {2 {" H% ^+ i! O8 v, ]) E* o9 I
    Advantages of Recursion( N6 B; G5 q- S$ U
    ; b- B6 i. ]2 l6 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).& x9 Z3 z# s: {# u7 t
    9 b, a+ h% e( ?4 x
        Readability: Recursive code can be more readable and concise compared to iterative solutions., g  G! q# v0 I$ ?: d

    & f; h! Z" O( tDisadvantages of Recursion2 w: H5 T# y4 ^; R% M; ^
    : Q" f+ L: ?& \3 k
        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.
    - j% }0 |# ^. j* a. K% k+ x% e$ B6 g4 }8 }# a0 H
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ) C- l- H# [+ _/ s+ Y0 d& T
    5 A  B/ c# L( G0 NWhen to Use Recursion5 c& Y- m) G5 x( S2 Q1 D

    % ^: ?* u4 N2 l( h( a, S    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    : [  [) u4 g( J0 g: z' N
    1 O$ B( i2 i) e8 y$ L    Problems with a clear base case and recursive case.
    # U/ Q2 ~/ `5 k8 v8 H/ U% k
    2 Z  N; G1 B2 B& s& T' m7 VExample: Fibonacci Sequence
      o) E  n' T9 z% O; g, I5 C
    : ^7 A2 r3 c- X% Z  qThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:4 q3 h5 H/ x+ v
    $ w3 W6 K& e: \2 E% @- ~5 ]
        Base case: fib(0) = 0, fib(1) = 1
    & r; z9 _9 A3 Z, y0 o  |/ M0 X- y/ u) y7 `# `" P, g8 H1 r& M% S/ j
        Recursive case: fib(n) = fib(n-1) + fib(n-2)  W9 S6 `4 [# g- X; m+ s% E
    / `- h& i& \+ t( r
    python
    % ]& n/ ?0 e/ [0 v2 g/ y
    4 m4 j+ T/ s' f* k$ R2 E
    , a' j1 T  I+ ]def fibonacci(n):2 ]4 V( q* P3 |! x* w% M$ Q
        # Base cases
    / e0 ^$ Y: k4 y& x% a1 s8 h7 z    if n == 0:
      M' w0 V) _2 \$ N% S        return 0
    / i1 P# ^4 H6 U( n4 p0 E" E4 Y3 U" j1 N    elif n == 1:* R$ F1 q$ Z1 Q2 D! `
            return 17 P2 ?: G" L% I9 z" B) F+ Y
        # Recursive case
    2 F7 w; T6 @$ V' P/ d    else:; O! X4 M. K. O: m& J
            return fibonacci(n - 1) + fibonacci(n - 2)
    % ?0 {8 C" s& S. g' G6 e$ ]1 C; z' R* f5 L' h8 K1 U- o
    # Example usage7 l( _7 M( }/ J
    print(fibonacci(6))  # Output: 88 r! ~( }5 Z7 [
    ) `4 E" x/ Y3 C* G0 l
    Tail Recursion) E3 V5 Q5 b3 g: t  [9 \" r- p
    & c; R. {: S! 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).% x0 _9 Q* |6 A9 Y; u9 _
    3 ~1 L3 Z1 z- ~0 G, Z4 ^' @$ t# v
    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-12-4 11:01 , Processed in 0.031483 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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