设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 , m5 j3 Z, E% D3 z, E4 e3 O5 Q
    5 ?& w& W: H! ], O9 S+ l
    解释的不错
    1 E! L2 e& p# g0 Y+ P  X+ y- J3 ^
    6 e! k* S2 A8 R$ u: ?递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。5 Z: ?. K3 {/ e5 a

    1 d  a2 R0 T0 f1 K2 C 关键要素% v4 K$ ~0 _3 W2 x# p. r
    1. **基线条件(Base Case)**
    8 T1 `/ ~( N: d* E6 |' `& G   - 递归终止的条件,防止无限循环
    " Q# }* @6 a  w* ]& n& F   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1/ k0 d4 K- w) F" I+ z1 [

    - Y4 Z: [0 l- g2. **递归条件(Recursive Case)**
    3 ?! d: C0 V: ]$ C: Q# E& q3 v   - 将原问题分解为更小的子问题( g: Z4 `7 k" C
       - 例如:n! = n × (n-1)!
    % o& w, I3 C  o  o
    & \6 x' u' G3 @1 |9 w3 b& J1 y- h 经典示例:计算阶乘: V1 }/ Z  L: b. r- e4 l! m# j
    python6 s( i; z1 g; r- [
    def factorial(n):0 R5 S9 G  c. G+ ]5 z3 p2 B9 U( ~
        if n == 0:        # 基线条件( S) o$ z8 U3 F5 o
            return 1
    5 k" F- `# [9 U    else:             # 递归条件/ E7 d' N2 f/ ?3 B* S/ }( Z
            return n * factorial(n-1)
    1 o3 o* R% H. N1 j/ j9 }7 o执行过程(以计算 3! 为例):' v! r3 f6 `+ A2 G
    factorial(3)0 i+ x/ @, O9 A0 s5 x% X9 s. e7 F0 f
    3 * factorial(2)
    $ m0 T. m: o0 J1 ?0 ]3 * (2 * factorial(1)); ^$ d: }; G# @) o3 ~; R
    3 * (2 * (1 * factorial(0)))
    % s  P1 S# r' O: I4 x! u1 m+ h" V  r3 * (2 * (1 * 1)) = 6
      m$ ]& L7 d; O
    5 y' H; _# }% E; u7 D& F 递归思维要点4 z. b& i7 y: d5 D4 W0 i) j
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    $ v. }. f+ ^$ f6 q% p6 J2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 {6 S# c6 V+ ^  {: }" d
    3. **递推过程**:不断向下分解问题(递)3 s' X" g' s/ E- S
    4. **回溯过程**:组合子问题结果返回(归)# Q1 G) R4 {) u0 v6 u! f8 b

    7 N" ?8 p' Q5 |6 }0 k8 M! W4 U$ f 注意事项
    $ ]7 j4 t9 w6 i! W, z  K9 K必须要有终止条件
    : Q6 n1 j# Z* o# k$ `. W递归深度过大可能导致栈溢出(Python默认递归深度约1000层)( S8 k: Y+ k7 [8 T: F. \* H1 V
    某些问题用递归更直观(如树遍历),但效率可能不如迭代% a9 V: ^. w- j
    尾递归优化可以提升效率(但Python不支持)
    " F; t8 _; N4 `0 [6 m9 {5 e" ^$ g9 X% J, @6 n# k" l6 l8 Q& y0 c
    递归 vs 迭代
    , c- a9 g# \8 q|          | 递归                          | 迭代               |* y; A! T$ b' I* |$ _& x* B5 l# t
    |----------|-----------------------------|------------------|4 ~; a# a3 Q3 s1 O  o' {
    | 实现方式    | 函数自调用                        | 循环结构            |: i8 n% V* ~1 @: |
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    7 b( B( S( i6 D: g3 _; N| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |$ f% o5 h9 b' \: _
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    7 t) Q7 R7 d1 x5 L8 `4 {
    * [+ @/ K* T: t5 ?0 l 经典递归应用场景
    7 f( C, {2 `4 ?) C6 u1. 文件系统遍历(目录树结构)+ h! b% F5 g9 [2 `; @
    2. 快速排序/归并排序算法. ^9 \# `5 p( S! K; u
    3. 汉诺塔问题
    " [5 o  U& n8 Y4. 二叉树遍历(前序/中序/后序)
    8 g' I5 p; H$ h. i5. 生成所有可能的组合(回溯算法)& u) l/ E+ e4 ?

    " H: i, }5 P. U5 j. ~试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    10 小时前
  • 签到天数: 3180 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,# ?& }8 W. r1 x7 D; }! L
    我推理机的核心算法应该是二叉树遍历的变种。- i! p( T& P# `  N  P
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    ) W9 z7 O) e3 x0 k& ^! {Key Idea of Recursion; [5 N. Q8 p1 L: M3 L  U/ u: H/ K

    3 d, B  |5 M1 U* A3 l( J4 a6 OA recursive function solves a problem by:
    0 z% H8 V& g+ s2 i+ x- j& ~" j, N3 E
    # V0 m- d: X( K) s$ O! C* s1 l    Breaking the problem into smaller instances of the same problem.
    $ ?0 j$ c+ h8 _9 q" Z" P3 \: v# E- P3 u. D% M7 I
        Solving the smallest instance directly (base case).. a9 o: l. F' @7 R' m& U4 A: o
    * m8 ]/ l+ v6 X7 j$ N" G( w7 d
        Combining the results of smaller instances to solve the larger problem., n5 k" f/ ^  h- z3 J# G

    ' v' _2 |% `: g  T0 oComponents of a Recursive Function
    ! {1 G1 B5 @9 }, v+ g6 I3 N& }7 t) [' d$ J+ n( r
        Base Case:  ^2 q/ n$ _' H  T0 `, x4 Q

    * C" w4 N% r, S, Y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    9 A" j6 G5 B3 [; T/ q4 _9 Z) q. d7 a4 }7 G
            It acts as the stopping condition to prevent infinite recursion.
    % t, j* y3 t8 q+ C( N$ P4 d+ i; i3 N2 f( @/ z) L0 U' Q1 g3 P
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1./ Y" u6 [( f: s, x* f* C

    $ K; A! x+ ^9 B    Recursive Case:7 ^2 {( ?/ k, J+ n3 z) x8 E
    0 k' o9 a# @4 _4 o* e
            This is where the function calls itself with a smaller or simpler version of the problem.
    9 u( k1 i# F3 `0 v; L, E$ x, a+ z; W& [2 |+ \* d, }
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ' b$ |$ a' ]( j1 z
    ) a" V& `3 N0 M4 E+ iExample: Factorial Calculation
    8 C# ~' k1 G2 r
    7 N. w  B8 f, jThe 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:1 ^) W# y% \- O& R. ?3 p
    0 `$ d) Y: V2 f6 ]8 S
        Base case: 0! = 1
    & f3 y/ k6 F3 X1 s8 z( q, U
    ; M5 o7 `- \+ l7 w: K% m8 {    Recursive case: n! = n * (n-1)!
    3 }: K2 I6 n9 C5 v6 E5 D
    7 B7 ~' t4 L- g$ a" \" s# L, iHere’s how it looks in code (Python):
    - K6 }3 I; y8 Spython
    ) Y+ o: a2 k# g" E- I! F/ V, s( y
    " o0 `; v1 A9 t1 ^4 I0 c1 F6 U
    4 }$ J; n9 k! r/ J6 I6 ]/ C( bdef factorial(n):# M& y9 |9 S8 C; z' A0 V% J* c
        # Base case
    ; P( t) Q# s3 F# I    if n == 0:
    ' ^7 @/ p, l, j* n        return 1
    / }- F+ }. d5 w    # Recursive case
    ' z  d: V: _' I$ z% ^    else:
    " ?9 K8 ^9 v8 g        return n * factorial(n - 1)
    8 B% z- e1 T1 t2 T5 E  u0 S8 s* V; P0 x
    # Example usage
    9 z* g2 L. h; V/ Fprint(factorial(5))  # Output: 120
    5 r* q- w, _2 S4 ^0 v( W/ `" j7 y6 Z4 @6 C/ [! a# \9 x
    How Recursion Works
    ( T" E6 e5 F! z: h3 N
    9 \# u9 c% d* J5 b    The function keeps calling itself with smaller inputs until it reaches the base case.
    " ]# [" Y1 c: p. }2 \$ J8 |+ y
    ( I5 h  w) V& E( A$ g9 z- }" W    Once the base case is reached, the function starts returning values back up the call stack.7 `: u( f6 g* ?2 \
    ; U. Z; x! i6 j% c
        These returned values are combined to produce the final result.
    ! Q+ B8 A( J0 h
    + y) h) t' L) }* }9 i- IFor factorial(5):
    ) {: j' c1 }+ A& y* u2 t  r9 p* O3 P! K/ I

    ; P( _# h' I7 v# Lfactorial(5) = 5 * factorial(4)
    ' X  |/ N' x$ jfactorial(4) = 4 * factorial(3)
    # k% z! N' I* {3 G* yfactorial(3) = 3 * factorial(2)1 J, B) {2 w2 K3 L5 q& i
    factorial(2) = 2 * factorial(1)1 s9 q9 y0 F' \: I+ w( a
    factorial(1) = 1 * factorial(0)/ Y0 ]: Z: i- _" m7 c
    factorial(0) = 1  # Base case
    : }: O. t, i% S/ ]: @
    # @' T( s2 B: w5 [Then, the results are combined:
    9 L& I: ]; ^  k: O$ U( w3 Z4 Z. z: c6 x  }7 [8 ]. l
    , K9 }) {* L1 I1 R1 o, r
    factorial(1) = 1 * 1 = 1
    ; E- J; M' G! l/ L0 M9 s0 |4 Nfactorial(2) = 2 * 1 = 21 ?% m7 w! y1 W+ ^
    factorial(3) = 3 * 2 = 6* W2 l7 u6 p* a! n
    factorial(4) = 4 * 6 = 240 n& X; f! Q# Z) P5 Q7 T
    factorial(5) = 5 * 24 = 120: S: K( t# [5 |0 n+ j
    7 i& @$ ~; R  _  l  j2 q) o! @7 o) R
    Advantages of Recursion
    4 U: T. _8 B" J$ T0 U1 I) e% E
    8 g8 Y( Y1 u/ W2 r2 t; G7 V$ X    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).6 L( g  X# x7 `2 D) |7 c

    . i: i+ U7 i7 R/ \8 q    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    & l; Y, `9 y! K2 B
    - b$ f' I) C9 q2 `! ^* FDisadvantages of Recursion$ F' V4 _/ N4 W, ?
    7 }4 \. y! t! i* L2 d7 `
        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.( z' x+ K: b, g
    5 O" Y1 c6 ^" O# x5 q% j  G0 t
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).( z' r' K) e" z! _3 O8 x; i
    + a- |. m8 m" f+ B
    When to Use Recursion
    9 b4 [) N9 R- R% x  l7 p$ `* n& F# m
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ! Y( q) b3 {5 d5 A0 \+ f+ G) |' l. Q  a4 G6 T" e, E. o
        Problems with a clear base case and recursive case.9 y% q6 j- N3 @+ k4 D, j+ s
    + O1 U( x+ s5 o- q
    Example: Fibonacci Sequence
    % K5 u& c- O+ [2 @( Y( I
    - r- S7 b2 J2 VThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    6 T; q. x3 v5 V
    ; r5 X7 W" f7 c; `, q* P* W; @    Base case: fib(0) = 0, fib(1) = 1
    7 s, }$ a: B$ l. _
    ; A" Q4 @, r- h7 b    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ) ~2 W  E/ R) K, V& y7 N: y0 w7 ^7 L$ X8 E5 Q! K* @
    python: b" Q4 p* q! ^  X( T/ j8 L* @' Q
    + N5 q9 ]/ V+ W; Q; D4 ^; m

    & j7 ?0 h7 m; [- ?+ u/ C) O5 d7 P5 Adef fibonacci(n):% l) b% q2 r, V3 o/ Z& `+ @" O
        # Base cases
    ; d6 H0 J+ W3 u) W1 U    if n == 0:, w3 C: v1 U0 U- l, l
            return 0
    ) `  }) F1 {5 B& q0 K    elif n == 1:& }0 |) a2 U5 n5 k
            return 12 f# m6 ^% ~  _
        # Recursive case( d" P6 V+ R6 A, g3 @5 B
        else:
    ; E1 a1 w$ k& H9 k  ?5 f        return fibonacci(n - 1) + fibonacci(n - 2)
    3 ~" x2 i% b7 w: v# J/ f+ u$ Y/ |9 F9 r( O0 \
    # Example usage
    # t- V- u5 \+ q  `& Wprint(fibonacci(6))  # Output: 8! k& e+ W# N- S- G, w4 i- G

    * D3 V' C. ~1 X, c0 jTail Recursion0 {% A, o7 `3 I
    2 ]" _+ _. o6 v
    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).
    * F5 ^6 W3 N$ _  z6 h  \
    0 C9 C- T( N% E1 L& v! k2 oIn 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-2-21 16:16 , Processed in 0.057048 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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