设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 g* X% B( D( x( @2 D/ \) e- i' v
    解释的不错
    + P# U  @9 k) s$ L* R5 w
    7 o1 S' ^( h; o2 i递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。5 r6 L6 _# X9 ^9 Y# @0 T: C
    ; V% J" _$ {# l! o# K. d% Y
    关键要素% x. d- V3 C! \% ?
    1. **基线条件(Base Case)**
    : D+ h5 [0 ^# s) N# ~  j   - 递归终止的条件,防止无限循环
    8 ^" E8 Z- b' G# U" N6 |( W   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 19 t2 Z* Y4 i. y* u( l

    5 |& ~( X' x& a7 z5 z' l. b* J$ f# e2. **递归条件(Recursive Case)**2 D' V; v4 c9 u" ~4 O
       - 将原问题分解为更小的子问题3 k9 e1 o7 ~" }# G3 F) B
       - 例如:n! = n × (n-1)!
    $ L3 R, \: G8 i8 j0 x
    ( H6 R* F/ _  [. n 经典示例:计算阶乘
    4 ]' L0 M3 \* s0 [$ G- s! x3 \0 [; N9 Epython
    + T" |5 l* z% r' b3 qdef factorial(n):' r1 }) n: g7 K3 o+ P3 r) ?
        if n == 0:        # 基线条件
    4 ~; [$ Q% K- k- M        return 1
    . @/ W- m& h- C+ d" E- M    else:             # 递归条件7 G; ]) d- @1 L1 I) y$ q
            return n * factorial(n-1)$ B! {/ n. ~4 O7 D4 s! Z7 C- o
    执行过程(以计算 3! 为例):
    ( ]" `! ^7 i9 Z  U$ Efactorial(3)1 f9 X: i1 M$ \; n  g
    3 * factorial(2)) O- }- h: r. R  a
    3 * (2 * factorial(1))
    3 ~4 |4 }; j9 G& P; r1 u6 t3 * (2 * (1 * factorial(0)))6 Y7 y' S- p3 n. ~+ h4 Q
    3 * (2 * (1 * 1)) = 6: z* A% D$ `5 w! p( G/ F

    & j' F( ?$ F* l$ t 递归思维要点
      D0 g& G$ B+ y# r1. **信任递归**:假设子问题已经解决,专注当前层逻辑9 C0 t0 l9 q- O* C7 U& @' _; v
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    7 P6 Y6 ~) |6 A  v- Z3. **递推过程**:不断向下分解问题(递)
    / l6 ~% s+ {" @1 m  q4. **回溯过程**:组合子问题结果返回(归)! O. N, h7 j& N/ F8 \1 V
    * [0 f, {9 Z6 H& I. l
    注意事项; `: v* h2 n6 N7 ^, j8 n
    必须要有终止条件
    2 E/ S- B) N1 |: _6 `2 t递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    * j) o+ R9 i8 d, N某些问题用递归更直观(如树遍历),但效率可能不如迭代
    % P% y) m, e# m) c% {1 K尾递归优化可以提升效率(但Python不支持)8 J1 ~. `3 s' y# o" x; {; k2 p1 v
    " {  ]% g+ \3 R0 |+ i( v
    递归 vs 迭代  H. S, {* ^/ ]+ d/ U, X7 K0 d3 C
    |          | 递归                          | 迭代               |
    8 I7 I% W* v% \1 p7 S7 V|----------|-----------------------------|------------------|
    & Z  r% ~7 m/ s: Q! Z| 实现方式    | 函数自调用                        | 循环结构            |
    ) I4 p" S% S; L' x| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    " x4 e& q# u9 L: \| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |( r4 @9 x5 j  x& X) g+ a3 j% h: y
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. N9 l; g" H$ r- M9 ?: y

    2 |# M* G5 o9 C/ l 经典递归应用场景! C2 @) a9 @4 [
    1. 文件系统遍历(目录树结构)
    8 c1 B3 h+ q- e  }2. 快速排序/归并排序算法% m$ f1 t) c$ q* V, f" B# Q$ I
    3. 汉诺塔问题
    ) O: e0 o* N" v/ p' J' _! R4. 二叉树遍历(前序/中序/后序)
    7 t/ m+ E: _: p5. 生成所有可能的组合(回溯算法)0 Y  v. K+ W+ p6 z) O9 t

    ! U' l5 }' A9 k/ s, p0 s' A5 y4 p% P试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,7 l0 ?2 w1 _* x
    我推理机的核心算法应该是二叉树遍历的变种。
    1 q+ s# M2 s, x' O. D! Y6 R另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:: k2 u. Q1 _3 s! }$ m
    Key Idea of Recursion. V9 x' g: V! o
    0 f( |7 j4 b7 C# V1 X
    A recursive function solves a problem by:& a4 v& }9 D  j* B

    6 Y# ?, T$ [( G6 f# {8 T0 i    Breaking the problem into smaller instances of the same problem.1 N. d9 N" K- m+ m- \& f2 v

    3 ?- [0 E5 N7 Y4 x" [* T5 |+ `  l    Solving the smallest instance directly (base case).
    - A  w9 e; t0 z4 |2 m5 l5 c0 l1 i, G; p; z  H* ^4 I6 e' T" s& C
        Combining the results of smaller instances to solve the larger problem.
    - e, _; ^/ r2 y* c8 `
    ) w1 Y3 Y3 Q1 g! PComponents of a Recursive Function% f5 O, l6 Y; |; o* k

    ' `4 @. L& ]/ a+ c9 m, R5 \    Base Case:
    * Q$ Y7 ?4 a! d* f
    4 g' ]6 z) P. R' g6 L+ Z        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    0 E# ]: N1 K0 r$ b& v- m7 l. C  o  w; m) G1 K1 {" V
            It acts as the stopping condition to prevent infinite recursion.
    + Y3 |5 }- I6 l9 t9 O+ T6 o; a4 B  ?
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
      l. H5 d" O& O7 L' r& H# D- g3 S$ H4 l0 ~! H
        Recursive Case:% l4 J0 K( O/ o. j' K+ D
    3 L' O% X* s& f* t' L
            This is where the function calls itself with a smaller or simpler version of the problem.0 x4 S3 G$ B0 }) y% v: M; e+ l
    . V) Q7 {: @4 i0 r7 @0 A3 E1 {1 D( G
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    $ g0 H1 C" Z$ B; R# {. G8 ~( H- G- b+ J7 f0 Z: |% V
    Example: Factorial Calculation' V) l. y. e1 f0 K/ T: G
    $ p( w* {/ V& i) k8 L3 C  |
    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:
    ! z" y/ L' j% j! m3 P5 y3 w6 H' C% K8 B% Z  G% V/ [/ c0 U# O
        Base case: 0! = 1
    9 n9 s7 [* {& w. D; T+ M# P6 E
    $ E# F* m" s/ n  v: @. t    Recursive case: n! = n * (n-1)!
    % g, |  Y6 L; v9 J8 i" G$ M9 N* E1 Y5 `/ l2 t! d# s6 P* K
    Here’s how it looks in code (Python):
    7 \5 p+ ?. O% c: ^/ A, t8 d" k# n5 z$ ]python& {% x5 i( \9 J/ m5 G( B' @3 N
    7 k% D4 q* U$ H

    : F$ L1 x% t& X) }7 {% m- i3 x2 udef factorial(n):. C2 `3 r: M" M4 t9 F* C* X3 T' S9 L
        # Base case9 Z# W& y6 A* c; k
        if n == 0:
    : k& z9 W& W, J3 K" l7 J; ^* f% l5 S& P        return 1
      |" U0 o) k6 r    # Recursive case' v! j; C& t+ K+ s# f% W
        else:9 d# Q" d4 P+ f( s% O/ q7 E
            return n * factorial(n - 1)* @( k1 `2 u! V! e8 t7 r8 v

    / m: n; Q$ u9 J; `, A# Example usage
    & J7 s! B2 D3 K1 n( aprint(factorial(5))  # Output: 1205 Z( x7 K: A4 E) B$ }! S
    . o- }  u2 M$ ~/ n
    How Recursion Works4 g" y/ o3 R1 F' u6 j7 c! I
    * X& Z( ?7 O  {4 ]  k
        The function keeps calling itself with smaller inputs until it reaches the base case.% d" m+ |0 ^0 j9 T$ W
    9 L9 |, K  H) U* j) O! Q+ z
        Once the base case is reached, the function starts returning values back up the call stack.
    3 E9 W- |. h2 d; |; U! R
    ; R, }5 l, G; D    These returned values are combined to produce the final result.: Z# Q5 b1 T7 |. o) s5 T- S! [: i

    & X5 F1 ]5 T' wFor factorial(5):- O0 a7 ]3 N) e  M. Y, O

    ; ~: f+ A, h; H! i$ {' J3 Y
    3 Q4 [! A4 m; c3 \5 _9 L# c! k1 Mfactorial(5) = 5 * factorial(4)4 b* m) {) D2 E& X/ Z8 b" X
    factorial(4) = 4 * factorial(3)
    + G5 H+ ^( A, Tfactorial(3) = 3 * factorial(2)
    * `) u/ _3 T: A0 Qfactorial(2) = 2 * factorial(1)" \4 H5 n: \" O. h4 R
    factorial(1) = 1 * factorial(0)- X7 r( Y% Z6 t* g+ Y! S
    factorial(0) = 1  # Base case# {/ N8 r3 h. [( z% T' t6 |
    3 r% N1 z) L, d1 d: S% H
    Then, the results are combined:6 n6 a. W& \% I* _

    5 z# B% Z7 z5 c& g' c- K9 T
    2 y# c% a/ m$ A. |% n' O+ h3 Zfactorial(1) = 1 * 1 = 10 F) A  Y' f/ z
    factorial(2) = 2 * 1 = 25 \$ K, H) D0 T! m9 e8 G
    factorial(3) = 3 * 2 = 6
    4 t- \% x* s6 X* U# ^: Jfactorial(4) = 4 * 6 = 242 R, E" D" N/ z4 h7 K
    factorial(5) = 5 * 24 = 1205 ]2 y- ?. q+ d0 p( F

    * V" F6 o" q% V2 RAdvantages of Recursion/ v3 P; x' G+ }, i2 X$ s# E

    $ r$ M# t/ Y% M( w7 }  E& p    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).2 V& _1 A* j4 H5 }/ g  j" o

    - G0 }! h% I" n9 ]* o0 [* q    Readability: Recursive code can be more readable and concise compared to iterative solutions.* J" V) G9 e' h6 e3 D

    ( W; }# ^& ^! A- [Disadvantages of Recursion
    8 Z& r# I4 c7 Q. G& d; F
    4 i2 U) G; u; T) a    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.
    6 Y7 y. c' E& f
    ! q; t& ^5 G1 d! I3 L3 |9 w  R    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).3 ]+ }5 [: n# H7 L
    . D/ U/ l$ l: \' r2 E# v
    When to Use Recursion: S2 n( O2 m! i' [
    - M; J" J. a3 U; T: \$ g7 ?( _
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).3 F2 {6 D; A- h( O& Y

    / B3 }; q( u9 m: P$ d: N- [* G    Problems with a clear base case and recursive case.
    + n" J# D9 L! ?5 `9 a$ a; j  v: y
    * c5 x8 W2 u, iExample: Fibonacci Sequence
    & L! E. e4 p" z: o6 U% C3 k, o& [/ I0 @- \3 a9 C
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:& }( z. g8 d5 n

    ; n: ^/ F2 D. B% B    Base case: fib(0) = 0, fib(1) = 1
    % s7 r5 ?, d) d) X+ {9 ~# u6 t: k4 @7 Y0 g/ G& G; V# R; L
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    / O! d9 Y/ E4 B4 v" R) U/ `! u; U7 V7 k2 J4 f9 N! u( b1 N. F
    python( O  D7 M8 B8 v6 D# \
    + O; D8 ]3 B( L+ y

    ( {2 |, G' ]3 Z5 H& xdef fibonacci(n):
    3 c' _0 C; k; S  X) k3 {5 s    # Base cases
    2 d0 J: ]/ L3 \) e) P/ b    if n == 0:
    % s# Y/ P/ I5 S5 l% U        return 0
      u) F& H% q! G3 d$ q" Y    elif n == 1:9 B1 l+ O# M/ I$ h8 i8 r
            return 1
    9 T9 B# M: ^* K6 W* J    # Recursive case
    ! s6 N* I, {+ E% W7 X    else:
    * M  ]! T) B: m" z: ^        return fibonacci(n - 1) + fibonacci(n - 2)
    2 w, Y. N' ~/ v9 m, n6 b# x( z0 R! \6 d0 l' }  Z
    # Example usage3 O9 W6 }, L# X+ C4 T/ ?
    print(fibonacci(6))  # Output: 8
    . C" s8 K& k6 L# N% }/ q  `
    + A1 b3 a1 r) O. a+ zTail Recursion% O- y4 V$ H8 _/ Y" D( o, b+ f( s
      v# [+ q6 H3 n/ {- C
    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).
    3 A, V+ G  \4 L% k
    * H1 `# h2 ?! s3 jIn 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 02:15 , Processed in 0.030104 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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