设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ' H& u+ E* O+ z8 N, Z; z
    0 Z( b& V: H! l! H' u% z7 @) e$ G1 N解释的不错
    ; S  n1 c" L% v8 K  u* ~* u$ z* ]4 M) D$ Q) c: a5 r$ ]
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ! P! p8 f  v7 x( D2 l
    0 u+ }  y1 [& Z) J. C 关键要素
    * n- N/ S, L) f6 E1. **基线条件(Base Case)**0 ?1 |$ u2 L, \3 |9 i7 J$ F
       - 递归终止的条件,防止无限循环7 D+ ^% F  U2 I  g0 H
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    # _+ j2 R8 w; I* X1 I8 ^
    2 M/ f9 F' M+ ?; l1 t6 A  ^2. **递归条件(Recursive Case)**
    % j+ ?% z! Y2 M- f8 `2 x+ u2 A   - 将原问题分解为更小的子问题% M1 }( H- L! L8 ?1 `% u
       - 例如:n! = n × (n-1)!
    . l. s  h( z% i% j& v4 f0 C. \2 A
    经典示例:计算阶乘* ?- v3 e. c/ \$ R
    python3 _. G/ Y# E8 F
    def factorial(n):
    , u$ w5 S% ?7 @) q) U    if n == 0:        # 基线条件) F- V, V; e% E4 A- z, L" S& k' ]+ z
            return 1
    4 s* D( m' S/ l) z6 `) b7 E    else:             # 递归条件: V5 t0 Z3 Y# C# y8 k( A' a' V
            return n * factorial(n-1)' t5 ~# f% a' z9 Q' P, L& u( I
    执行过程(以计算 3! 为例):
    - O  M8 ]1 ]3 A+ r/ Q1 q- mfactorial(3)
    5 [* k3 Y+ Y" }2 V, m0 b( _) Y1 i5 v( B5 y3 * factorial(2)8 D: J3 {  `$ q5 _" p
    3 * (2 * factorial(1))
    " O1 _; y. `4 G# {: m* E$ U. d3 * (2 * (1 * factorial(0)))  _( t0 J, h5 N. {2 a9 E1 |/ [+ `* }$ h
    3 * (2 * (1 * 1)) = 6
    / u( Q2 l' M. O$ ?: t$ q7 d
    + q* U) A1 Z5 V) t# Y, T 递归思维要点' h7 W6 s; w2 ^# K5 I7 c
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    5 H% Y. b! y' j, u# X, O: d2. **栈结构**:每次调用都会创建新的栈帧(内存空间)4 U* }" e, d0 w$ z* f7 q) v+ O- b" j
    3. **递推过程**:不断向下分解问题(递)* X3 k. W+ |. j+ h) Q
    4. **回溯过程**:组合子问题结果返回(归)
    . f/ y- {5 t" r( @: M3 S. t5 L
    : N+ A/ v3 E# X% V& @6 r$ Z 注意事项
    ' }# R4 P: S" m/ P7 S必须要有终止条件1 h4 h6 c, u; v$ x
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)6 E& T* A- q2 x1 Z
    某些问题用递归更直观(如树遍历),但效率可能不如迭代7 P; N' Q+ k  P, Z4 X, E
    尾递归优化可以提升效率(但Python不支持)7 H2 ^& K' U8 u+ n

    * y! s6 r$ j7 t8 P& c$ U 递归 vs 迭代  s! ^- i- M) A3 b4 [3 y
    |          | 递归                          | 迭代               |9 W9 W0 q, E1 {& u6 K  p; v
    |----------|-----------------------------|------------------|
    4 @2 c4 w4 j- _4 c! e8 I8 {| 实现方式    | 函数自调用                        | 循环结构            |3 U1 i- B7 I2 F- P/ c8 }6 q6 ?
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    6 Z  l* }6 ~8 k8 a& V| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |: ]2 F0 w$ U8 T  j
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |) S0 C; O- H& O* O  U, \4 ^# ?4 D

    6 Z' L7 z7 D9 P( k6 J! l6 A 经典递归应用场景8 y7 o  W% C% A- Q+ G
    1. 文件系统遍历(目录树结构)
    2 h4 g( _8 k9 t6 x# u2. 快速排序/归并排序算法5 X, [. M' z; w- R5 G3 P
    3. 汉诺塔问题1 _+ Y; \& r9 i. ^# J7 z
    4. 二叉树遍历(前序/中序/后序)
    % {* p" r  Z& ?: F5. 生成所有可能的组合(回溯算法)- m& N9 k9 F$ `0 E6 v# M8 M. B

    ; c1 T5 D$ V( Y8 ^% a; w: w. b: y- A试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    5 小时前
  • 签到天数: 3251 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,  k3 }7 V4 N6 p5 G
    我推理机的核心算法应该是二叉树遍历的变种。6 }2 d6 I- }. b' e. i: C/ [
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    8 i" X$ m# p: R0 x# dKey Idea of Recursion
    ! ]6 w: M0 h" X3 W: U0 O; l+ i6 e+ R; u4 S: t0 K8 j
    A recursive function solves a problem by:
    7 X+ h& v4 k1 Y, b& o: l2 D+ x2 y" I% g
        Breaking the problem into smaller instances of the same problem.; n$ j$ m, a/ P7 z6 w; J6 z% u0 U) m
    # i& R) I& _, N* {6 Q. X
        Solving the smallest instance directly (base case).- g  c% J7 b" \, ]: u& l
    % r( M5 k& S' E2 \; C2 c
        Combining the results of smaller instances to solve the larger problem.+ k5 }6 _3 ]" ]. Q& w

    & ~2 i+ s+ L5 [. O) g2 Q! G" cComponents of a Recursive Function
    2 g% K* i3 A  y8 {4 ]7 K& n) Y
    / J& N6 n/ R- y% F    Base Case:
    0 c/ P% G' @$ L* l* s
    6 J- ]: N# k8 ~8 N+ v2 u" x! B# x        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.6 J9 F( q. E! L' M3 B
      M5 x1 j. j- Z, Z" m8 S6 z
            It acts as the stopping condition to prevent infinite recursion.
    ; _5 N! r4 E0 K. P) I8 e2 r( `6 }2 u5 L  U5 _7 [$ {  ^% F# P7 ~
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.: E; i8 }* b* ~

    ( M: h/ A3 g7 ?7 Y5 @( V, v    Recursive Case:
    3 s2 @! [6 M  K* V/ u9 F* [8 @
    : a2 ^* o7 A9 ]" l$ Y; x% s: x        This is where the function calls itself with a smaller or simpler version of the problem.
    ' P  K" }& I/ I+ @) N
    3 G0 m7 c: W. U4 p! f8 i2 B        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    4 E: H  U. m7 R% t7 T7 p$ T3 _) v- R4 f2 h- |, @
    Example: Factorial Calculation) c- q' `" i8 s

    ( Q6 i+ f  x1 r* }; h& UThe 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:
    / [9 ^0 ~/ B7 {5 n, r& o- K7 @3 b9 H
        Base case: 0! = 1
    . q' H1 n" t- M, ~8 S& P% o! W, j. _9 {" x; P
        Recursive case: n! = n * (n-1)!
    ) y. [4 d6 d* [0 L$ o( P) f! G) g$ Y& x$ K+ j7 w
    Here’s how it looks in code (Python):8 n6 r( o, Q. U* X. N
    python* y0 r; }% n  `# E+ w
    ) r. ?. z( _4 i$ M$ x- N
    7 K; f. @) i  O1 k6 J
    def factorial(n):
    7 M) w, |; e% I5 k    # Base case
    5 Y- W& i2 B2 x" \6 r6 c5 S    if n == 0:
    ; M& U' v$ W  m0 l  k  i        return 1  b8 v' C- W- o* @& |' z: K
        # Recursive case' b  {9 [3 M+ o# f3 M
        else:
    7 {1 F; d5 S& ]% n! `: u6 |* l        return n * factorial(n - 1); P( V6 \8 \: z$ k) d
    , a$ O3 G* b7 A7 D9 W, G
    # Example usage1 g0 a8 o6 J3 b" M1 x7 e
    print(factorial(5))  # Output: 120
    / i! V2 f( |/ N4 c  C/ d2 q2 j( H- e! J, L5 C& ]$ [
    How Recursion Works. G  o6 ^$ R" Z& @# Z, J6 d4 B

    ( {+ q+ t/ y3 R% S; ^( Q$ Z# Y3 v    The function keeps calling itself with smaller inputs until it reaches the base case.
    % F0 x4 U: S# e1 _6 G
    ; w5 j* Z8 b/ H9 R- e" K; ~- a    Once the base case is reached, the function starts returning values back up the call stack.. e, N+ |% T2 |+ w

    ! Z& ?& P% s; Y$ c) ?. a- U; |    These returned values are combined to produce the final result.
    $ t& Q& w3 l# m1 t8 t' M  ^, O+ g" z. D! s+ l2 b
    For factorial(5):. _, G$ m  ?3 A; g# e
    8 x3 s9 M$ {( z. N/ x
    - v7 [6 A, Q; C5 _
    factorial(5) = 5 * factorial(4)
    3 ~7 U- G! I5 [, ufactorial(4) = 4 * factorial(3)5 E5 \; y( l7 \- W* r6 _3 J
    factorial(3) = 3 * factorial(2)& D5 X7 R6 \+ T& h; I: A: [
    factorial(2) = 2 * factorial(1)  u, a4 A0 S5 ]8 K7 o
    factorial(1) = 1 * factorial(0)
    8 ~) ?, W& @+ efactorial(0) = 1  # Base case$ }! T/ \- \5 l* G

    ' C5 D, g2 Q1 ^3 ?8 o/ f$ p$ e; HThen, the results are combined:' q/ U& y: F! q8 }
    # h4 Y! t4 q# x) a! x+ E
    ; o1 i1 G, u: T# E5 q) ~: [0 R
    factorial(1) = 1 * 1 = 1
    2 q' {- a* ~, w3 x( `factorial(2) = 2 * 1 = 2) n9 {8 F+ B0 L+ i
    factorial(3) = 3 * 2 = 69 z! M$ t  U7 b6 Q% }! V
    factorial(4) = 4 * 6 = 24
    ! c" R. o  ~  p$ S' B, ifactorial(5) = 5 * 24 = 120
    # A! V* S8 b9 _1 I9 t6 r; ^- H  E' x
    Advantages of Recursion; k/ G# t0 ~" a% U
    + `, M: G% e5 H" Y9 T
        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).
    8 G, ^: U( ^& V) H# @
      |; g7 D+ u; I" p& s5 F4 I7 y! e    Readability: Recursive code can be more readable and concise compared to iterative solutions.& T( Z# A6 N, Q+ b

    - ]) E: v% t6 a0 h3 H- Z6 v) hDisadvantages of Recursion( w+ k% m7 v3 K# J3 s

    ) K8 M( E) d  H9 J) X8 K& L    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.
    $ q8 Y9 a; h& {$ G8 B6 l. H/ y3 l# S! j
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ I1 c0 K0 {2 r8 N
    3 T* H, _* a$ c6 i( H9 g
    When to Use Recursion, G! c6 ?* r9 |4 W! A& u
    : V; C  r/ l1 M' Z' p
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ' E* Z7 l4 |( E- m) }' ~  F5 K, ?2 w9 N) J
        Problems with a clear base case and recursive case.
    ( ?3 m! k! C- C; j( @+ K1 e3 C' L8 V3 I
    Example: Fibonacci Sequence8 r( _9 Q* U3 E3 X+ c
    . H; c7 a) c% a: ~
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:' b: Y1 m" j2 H- i- R! Z3 E1 m  i

    9 V% [2 f  S9 Q+ j% `    Base case: fib(0) = 0, fib(1) = 1; m9 m% @- g7 a7 ^# ?5 }
    ( M  m  H( ~+ s& Q( x( V- I
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    3 N/ e) ^) a( R. Y1 W) ?5 {& [% f
      {1 Y7 i4 Y  x7 Dpython
    4 T/ a8 r; ?2 t2 g9 P" i
    7 Z' |) R4 K. L% Y2 N6 O9 T2 {# p
    def fibonacci(n):
    # J+ T, B+ W: x: L  C! i) S, K    # Base cases7 n2 p; B5 z6 }7 D
        if n == 0:
    4 m5 f2 {5 N, b' h+ m  x        return 0& ]5 E( a9 f0 B
        elif n == 1:
    $ W+ R0 O9 [2 A        return 1
    . J* T3 t; U4 Z7 G# E9 X: K. [) _9 N    # Recursive case; C& D% n/ Z! k$ f) N
        else:
    $ o% s* O$ @( Q, u# w. \+ ?        return fibonacci(n - 1) + fibonacci(n - 2): Z- k; O  K# w. ^, G6 I, T
    $ r( k, J8 X( f) Z2 Z
    # Example usage
    + a0 c( n1 H: I; u; Y* ]1 yprint(fibonacci(6))  # Output: 8  v. s+ V. k1 }& x* e
    # C  Z) w; X  b! `( Z' R5 O
    Tail Recursion/ L1 Z+ y) ~2 p0 W- N
    ! L: ^- G! ^9 B, }1 h% r+ W
    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).
    6 b% o; q4 |) @+ ?/ ]+ O4 B$ P; p( t3 c3 Q' m- {% K1 m! h3 y+ T  R
    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-5-27 12:55 , Processed in 0.057916 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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