设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 - v% c" \  ~4 r6 ^

    " s# {  A5 u- Q3 V7 N0 b解释的不错
    : p' K# n# ?  g- o+ J
    : z( ?! W& T) E9 X; S3 W4 X递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。( X$ b* U( i. V7 H" L- g( B
    : y/ S0 ~1 M- v3 g# @
    关键要素
    " \4 L6 r7 J# q# D' e8 ]1. **基线条件(Base Case)**
    / _4 T# @# t/ C* h& ?* H   - 递归终止的条件,防止无限循环
    " I7 D9 m) n; Q9 e$ S' b   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1' t5 }8 _1 x" ?: m1 o2 U0 @

    6 V8 h  z" o, H3 `+ ]8 X2. **递归条件(Recursive Case)**; a6 m( t$ Y3 T* H+ S+ r+ e% W' _
       - 将原问题分解为更小的子问题
    7 c, L% r" x- A1 p* W   - 例如:n! = n × (n-1)!
    9 H# W, A' J4 s0 K5 j7 L, T
    2 G% q) h* ?& p6 L( C3 E 经典示例:计算阶乘
    0 H8 j: c' s2 e+ Y: f* tpython
    2 d5 r: c4 L3 E7 kdef factorial(n):
    # o9 g; L, C- S( {. ^# X# \    if n == 0:        # 基线条件
    2 c9 j* y3 E2 P$ \2 @% S+ A: \$ D        return 1
    7 Z  e9 c" p) \    else:             # 递归条件
    $ A; R& Y. O0 J6 p& f# d9 ]2 X        return n * factorial(n-1)
    ; o. h+ ]  G, S- ~执行过程(以计算 3! 为例):
    6 r/ G+ W0 i$ e) X$ O0 ^0 ~) ]4 Vfactorial(3)4 z5 G5 e3 T5 x9 [5 B
    3 * factorial(2)
    2 w( z$ v1 V, x9 j# Y3 * (2 * factorial(1))6 x" l6 y2 |: @  S: a. d
    3 * (2 * (1 * factorial(0))): C$ X2 |$ G1 U( O) c8 P& m2 @
    3 * (2 * (1 * 1)) = 6" ?# n; Q% |9 b. E# N& ^! y4 m$ P
    1 F4 P/ u% r2 b4 i* p
    递归思维要点
    " C- B% r& m1 K. ^$ c5 G* h0 }9 Y1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ' X; v  K5 P& O5 T! r2 [4 ]2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 D6 z/ q. x) Y" }4 l/ Y; ~( J
    3. **递推过程**:不断向下分解问题(递)$ R# c$ Q8 g6 G7 n* X- u: n
    4. **回溯过程**:组合子问题结果返回(归)
    ; Y/ O& S5 k* j! a' V6 i
    2 G9 \& W/ N+ `0 i. G 注意事项
    1 `) \, R8 ~. o3 d% e3 x必须要有终止条件3 w' @7 T8 t% ?1 \7 k
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 B( h$ e8 e1 D8 g9 h$ T
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    # j, d' A$ x. }: g+ P8 J尾递归优化可以提升效率(但Python不支持)/ `/ u  T8 r( P

    $ ?6 T6 z% z+ U: `8 h 递归 vs 迭代! d/ i  O. F& s
    |          | 递归                          | 迭代               |' r3 F. ~- o. S5 `4 A  q2 b+ N& M
    |----------|-----------------------------|------------------|) S# @9 p- e# B' ]* |5 I2 q
    | 实现方式    | 函数自调用                        | 循环结构            |# \7 U: O3 U2 V  z
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |/ r% b$ q2 r: f
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |. ]9 I, O  R# i1 a; q" X
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    0 }, v# u, m6 n* C7 L- ]
    ( m% i. R0 e2 N6 X, g/ `5 z 经典递归应用场景) z1 C: e& Y/ w- c
    1. 文件系统遍历(目录树结构)
    5 ?* H1 g0 n, h0 W' g3 ?% A2. 快速排序/归并排序算法" _" {2 J* X# c" l" r" U9 a
    3. 汉诺塔问题
    / b% J, e! L% K# E* s4. 二叉树遍历(前序/中序/后序)
    ; C3 F4 O3 ]6 ?/ W5. 生成所有可能的组合(回溯算法); X2 y) n3 p4 p" H$ G/ h
    1 @, G: h% V8 ]
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 06:39
  • 签到天数: 3105 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    / |) N/ U/ c+ a, q我推理机的核心算法应该是二叉树遍历的变种。
    ) r; `' D, p& q# V6 n3 @' A- d8 C另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:9 S; v" h; B3 o. ^& n9 Z) W: O
    Key Idea of Recursion
    0 G1 T2 O2 G) @3 ?* _
    / ^+ A: Q+ d1 ?- k0 VA recursive function solves a problem by:
    " x' A2 V* ]0 d) h9 Q3 I2 A& [) ~9 S; H, u% {8 B; Q
        Breaking the problem into smaller instances of the same problem.
    / Y9 x: j4 F- U0 O) c
    ( O, Q2 g; Q' P! i. O* q: d+ a    Solving the smallest instance directly (base case).( h+ \8 l4 z4 h" k# w; g

    + ?1 L9 p3 F$ W- ~    Combining the results of smaller instances to solve the larger problem./ h# j4 X) [% u
    ( g4 S* ]' b8 s7 t6 ^0 I
    Components of a Recursive Function; [  }  |$ d! ?  ?

    ) _- I# ?; Z$ A+ f- ?# ^$ j    Base Case:! h6 C/ s. d8 t6 |: t  I% t
    ; Q: S3 t) U" X) n2 m& B
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.- f$ H' _8 N" `3 t& g: u' F

    ! J- i/ Q9 H  b4 L& u        It acts as the stopping condition to prevent infinite recursion.
    7 ~) c, ^. G* g/ y0 @; D2 h" T+ W8 L6 C+ N# |
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    9 d! h8 l: H+ |" o) n# \6 C' X7 K5 S
    6 D; I4 S$ P/ y5 B    Recursive Case:
    9 O* J# a3 [" i: G1 Q
    2 S0 t2 r8 _! ^- _" `/ F        This is where the function calls itself with a smaller or simpler version of the problem.
    & Q) Y$ h: [5 l+ h  X; F
    , V) B: \" A9 w, E; V1 F/ V        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    9 I- d3 q7 J8 C" m
    6 b1 ^/ A, {. p0 i) H8 {3 G% IExample: Factorial Calculation
    8 _6 r; j; X* i7 [2 x# R: E1 q0 p( @, j6 ?4 |% D% `" u
    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:
    & `1 B' X6 o" l  B% y5 x0 S0 X
    0 Y+ e  Y# v8 g- c    Base case: 0! = 1
    * {9 W. U. B$ D  ~1 O7 k
    # X8 w3 y4 d5 ~( I  X8 c: Z    Recursive case: n! = n * (n-1)!$ E- _) M- Q! Y% H6 d( e: u

    # h& J8 x7 ~: DHere’s how it looks in code (Python):
    7 ~& D" d* v" k- upython  ?6 p  w. J! b

    * }3 h; R; W5 g% A  E# A4 Z) v
    . m3 t6 B: u8 a* A9 I4 [def factorial(n):, I* T2 k6 e" D6 f: A
        # Base case
    . ?- H- M1 u4 y/ k- B" A' a4 L3 z    if n == 0:/ |. e! ?7 P6 Z% G
            return 1
    1 Z7 @4 u$ n. T) U2 Q9 a/ N    # Recursive case( ]4 `- j, o* h( F5 X1 |
        else:
    & ^; ]8 U  ?: E7 S        return n * factorial(n - 1)
    ' e9 ^  x) n' c( R2 H; `6 W0 U% C6 |# q5 ~3 c9 a% N% f
    # Example usage
    2 g! u3 ~3 K1 @2 `3 k" uprint(factorial(5))  # Output: 1202 x5 E2 U8 y% W9 }

    & i/ E+ n5 [+ }- f( aHow Recursion Works; A4 i2 b% O4 h% H$ F

    " t% w8 S9 C+ k4 x" l    The function keeps calling itself with smaller inputs until it reaches the base case.
    . i/ x( F4 f7 W3 W, Y
    . ?* S. e! c2 ^2 K7 ~; T& n9 b    Once the base case is reached, the function starts returning values back up the call stack.
    9 H! C2 K  `6 v& {/ W6 R3 A8 d! k( W+ a; G& b
        These returned values are combined to produce the final result.
    : d/ ^+ a. ^. T. d# G4 c) E- K* K. R6 P
    For factorial(5):
    0 `+ S/ B) e3 S8 _2 m) \# {4 G: H/ K$ T
    $ k( V% B0 [. P6 C* F( s! P
    factorial(5) = 5 * factorial(4)% {: Z2 z" i0 k! T
    factorial(4) = 4 * factorial(3). M' O! L1 d; `7 R* [: W. v% D
    factorial(3) = 3 * factorial(2)" G- W$ y* Z( Q; g* g
    factorial(2) = 2 * factorial(1)' y4 {+ W5 R3 R; b; c; k) w
    factorial(1) = 1 * factorial(0)
    2 O+ J8 O" M+ v8 A$ e$ {factorial(0) = 1  # Base case& a  f7 t# R3 M! a7 N# T, D' ]
    9 N! I2 Z8 o2 p* Y7 E; A! [' ?. U
    Then, the results are combined:
    2 A2 n, t. P% E1 y) J5 S
    , `& k4 ~, I5 Z9 t: y) L8 z4 q; V/ [; a* U2 ^# o0 A3 m
    factorial(1) = 1 * 1 = 1  f5 E) S# O% v% V) I+ P; x
    factorial(2) = 2 * 1 = 28 o0 X; {- C8 A) L2 n' H
    factorial(3) = 3 * 2 = 6
    9 o# L6 f/ b: o/ vfactorial(4) = 4 * 6 = 24
    , r5 U" ?5 W" m7 [7 R" Ofactorial(5) = 5 * 24 = 120$ C5 D2 n: N5 h7 t; {8 y

    & C4 d8 X7 \# B2 w0 g5 G9 _; [- AAdvantages of Recursion# f3 q/ y' [# i5 R% u# o$ q# e$ \) Y: h

    0 m* g6 d& o3 O+ P, O3 C7 T) 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).
    & k/ u" E; I+ y$ X7 c9 }& b7 P/ [4 R2 I: @1 V/ h  e2 q8 i
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    " @7 w0 w. x- A/ x4 F: {4 U) f$ o; r( f( h2 U
    Disadvantages of Recursion
    0 `0 R# G: {! [9 ]% C( \. v" N9 i! K* E; 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.
    * F, x* o6 R: B0 n' ^& T8 y, H! [; F8 [; u& _0 P' T% A
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).5 K9 a! s. C# D- V, w% X
    7 m8 H6 x4 I8 k6 u! _' {' w
    When to Use Recursion
    ! M& ~% u, T! N1 I6 k, W. c
    " ~( L' ^+ u/ y2 Z    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).1 R: w1 M% k1 p: \

    # F2 T5 h' @- Z+ v2 t    Problems with a clear base case and recursive case.
    . V) `2 [5 v) y/ W! F+ c3 s/ C' y# `- |
    Example: Fibonacci Sequence3 p9 L8 x/ C" c! A, ~

    , A* q/ J: _$ G' N9 CThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:- |$ X! A) a" B; v- z
    4 R' q& l3 ?# K9 @' |/ l
        Base case: fib(0) = 0, fib(1) = 1
    9 f/ C$ J, T- H) H" E. m- y0 ~
    - A+ }+ P7 a3 i$ R9 ]- k- X    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    . g0 k% l1 ]; i0 P- f6 m. m( ]
    1 P0 ?, R7 u1 D* W0 c9 ?python
    & V- g# y# T$ ~6 ?& M( X* F' G  D7 \  z- P5 X2 R
    1 J+ [% n: a5 [* t! m0 Q9 O, C
    def fibonacci(n):
    . f  d( Q& t! f  T/ F. h+ ]6 U    # Base cases
    1 F  D" E+ F& ?: s8 Q$ @$ Q    if n == 0:
    3 n+ _6 p, \, h" d* p        return 03 q5 e$ Y# ]9 k8 Q0 b
        elif n == 1:3 S: f$ z5 X. Y5 z/ Z9 d1 }
            return 1
    4 {* _: ?$ S4 T! P+ R' V    # Recursive case
    + g: w. B% ^+ X) T( h. K( X2 e: v    else:
    & S% Q9 P/ l; B7 I: L        return fibonacci(n - 1) + fibonacci(n - 2)" K  e: |- q0 U/ J9 R

    , e7 f/ ~0 R3 M% e  H/ C7 R: j# Example usage8 X2 M4 `* a+ {3 n2 K. e: d+ B
    print(fibonacci(6))  # Output: 8: `' n; B8 C* {  D' m3 l

    , \: m* b; R- `' y2 xTail Recursion( g0 ~3 ?" r. A7 p0 @
    $ ?2 s4 X0 m. Z. |4 S# C2 V3 X1 |  q
    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 j6 m6 c4 ]! E
    $ a8 X9 |0 D7 ]' e- d! l
    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-1 23:51 , Processed in 0.032270 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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