设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 , t7 c4 h" k; C- a+ E

    - B3 e7 ]+ d; t* T解释的不错
    6 @" S. |, J, ]3 Z3 e  Q. M( B# C
    * T: D. N& p* [/ c; B- f5 `  y递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    1 @+ [) _- N/ v2 N- l, ~3 C" t: R! R/ n8 J1 n% B
    关键要素
    2 Z. H) u1 }6 j1. **基线条件(Base Case)**
    ( C. W- ?& K) N* J   - 递归终止的条件,防止无限循环7 B* L4 m; f  C5 l  T$ P9 M
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1; o; P8 M! A+ w7 Z! K2 D

    " V" y% n; G) z2 U( _3 }, K2. **递归条件(Recursive Case)**6 Y7 |8 d4 [5 l7 q0 M. ?- ]
       - 将原问题分解为更小的子问题
    ) A3 t% U9 Z: i% m  \: z. Y. y   - 例如:n! = n × (n-1)!
    ; y% |) v- e7 c+ R; x% N+ L
    7 ^  ?) [9 P/ ]' i# X7 X/ ~. Y6 U 经典示例:计算阶乘2 V9 w. v; m9 U* ^
    python; r- C# i0 ?  L* s9 j4 C' W
    def factorial(n):4 G: G8 m: t& E  _/ J4 N
        if n == 0:        # 基线条件
    + }8 t; M0 W+ D        return 1
    / K' z* G4 p& P: s& t    else:             # 递归条件$ Z1 O2 o5 z; o6 G
            return n * factorial(n-1)5 |0 ?% u' K5 L7 Y
    执行过程(以计算 3! 为例):
    ; m" j+ ^! L" T8 t; m3 Ifactorial(3); I( Y+ U* b% ~3 I) `; C
    3 * factorial(2)
    5 z; W0 I, p2 D" m- B& Y7 B! k' L3 * (2 * factorial(1))% C3 r2 e0 g6 n' H
    3 * (2 * (1 * factorial(0)))
    ) M$ p/ g- I* L$ S1 i% V3 * (2 * (1 * 1)) = 6
    ) L# R2 j- Q( q; R+ t0 U; }% i( Q& U6 ^5 u# @) W' a
    递归思维要点( S3 ^% P' {( ^% X. S3 V
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑  ~$ g1 C7 Y9 t! w
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    - Y' h9 Y% e6 M9 A" o' v3 `3. **递推过程**:不断向下分解问题(递)
    ; e+ a! V' {" h( x) T. n- n) h8 I! a4. **回溯过程**:组合子问题结果返回(归)
    0 J! a$ o. D" H0 W) F* J6 ?
    & ?4 {  e- K( m4 S: ~6 O8 j! J 注意事项
    6 [3 S( S# v' v# T6 N必须要有终止条件$ w5 ^9 h/ j" a
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层); {  S1 G7 Z3 P9 ?: C  h
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    - n! y9 r1 q% C- c% w/ N' d9 B尾递归优化可以提升效率(但Python不支持)
    ) t3 n" e# Y; Y3 p6 P8 t  o" z% h( ?/ Q# G% U8 x
    递归 vs 迭代
    : T& ~5 y; D: p|          | 递归                          | 迭代               |! b- E- v! L* u: {/ b
    |----------|-----------------------------|------------------|' N8 T% V1 a0 S+ B) w, |: ]( o* B
    | 实现方式    | 函数自调用                        | 循环结构            |
    - U/ ?9 N  x% M6 [| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    " r+ h# I; H; Y/ J; y5 G5 f# o| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ! `8 s0 |4 b' w" [' k| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    : K. m6 t4 U7 W* e- N, ]& H5 V4 r# i: C4 {: D( }
    经典递归应用场景
    6 t' X& ]2 M2 O% x4 j! ?) G  H1. 文件系统遍历(目录树结构)
    1 D- \3 y2 F, y8 F4 r( R: c( |2. 快速排序/归并排序算法# x5 P$ t: t6 ~  n% b. k( g' O
    3. 汉诺塔问题
    , X. B# _" n+ \, ?( O4 q* b4. 二叉树遍历(前序/中序/后序)1 D  s# B, ^  \$ s4 y! K
    5. 生成所有可能的组合(回溯算法)$ R. \; G% c3 g9 r! x2 U3 L  @2 p

    2 f; g/ G+ H3 r* w; @5 I试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    前天 07:13
  • 签到天数: 3219 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    & j$ f* U8 S- \1 B' {我推理机的核心算法应该是二叉树遍历的变种。9 j$ _7 n2 v# b" h7 {/ }3 I
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    / [* H* I& Q/ M$ Q% fKey Idea of Recursion! T4 k7 ~& Z3 G3 U( S$ F

    , N" E8 R9 T4 t" @8 C  ZA recursive function solves a problem by:) k; x) b/ Y$ x
    / N# I, |2 S1 Y1 J$ s
        Breaking the problem into smaller instances of the same problem.  t& m2 [; O' R. v& ]) E3 b: y

    4 Q8 O( T: e" o$ q    Solving the smallest instance directly (base case).* N6 Y! g  E" h7 h5 T" H

    4 s1 i+ Z; e5 |' ?+ ^    Combining the results of smaller instances to solve the larger problem.; X* B/ c9 O: c# }0 g4 @

    7 k4 q& d/ S/ r" t! w5 c! rComponents of a Recursive Function
    + P6 N' L. G$ k6 q3 a, X
    . b0 I) M& G* ~5 \- r' n    Base Case:
    , W6 ^+ Z4 T7 `5 X! Z3 s1 _# k0 l# ?8 i6 h) P1 p8 C! I/ n" f
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.+ D! t$ D* }- Z/ V2 M
    : G1 T5 d) H7 T5 v9 H* J9 y
            It acts as the stopping condition to prevent infinite recursion.
    8 R0 A/ M" ^) Y# n8 v/ ]. d+ P% {% d1 X9 A: x( G
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1." m$ s3 P* D! f' b) u

    . m" f  s- u  a4 Q    Recursive Case:/ S2 s' B/ K- f# y; ~

    # @! ]+ Z; n/ u) L; L. r3 m        This is where the function calls itself with a smaller or simpler version of the problem., N8 g9 J, s1 K) q/ m; o
    - U- ^. X4 c: x! `+ `- p
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    6 Y" Q. t  y( i8 V/ h
    0 [2 h9 q& z5 ]6 b8 W) VExample: Factorial Calculation1 q0 ?) _1 q' j# M5 q& {
    * r" P( a( X0 E* t" C6 u! v. y
    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:
    ; X( a" {, b9 E2 P! P
    $ e$ F1 R% v, }3 o& Z    Base case: 0! = 1, d. H3 ^" G$ i# M. R/ X; \

    8 t( Q+ \! U$ S# {# p6 ]    Recursive case: n! = n * (n-1)!
      A6 R5 [8 d$ x4 h5 i. @" ~) S' t+ p( Q" @: R  v
    Here’s how it looks in code (Python):
    ' I! N* P8 A& S' ?- Lpython
    4 Q9 L8 w/ I6 O( y9 c
    ' F8 z: J1 R6 I) E! A, f% z/ z7 Y/ W0 q) j8 ?1 B1 @  Y- E% L
    def factorial(n):$ O4 V3 N4 r( X3 N8 d0 ~2 Z
        # Base case
    ' B! A8 x0 |$ J" g2 N, N$ A$ p4 ^    if n == 0:) ~' E( P4 N2 T, B$ m' v3 [
            return 1
    2 L+ z9 J7 Q$ G' D% N9 ]- t+ R& W    # Recursive case, @8 V# F8 O% S3 y
        else:
    9 w4 q; N  Q  ]* w; x! I+ T        return n * factorial(n - 1)
    : s! K+ ^7 U0 ]2 E" Z
    5 _5 g9 E( C4 D6 L# Example usage( y2 M0 t: m, Y- u3 C- B
    print(factorial(5))  # Output: 120
    8 @( j5 _/ T9 h: ]$ v
    ! @% c3 ?$ Q2 T, T5 P  l8 i! A+ D! VHow Recursion Works3 j! E2 n# \( D" O. o
    0 ]! z/ h- }) A% N" z$ L& @
        The function keeps calling itself with smaller inputs until it reaches the base case.
    4 N. d/ H. f" f) l$ H0 ^( _& ~; x4 ?# C! q! `# }& @0 F
        Once the base case is reached, the function starts returning values back up the call stack.; B9 q  ?9 W% b& Y4 b6 c2 v* L

    . A  H2 g  X7 r0 O) l; _8 v1 k    These returned values are combined to produce the final result.
    + u% B2 b" l& |$ L2 |# m
    : p8 E. D) j8 M* @$ eFor factorial(5):
    & Q- K/ A1 t( K( u7 ?6 x& V! q
    2 j; b* z. v5 t1 Y0 S8 I' V3 m  ^: M- }+ X" Y, h# A
    factorial(5) = 5 * factorial(4)# T& f. r  t9 A$ L3 F: T
    factorial(4) = 4 * factorial(3)
    - i6 R: Y1 r$ M8 Kfactorial(3) = 3 * factorial(2)7 @$ Z' M. Q: E! |! W
    factorial(2) = 2 * factorial(1)& d4 w9 {4 A" J7 p0 D; M
    factorial(1) = 1 * factorial(0)4 {8 E" Q7 O2 k( a1 O% A
    factorial(0) = 1  # Base case
    ) P' a# |: A% }6 u% Z5 b4 x+ T
    9 {, H' Q5 y" X0 NThen, the results are combined:
      d6 G6 \$ |$ G7 R
    2 s7 O' s/ o4 z5 F+ f" i
    ( ?: k2 y% e; @: Y* ffactorial(1) = 1 * 1 = 1
    5 H) e: M8 h# @- D' cfactorial(2) = 2 * 1 = 2
    ' _0 T  V# B6 E' O, Tfactorial(3) = 3 * 2 = 6
    8 d8 `6 X8 R. w- A1 z( J/ gfactorial(4) = 4 * 6 = 242 y& W* E; c5 z$ _' U" O
    factorial(5) = 5 * 24 = 120
    8 D9 g9 T1 \) x) }
    , K6 e) Q% I) o/ Y& [Advantages of Recursion
    1 e  ]  v5 A$ g4 ^* @9 f, n0 b: e+ i* I6 Y. N2 [* 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).
    % G" q& z, `$ U3 f0 g& b3 x* e- C" Y2 |% A7 I  V
        Readability: Recursive code can be more readable and concise compared to iterative solutions.+ |: ]8 d: r& q  N5 R+ w
    $ o% c( C: _4 f$ [# t9 x
    Disadvantages of Recursion
    7 B! }4 L  `; t' k- A' H1 @; h9 p$ c
        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.- L4 B; p) B$ u: {3 p* G
    . Z' b$ M' K. h8 u
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    - I7 f, X' ?" P# [
    3 c+ a- o$ D/ aWhen to Use Recursion, m2 p, R1 j% Y9 L. M

    0 N5 v* r6 h6 _, |1 ]: ^- G2 M9 b    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).7 ]0 L2 @1 G( B9 o! @! H+ L
    # G9 C/ j3 a: U! ]
        Problems with a clear base case and recursive case.
    % Z, Y, A! a6 q& `9 |# P
    , _' z6 m: a  B( QExample: Fibonacci Sequence  W2 K! M+ g7 w4 M& _: G' ?- @9 @0 F

    ( T5 Y) I0 B7 c* r, A# SThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:2 q5 I5 w( U/ M& l' p+ g. N) q/ q

    : L$ k5 A& G. l  k  j/ I' v( \8 R) `    Base case: fib(0) = 0, fib(1) = 1
    : h  `6 _+ G' v, P. E* U5 I; A4 w( \( r4 U
        Recursive case: fib(n) = fib(n-1) + fib(n-2). V$ a4 K3 D6 U7 H( f" T! h, d
    ; B7 l4 r: g$ C
    python6 z" Q4 `) Y7 [6 N. w/ U

    & a# m% ^  q2 B6 x6 O2 G; k5 ^. d! l" Q1 |3 I) c+ i
    def fibonacci(n):0 T# U, W0 z6 w# D5 z; J4 N
        # Base cases% I9 Q" l" `# A  }3 Z% N
        if n == 0:
    # W: y0 i) g/ f' B- M8 r        return 0( S1 k! t0 n2 `  w
        elif n == 1:
    8 V4 v1 C' F) [! `        return 10 O- K) Y" i; d' S
        # Recursive case
    8 D' k- n5 W4 @    else:1 Y! T; a; y1 S
            return fibonacci(n - 1) + fibonacci(n - 2)
    % ?& [: Y$ R& h& A+ J/ K& ^3 S, H9 L0 E3 ^& i+ I+ j) I) v
    # Example usage
    ; |, x: k) t" `1 ?print(fibonacci(6))  # Output: 8. d7 r8 V; t+ [0 L7 D) i$ \
    - J4 p4 c+ J& X
    Tail Recursion+ }0 ^/ W* P8 _( J4 Q0 E* p

    0 S; K! V* n! f) `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).: y9 s* v1 ~0 U

    3 c% t$ D* y1 [9 p& a* s* lIn 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-4-20 10:41 , Processed in 0.079730 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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