设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    " [' D6 f8 x/ l  C6 B8 O1 h: Q
    0 l: N( y9 c0 A! U2 @解释的不错, ]4 ?- y3 d0 g
    $ {4 t5 k7 O! N" g  u+ a- `
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。; u/ v1 @3 k7 f$ V% A6 _

    ( j7 w% q4 o7 n1 R 关键要素$ H; o# u2 J8 `
    1. **基线条件(Base Case)**
    1 A: C( F5 _: L: M( k   - 递归终止的条件,防止无限循环
    " M3 ^- }" j  r3 M: X: S; E+ |   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1* v( Z; z5 J$ s6 T4 f7 X. u6 B3 x
    0 l5 l6 Z( _; H6 v4 F6 F
    2. **递归条件(Recursive Case)**
      A8 y, z6 v6 M' y" X- ^   - 将原问题分解为更小的子问题1 l+ X0 U& y' G1 C2 _9 r1 y0 i
       - 例如:n! = n × (n-1)!0 ~4 q) r1 \5 d; \$ O( _! R

    5 q0 f( N% ]: R 经典示例:计算阶乘  c1 Q9 R" q( U" H& n% v. E( f
    python  ~% p# I" q* o: H. |6 m* g
    def factorial(n):/ h, w6 s+ x- A, D, ]2 n
        if n == 0:        # 基线条件
    : j) S- h) j* E. k8 _        return 1
    * p) @% K. Q9 s6 [1 L9 F; W    else:             # 递归条件$ ~" V' C. {; Y
            return n * factorial(n-1)8 K; B* i4 B2 B8 |& O: V
    执行过程(以计算 3! 为例):9 q% t9 |' A& Y* Z7 n9 F* e
    factorial(3)
    ) e$ P  E" ^2 a, m  k% B+ M3 * factorial(2)
    ( f- H6 ~7 b5 f  {/ ]/ A3 * (2 * factorial(1))
    . k3 ?" T+ L2 R3 p0 ?3 * (2 * (1 * factorial(0)))
    , v2 d. T3 g+ v1 x) r; p2 X3 * (2 * (1 * 1)) = 6! u) L, E4 O  X: r7 E, F% Y0 ^7 g

    7 @; `  R% ^( q- p2 }7 G 递归思维要点4 T& f! q; h6 y" y
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑; ]2 S/ K; \7 j5 Z0 f
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ) Q: t/ Z0 S& Q3. **递推过程**:不断向下分解问题(递)) S% N. ~. a/ K) }3 W
    4. **回溯过程**:组合子问题结果返回(归)
    % @( @( C( l" n2 v# g1 ~' N; s# S7 Z! W- f
    注意事项
    8 t' m  z" f* Q! E! t" _/ d: m必须要有终止条件) c* h( R) S: {/ @9 Y' K/ ]
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    1 z0 K  c7 `: W2 V7 ^; U' i6 Y某些问题用递归更直观(如树遍历),但效率可能不如迭代' H5 a3 `6 E- S
    尾递归优化可以提升效率(但Python不支持)8 T$ P+ g. J2 p2 s7 ~- ^

    9 u6 d) g+ P1 N/ y# r1 q2 T 递归 vs 迭代
    ' M! a) E3 q6 k' @5 a|          | 递归                          | 迭代               |* p# Z1 E" o0 A" e+ x' `
    |----------|-----------------------------|------------------|1 a" M) M# _8 f; U
    | 实现方式    | 函数自调用                        | 循环结构            |7 K) y+ y$ Y& L
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    " K6 V2 |3 Q; H6 B| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |! M/ l9 C3 u% k1 V
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |( S0 y' @- O1 O
    1 o& C/ B! M& y% y' h$ @8 M/ _
    经典递归应用场景+ S% s6 t, w8 H0 H
    1. 文件系统遍历(目录树结构)
    & [" F& X" Y, z% D. h2. 快速排序/归并排序算法
    5 }$ y, Z2 a' V7 s9 J: H* S* ~/ s5 s3. 汉诺塔问题
    ( H" m  z- \6 I. x( p1 x; ?8 Q4. 二叉树遍历(前序/中序/后序)* g0 E" f. c: O( M* B* K; @
    5. 生成所有可能的组合(回溯算法)( G2 T5 C/ T8 o+ J- t; T

    9 H- x$ \1 |: {" e' H" V# l& N试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    16 小时前
  • 签到天数: 3110 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒," O6 C3 A. q8 b/ t1 M" v8 H4 W
    我推理机的核心算法应该是二叉树遍历的变种。
    ( N: @# Q$ D( E% }* P0 u另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
      D- t; |+ E" u2 KKey Idea of Recursion
    / x/ K" z/ r+ @* Y
      M. Z# P  U# o$ J& }2 Y! i9 p) CA recursive function solves a problem by:7 q- j* i: T! r6 x/ o5 q# |: S6 o  M  q

    8 R2 @; S7 l- T% N$ n7 ]$ c# r    Breaking the problem into smaller instances of the same problem.
    ) V. c( T) _, _2 V8 ~6 o% Y; o8 f6 S2 s( l
        Solving the smallest instance directly (base case).
    5 H+ u' w- J$ j# V! `" e
    6 X% l  S  S/ K2 A    Combining the results of smaller instances to solve the larger problem.0 d& ^  Z. h* F& ~. S1 h
    + C. {2 {% T5 K: A
    Components of a Recursive Function
    ) }" P, ~- T, d& u. j" r
    6 ^9 h0 q, j0 S+ `: m% G0 p/ j    Base Case:* V" e- g! \8 K+ ]) f9 ^

    . N$ L7 r+ p( s8 h+ W        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.9 T$ a0 k( ~" ~+ d: X* ^
      V( C: N7 J8 y! S6 Z; K. c; d
            It acts as the stopping condition to prevent infinite recursion.
    9 ]  j" Z( s3 |6 k6 m- B. L& A1 a3 G; v6 X: k+ I+ n8 k
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1." i3 k/ v' \0 Y# F. g6 ~
    2 h1 V5 l8 O! S6 A$ W
        Recursive Case:# E% R6 t5 B0 d+ r# w* l1 d

    + k+ P% y/ C- l7 I5 C        This is where the function calls itself with a smaller or simpler version of the problem.
    + w' O& F8 @0 V' L
    ( b6 L7 G1 Z8 ]. }        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).; v9 Q  S% F4 z) H% S& {2 b

    # z2 b0 Q; d; `$ n; `! T2 N4 MExample: Factorial Calculation; ?2 v+ G" R( f6 j
    , d9 Q8 j; d5 T* C5 t
    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:) u" B4 e" m& c4 o

    4 O5 l1 }6 I: i+ \    Base case: 0! = 1
    . @& w# h( S" T! g8 Q5 t3 G5 G. t5 }
    & c3 ]6 f' I! {    Recursive case: n! = n * (n-1)!
      u* ~; G( l$ G# C, x
    ' f5 {' a+ V+ L1 b) D+ f' UHere’s how it looks in code (Python):
    . N, R: S0 R5 Kpython/ R) @" s* H. w1 W

    5 g: a3 _/ t- `" e% N2 e" R. C/ D0 y9 P* F0 X
    def factorial(n):, [. h- S  h, V- l4 V
        # Base case
    6 ^, F5 G6 g# Q. K* }    if n == 0:
    & A" z& ^! k: o        return 11 z- w* ^) g: H; P
        # Recursive case
    # y2 O! A: {5 I7 u) N1 [    else:
    4 s7 N! N, t. H+ }+ a        return n * factorial(n - 1)
    0 w; U$ W1 o& P+ M8 M: W+ l9 N5 |' z/ ?4 G. s
    # Example usage
    , ~$ p& N' h; Rprint(factorial(5))  # Output: 120
    2 ^& V0 o" C# v0 [$ I3 e1 g3 p' l/ y& Z
    How Recursion Works/ B7 z% L: |. A' G

    " M+ I! o/ [/ `2 Q    The function keeps calling itself with smaller inputs until it reaches the base case.
    ! d' b- s% s/ R8 b
    % l* ?& D) P3 Y' f0 M8 Y% N# t. \    Once the base case is reached, the function starts returning values back up the call stack.$ O/ W& E) Y% D) v

    # I/ H8 ]0 i2 A2 u' ~/ {/ T    These returned values are combined to produce the final result.
    " G' [0 Z7 N- ]0 c2 Y9 X: P; ~9 N6 c- `# r+ w! }/ x' H9 c
    For factorial(5):
    0 y7 P9 ^5 a7 E9 V
    . a2 u  r$ o& B0 y2 G! T
    " g+ q$ N: q- m+ ^: S  ifactorial(5) = 5 * factorial(4)+ S- O" p3 `6 B+ |7 I  Z* c+ u
    factorial(4) = 4 * factorial(3)
    2 d8 L# o5 d8 u  jfactorial(3) = 3 * factorial(2)3 m" l5 i+ P/ m) V$ X$ }+ n
    factorial(2) = 2 * factorial(1)0 N# R2 l: M* K* `" e# f
    factorial(1) = 1 * factorial(0)
    9 |5 Q5 j  Y, N; \+ b* a) \factorial(0) = 1  # Base case. ?) Z7 v1 v8 @: N0 q! b

    ) E( R. L5 T3 }& r0 vThen, the results are combined:5 B5 v6 b7 Q4 L. p$ f: v/ M0 ~
    - Z! U# _' L& c) m( W

    ! j- |% i6 s  `: T3 c: J! ^6 {6 [factorial(1) = 1 * 1 = 1
    : ?3 U3 d6 S: z: ?factorial(2) = 2 * 1 = 2
    ( L, k7 T% x6 o1 x; H! q* P' o# @factorial(3) = 3 * 2 = 6+ K# N* F/ o$ N
    factorial(4) = 4 * 6 = 24
    ( n# ]( c7 q$ \. b. ^factorial(5) = 5 * 24 = 1208 g5 W5 Q' {2 S8 D
    5 M- o' I% S% U0 A
    Advantages of Recursion
    ' ^/ p5 Y* `6 G: c- t" Z
    & L$ }0 V0 \: e! Y. \' i    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).( o0 Y' m3 e3 y" B  a, `/ _
    6 A- o8 t4 U) D) w+ m4 u4 ~( U
        Readability: Recursive code can be more readable and concise compared to iterative solutions.) C4 x, V7 s7 g3 y
    ; i  S. G" X: n6 [$ e+ i; u  l
    Disadvantages of Recursion7 b+ S9 t9 C* h
    ' f5 [0 a- y2 X$ @
        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.! R0 R) N4 n0 l6 |; j3 H& s
    ) p* V; A* i$ N. R
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).. Y- T8 Z& I* y' n
    & s6 l: v$ ]0 z( b0 x  {
    When to Use Recursion/ M$ @& m- w$ M1 I* q
    & T* Q5 @2 p! N1 Y/ w$ e
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).' `/ c; X5 P% M) \! P

      E( _9 ?9 W7 }6 q    Problems with a clear base case and recursive case.
    5 f% U& h: C6 z* e  ~
    0 Z( S. m" ?9 Z+ M, pExample: Fibonacci Sequence
    ! w" D9 {! q# }& X# G, ?  u" y$ l5 E) s/ t' |' u5 D
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    , F0 N4 ]( x! x' g; {0 `. t& `! ^; A! y7 i; n. ~
        Base case: fib(0) = 0, fib(1) = 10 t7 R, i4 [! g5 G2 Q

    ; j( K( r! [1 m6 d: b    Recursive case: fib(n) = fib(n-1) + fib(n-2)9 O. a! Y9 H7 N& M# u

    ' {4 }6 ^+ U2 |8 D3 @python7 w' _8 z2 `  R2 j. b

    ' L2 V/ ^1 C$ ?5 f# D' d  `8 y4 ?5 K6 e: z7 M+ R; R9 f  g
    def fibonacci(n):) l+ ~5 [$ F, V% z
        # Base cases8 g1 P4 {7 m% }; g5 ?8 h7 b( A
        if n == 0:5 p, ~" k  L9 }7 d% n$ `
            return 0
    / j: y; \$ ]8 |( t, p    elif n == 1:
    6 j8 n1 D3 V! f        return 16 X# Q7 w9 H$ P6 T' m* z
        # Recursive case3 \5 e% _: {: ?! |. `4 d
        else:
    ! L$ l1 m' @9 S0 l5 p- V        return fibonacci(n - 1) + fibonacci(n - 2)
    , Z! P7 S4 g2 |# K0 M6 W1 B/ A
    , y  k# D1 V; x/ f! d# Example usage
    9 {) B/ S* o0 L3 Q6 ?print(fibonacci(6))  # Output: 87 d# [6 m# J, [8 I! f) v. _

    ) V& i& T% C, E7 a+ U! yTail Recursion6 m8 p( C' B* N
    ( ]: \, T$ d/ 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).
    9 ~1 O3 u  M% d8 f9 N( a2 _5 F$ F; }5 V2 }4 A; s1 F
    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-6 22:42 , Processed in 0.029514 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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