设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 2 W5 Z; k( P7 f8 q+ h1 I

    % R: k# k+ Y7 c2 \' [( a. m" F解释的不错
    9 L: ~& X  C8 k& Z
    4 q. [: K. S9 N" Q+ [递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ( k/ x- s" P. {" l
      J' X! B# ~+ x1 g2 P  P2 F! } 关键要素
    $ y  K' y7 f( [$ j- y* r1. **基线条件(Base Case)**6 k! v7 M( y$ t- {! P' R
       - 递归终止的条件,防止无限循环
    6 u" h& ~1 ]) J* \' R   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1: E" w* P% Y& ~

    ' ]& A1 o/ C! a# x: r2. **递归条件(Recursive Case)**
    0 F6 H4 f! {$ {( P& y  K2 I0 |1 C   - 将原问题分解为更小的子问题, h, c7 r! Y* u% ^$ B& A
       - 例如:n! = n × (n-1)!
    8 @: X+ d* Q+ h' H8 t
    9 Q; K9 }! g9 B. o' f& i" w 经典示例:计算阶乘8 E, X- w% l( N. h3 T3 e+ S
    python2 h; p. i, c: S
    def factorial(n):( U; V. l3 p* H# r- m. [, C
        if n == 0:        # 基线条件
    5 `) _3 @) {  s0 X9 m  O* r* E        return 13 x1 ^: K1 F2 N1 W1 G: {4 e
        else:             # 递归条件! s2 V* r! ^' Z
            return n * factorial(n-1)7 r2 b/ ?2 B* j, A6 f
    执行过程(以计算 3! 为例):
    . Y. x6 Z9 u, m- ?3 ofactorial(3)2 V! X8 i* z3 a
    3 * factorial(2)' s5 w1 t! x! r2 I3 h1 W
    3 * (2 * factorial(1))
    ; d/ `( H, p* L( R+ P; S& _; s3 * (2 * (1 * factorial(0)))6 W/ g4 L& |5 W! Q* @5 N$ |/ M! E
    3 * (2 * (1 * 1)) = 66 d  X$ ?. V" v
    5 j; H$ p* ~3 W6 ?
    递归思维要点
    3 Z% q. M& b& @' Y) w- Z* P1. **信任递归**:假设子问题已经解决,专注当前层逻辑6 ~; g) Z0 k' e9 H  R) ^7 U
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    & o) l3 _) q8 Y  \* X- O/ F3. **递推过程**:不断向下分解问题(递). ^/ ~, c( a  R* Y; _
    4. **回溯过程**:组合子问题结果返回(归). p, B9 l/ s6 B5 l+ y

    . B6 j/ C& T6 v+ \0 R 注意事项" g6 \% \, `5 s5 x0 j6 i+ t
    必须要有终止条件
      z  I' F/ e4 m% J  ^递归深度过大可能导致栈溢出(Python默认递归深度约1000层)+ m9 d  {* u: `9 q, E: Y" k
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    * r- \5 `, @) c. y8 i  L3 ?6 E& F尾递归优化可以提升效率(但Python不支持)' A3 H) g$ v3 O

    5 `! z% x9 U) p0 H% r! n$ o 递归 vs 迭代* v1 p- ]- w% Y) C% H) _9 W1 v
    |          | 递归                          | 迭代               |
    5 S, V. U, j% X& x6 c3 A|----------|-----------------------------|------------------|' W3 }3 k' D% Y, I& {- u  Z1 M+ z
    | 实现方式    | 函数自调用                        | 循环结构            |' J) f: D! ]' U3 {2 s
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ! `/ \. o: @% }) ?| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    4 R; L0 `+ N, F6 c- q1 a3 l3 f3 k| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    + l" p; T  o3 _' n& ?1 u$ j5 h% \0 s; y9 ^& U, Z) j9 ~
    经典递归应用场景% m  L( E6 E* ^7 s8 V) P: w: T" T
    1. 文件系统遍历(目录树结构)2 T; n: Z: ]" [: _
    2. 快速排序/归并排序算法2 S4 V# G+ W" A/ T' D" a
    3. 汉诺塔问题* h3 U: s3 o' p9 b
    4. 二叉树遍历(前序/中序/后序)
    " L  {7 O) r+ z8 b* ~% H, j3 n( w* R5. 生成所有可能的组合(回溯算法)
    $ Z8 N7 j% r* G# T& H* s, r$ t: i. P9 V$ `! E2 Y! B  I# N( H* X! s
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    3 J7 f0 F& z7 [1 D. q9 ]我推理机的核心算法应该是二叉树遍历的变种。
    , ?8 ?* A5 l/ x2 D* \5 M  `另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:4 \1 w' b, @6 j8 [
    Key Idea of Recursion0 E/ N  X6 l8 h: @# m
      U2 J, B( O0 e0 S0 X
    A recursive function solves a problem by:6 e5 A  j$ z2 q. e, |$ C) m
    ! l0 S2 Q5 D7 p% a# U' L; Z6 ]
        Breaking the problem into smaller instances of the same problem., U: E1 }! R5 N# g, r1 A
    ! w8 y! S; y% p/ U8 v* }0 H
        Solving the smallest instance directly (base case).
    / K+ u6 P0 R, d( Q
    % h- m" r8 D- K* I    Combining the results of smaller instances to solve the larger problem.
    . c6 D  T/ w4 q7 l$ C* ~/ @% I/ G, n3 E8 K" p& l7 ]- p. ~% G
    Components of a Recursive Function+ v; C0 I; c# R- d& k* k
    2 \: Z. e+ s& J) {
        Base Case:; t, H6 r) R" \6 ?: l6 S8 b% D; c
    * \; D1 a# q0 H* x. k: ^( r
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    , T$ V+ y2 R6 C2 P1 E" v: A7 U' P+ r& i5 ^$ x- p
            It acts as the stopping condition to prevent infinite recursion.; ~( y( J& h5 G
    6 g9 W7 C9 G2 t! S; m) O2 H" P3 V
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.3 J8 U, [; G' c; M' i( A6 ^

    6 C6 y* ]& `# E    Recursive Case:
    " w0 q! T0 y7 N/ z' Y& w8 k4 T1 L* P# E9 {1 x4 e& l% s8 B' _3 L- K
            This is where the function calls itself with a smaller or simpler version of the problem.! }' u3 v. C% Y* p5 B

    ! K0 c9 p' P" c; c, `# `. ?        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).; k" ]5 [- \; \7 ~

    , I5 C) U$ T9 F* y! B/ c$ X2 |Example: Factorial Calculation
    : q' W. ?8 [: C3 t! b$ K% C3 p
      s: T4 u+ t  E) fThe 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:5 G" ?4 c0 h4 {8 v

    4 _8 W3 o0 u: [1 i& O3 E! [    Base case: 0! = 1. \5 B# Z! x0 B- Z

    ( V, ]7 L/ S! M    Recursive case: n! = n * (n-1)!
    ' V4 g6 p( w4 N, i3 d; ~4 Q6 v
    1 U' t* a; L4 i, {Here’s how it looks in code (Python):
    $ M/ g# Q, O3 v" U" Vpython
    6 |! P' d* ]/ N7 J' V. U; d8 T! C! y; i- l7 R7 U) n

    % P5 f. s* s9 idef factorial(n):
    , |' ?8 Y9 ]4 `7 t0 l& U6 n    # Base case
    - @# P! G6 M* N2 q3 J  L4 r2 b    if n == 0:
    # f. D+ o) N* ^* q2 h        return 1" j& e) Q- x5 I' x, g- \" C. h* Q- ]
        # Recursive case
    # F7 x' I& L* S5 m    else:
    3 F) L4 w: ?. h7 ]        return n * factorial(n - 1)" @! P' i% O8 F3 e2 d4 d, c( o  V, N

    . n+ H$ B, I1 q7 k% [+ L) ^& X. y# Example usage% p) t3 T6 o6 D3 b
    print(factorial(5))  # Output: 1205 G8 O: M0 Q- b: V$ X0 O3 W
    7 W# a- t5 |6 u
    How Recursion Works
    8 _5 J: n1 H5 g- j. B
      G7 u/ c/ o3 |5 }. {    The function keeps calling itself with smaller inputs until it reaches the base case.
      p: J( K* _& n4 t
    2 X( H% o3 b) n0 g; g    Once the base case is reached, the function starts returning values back up the call stack.
    7 H4 Z  f& O) D
    1 K6 Q% d7 [  `' t    These returned values are combined to produce the final result.* X9 s' e, K, V. z1 ?& b( b
    2 z: E1 _/ K3 t5 _& y. g7 [6 R1 J
    For factorial(5):
    3 K* Z: s$ V& g: J7 J. G! I; w4 M' I: s8 V" {1 q+ Z' X

    ; o! A( K  x+ Lfactorial(5) = 5 * factorial(4)2 a+ d6 ~# r3 |
    factorial(4) = 4 * factorial(3)( E2 v$ W( w% _# O+ i9 r0 X3 E
    factorial(3) = 3 * factorial(2)
    # N9 Z; z0 B7 N! D2 O, cfactorial(2) = 2 * factorial(1)
    6 n6 e( D" N$ Q# i1 E% |factorial(1) = 1 * factorial(0)+ T* \) I. h2 p/ e6 }
    factorial(0) = 1  # Base case
    : q* w* s8 ^$ G! D1 b7 ]* }4 O4 [1 ^
    Then, the results are combined:" e1 x# `* P! ]

    - P# ]- \7 d" o" I9 x2 U
    4 a6 o! i0 h9 i0 y0 i8 y# tfactorial(1) = 1 * 1 = 1
    7 F  c/ \* v/ D8 O3 h0 a# xfactorial(2) = 2 * 1 = 2! t" ~' [. e" f3 N) [1 y
    factorial(3) = 3 * 2 = 6
    ' ?: _+ k- g* d5 I" ^4 @& Ffactorial(4) = 4 * 6 = 24
    " c3 p1 v6 l1 ]! p- e0 y/ c5 kfactorial(5) = 5 * 24 = 120
    " F3 b4 |( |$ a; D6 W; ^
    + H3 I" D; p6 FAdvantages of Recursion
    9 f  k; Q& k# @0 n; Y% I+ i
    9 y3 Z2 {/ h, |" q! x& t1 F3 H    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).
    " `9 h* V* T, v
    ( Y3 G- N( a! T    Readability: Recursive code can be more readable and concise compared to iterative solutions.* z! A. K4 v9 N5 n) P* K7 ?# }) Z2 z9 c

    7 j4 a; I) ]2 n0 z9 QDisadvantages of Recursion3 K' Q* K- P  T4 E5 b9 e

    + o5 t" O6 W. Y6 I. G; q, d    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 Y3 \1 T6 U, L8 I: p' n: N$ L
    # C3 j  `& Q8 K$ i) ]# }' D2 ]
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    + V7 v/ I7 ^# A+ t* ^7 S% N' o6 b- z! s$ n; I# n* d& A
    When to Use Recursion
    : {" F1 V4 ?) ?3 W0 H  h5 h( X
    6 s* n7 H6 u, G' |& \/ O$ B    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    & x- O) i* d+ s) d* e6 |3 T4 ~
    ( X  |, p' h- X7 _6 B2 j. Y0 {    Problems with a clear base case and recursive case.
    $ s9 C1 Y# c7 K2 A/ y7 ~: _) {
    ! i, y8 g2 }  i3 w: |  IExample: Fibonacci Sequence0 n8 ~5 P" r5 J2 E

    ) X/ P* P- J2 y0 o/ K1 IThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    6 v5 y3 v+ o$ A, g/ r: Z, U$ u& ?, g" `! E1 a
        Base case: fib(0) = 0, fib(1) = 13 P6 o* O5 `, C  J% v: |
    # Z' f! U9 O6 U' s3 I9 r
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ( N0 X1 N: s, B- ]4 p
    0 F4 ]) B, {/ w( I2 i% @. c; ^! |% R7 epython: k& `3 F: Y; i6 p' k

    4 C7 N4 l6 k. L4 n# C* A& u/ L  H4 C  q# E  t6 T* B( X
    def fibonacci(n):
    # U, L/ d- B- i; I+ L0 R2 M    # Base cases* o) r. w& r" V& q9 e' V" ?- b
        if n == 0:
    : H) m2 l2 O' [; ~( \        return 04 i, i0 T4 z9 I0 `* @7 c. [& E4 m
        elif n == 1:
    5 A2 e) ]0 p3 S        return 18 F9 @1 c8 e' U  T8 E' ?' b* a
        # Recursive case
    / q. I. W  _9 i    else:
    5 b! s5 Q: `3 U6 o  [1 m- p        return fibonacci(n - 1) + fibonacci(n - 2)
    8 \7 y6 x$ |6 x. h5 X7 ~! g" O9 }' o/ E6 L6 G( p; @
    # Example usage0 W9 t  o2 X! x( w9 d9 C; z2 a
    print(fibonacci(6))  # Output: 8
    4 L1 d' b" r, K4 ?8 P6 i  o/ B7 a) O& C* ^5 g
    Tail Recursion0 z$ e- \! Y3 H* v* x

    + M1 i  ]% ]. y5 z9 Y/ kTail 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).% G) @/ v( x; C; v# l& u% T

    6 @, G1 A1 R- v0 a5 i7 V$ X/ _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-1-17 08:57 , Processed in 0.039155 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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