设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    9 i1 R! m# Y3 o2 d3 u; d; k
    1 G5 l; D) q5 }" B7 D  b+ C解释的不错, [. X+ ?8 t! {( s
    : T! T6 Q" t6 Z) m
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    , N+ t, U9 T- }2 I% @. }6 i9 a3 M
    关键要素
    4 p8 z8 K& Y3 M0 X1. **基线条件(Base Case)**  k6 o: B+ Z! A. Z# g% i; l
       - 递归终止的条件,防止无限循环
    % T! X6 x$ U3 q0 `   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    2 \$ j9 O8 B- _- C# p" |8 _1 q  C
    ) s2 W3 e6 ~5 u' s! _- M2. **递归条件(Recursive Case)**
    ) M9 g8 M! x/ c. e8 q2 s7 T5 n$ N   - 将原问题分解为更小的子问题
    ' b( l; Z% \, F3 H" s: Y! k  K( ~0 e) E   - 例如:n! = n × (n-1)!7 [2 p, t* l$ B0 O0 v& ]; d) w
    & a# P4 N) |1 e$ {  t
    经典示例:计算阶乘! x& |! r. |7 q8 [; v
    python7 y1 M' X& J& {9 o- ]9 x' c1 G
    def factorial(n):4 w/ m  J. _3 z; w
        if n == 0:        # 基线条件3 S  S" y0 d1 I9 P2 I
            return 11 j4 }0 J) d  g( F
        else:             # 递归条件
    1 q, h+ d3 \0 @7 P9 x7 I% [! p        return n * factorial(n-1)
    : w' X2 ?$ K$ q执行过程(以计算 3! 为例):7 w% r/ T/ h- D, y
    factorial(3)# }# j7 C6 F% q: l
    3 * factorial(2)
    7 k, D+ o2 {+ q4 h9 }# C  {% w* e3 * (2 * factorial(1))8 v' D# ^, `: k4 H6 L) i; G
    3 * (2 * (1 * factorial(0)))& B1 ^- ~, I1 T
    3 * (2 * (1 * 1)) = 6
    + ?3 k  W6 ?( i$ C! }$ X  q, T" E: R0 u- s9 O
    递归思维要点
    5 O! s" q& @* f0 F6 G& V* q, N1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    6 p% y4 U; ?$ i2 K+ S, m2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    9 ?# g5 w& y5 r5 }9 f: Y5 G! u# S* |3. **递推过程**:不断向下分解问题(递)
    & Y8 {" D7 I) l* ~* R; O1 i" u4. **回溯过程**:组合子问题结果返回(归)
    - i0 w) e  M6 W0 T6 q) k1 s, L+ ?/ z  u0 x# o( r! K) l3 a
    注意事项
    $ R! e0 e  G* }7 u  s必须要有终止条件
    ) V+ u0 t2 C& U递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " k5 m: r; C6 w5 t1 r5 `某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / [3 e, k0 ]7 Q3 `# Z1 j尾递归优化可以提升效率(但Python不支持)- j$ S# J2 {9 ?! J. h# E3 ^. O2 l
    ( h# c; u! r9 y
    递归 vs 迭代' ~% [+ S! [9 {/ Y/ o' Y
    |          | 递归                          | 迭代               |  r3 h. \: \; x  B
    |----------|-----------------------------|------------------|' A( r) S1 G7 j
    | 实现方式    | 函数自调用                        | 循环结构            |
    ; r9 z* q" o3 F| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    5 W$ b" O6 H/ ?# V/ c0 p| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    % S! p2 s% K+ I# ~| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |5 S% B, ]' c# g2 H( K3 ]
    & b2 r' n$ v2 V- x
    经典递归应用场景
    * ~- D4 K5 j+ L, t( Y1. 文件系统遍历(目录树结构)% [& l% [. c( }& N
    2. 快速排序/归并排序算法
    , T$ N5 y4 j, p0 Y7 @2 ?: {3. 汉诺塔问题
    3 U% a8 X& y" h4. 二叉树遍历(前序/中序/后序)
    7 ?$ _6 z; ?, E5 S  ]5. 生成所有可能的组合(回溯算法)' n: F3 ^. ?/ K1 l- Z, ?
    $ ?" p5 H9 g( p4 _6 f, {8 Q7 n
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    7 分钟前
  • 签到天数: 3014 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    - |8 ]5 Z' H6 }  c& Q我推理机的核心算法应该是二叉树遍历的变种。
    " O; V: D+ S& h* L另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:8 ]$ F5 \- Z1 f8 F% c
    Key Idea of Recursion/ ?( v2 W" H+ l

    ! Y2 b& L+ y/ i1 ?, oA recursive function solves a problem by:" n. T0 H# Y. O3 p

    - I9 b* ?, F2 [- A+ P; T# @6 Y    Breaking the problem into smaller instances of the same problem.+ y' v- F1 e$ g; \
    ; X' X' C3 X, a/ o" f- _  l
        Solving the smallest instance directly (base case).+ `* w3 M% o5 h% \
    7 }( x( F% t% Q
        Combining the results of smaller instances to solve the larger problem.1 L) m* X  M4 {: V

    3 p. Z- V& o7 t2 `Components of a Recursive Function
    * o: z5 V( K# X, s4 `+ D. o1 w7 K5 M
    1 `; S) z$ {$ x' {$ H    Base Case:
    2 [, ]0 W0 B: f* S, L! C, Y2 e, X4 S" W
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.6 H, k0 r) }$ E0 P' {
    % k, \5 ~4 D, ~- h5 E
            It acts as the stopping condition to prevent infinite recursion.
    4 `' v: y- W& S& T( U4 g" [4 K% [' [
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.9 f1 T* N6 @) ^3 R1 G& {$ A

    + w3 _0 {0 N7 q8 M5 i$ a% u    Recursive Case:! J" V4 B; a8 D# Q5 [+ ~

    # F( q; x! ^9 ~        This is where the function calls itself with a smaller or simpler version of the problem.
    & n% e4 m" S( Q' ^( e$ {* G3 {
    7 J: t6 {8 I8 l: f) ^        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    % o5 L! c2 c& Z% V0 J! N3 m& n: k5 V8 }
    Example: Factorial Calculation3 k$ c# _0 j& |4 v+ [

    # N" g3 H2 L) }% f4 ~% XThe 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:
    0 ?, K% D' {. C  `" Y! ?. p2 d2 H
    0 i4 s: S% h/ }& P: u    Base case: 0! = 1
    ; S; L& Z# R5 o" B. O! H0 v4 R
    8 c6 X! i" {! [1 @1 `0 E    Recursive case: n! = n * (n-1)!2 q4 s  q0 j" L
    2 H: |4 ]8 |8 W$ ^
    Here’s how it looks in code (Python):8 t5 B& D% E: Y6 G6 s9 \# y- G' X# [% b
    python4 ~. Q+ [+ \( z0 f8 D! N+ ~

    + g5 e* H2 f: t0 U+ b% P, k; d1 q- f; t
    def factorial(n):5 \! s  e3 A/ \. N
        # Base case
    * G! @3 {: G/ t$ ?    if n == 0:! G( i1 [) U0 H% o$ g7 R2 }9 J3 }5 S
            return 10 N/ Y" t5 }( y% L$ z
        # Recursive case
    8 z2 U# c* f- B    else:
    0 W. f$ i0 ?: j7 B/ \        return n * factorial(n - 1)' z7 f; v& V8 Y( _3 Q8 ~
    1 u* b3 Y% l# l# @/ o
    # Example usage/ f5 ]. Y: w: @. a" u0 X+ Q
    print(factorial(5))  # Output: 120. ~, p, I$ z4 a/ w9 E
    * W" c, C  x) o. }- H
    How Recursion Works' W. K9 V5 n: g( ~0 z, {' Y, U- d7 ?

    2 T5 J  D7 ^# }: }; Z4 p    The function keeps calling itself with smaller inputs until it reaches the base case.
    3 R4 ]2 E5 n1 s$ Q1 D% V
    7 I; I8 ~4 q. o# H( M9 A    Once the base case is reached, the function starts returning values back up the call stack.7 r" q: x; K5 y6 V+ Z

    & O8 z9 n# R8 o    These returned values are combined to produce the final result.  p; t0 @' I" M( E6 R( N& g* W- q
    : J! L8 v: t7 W7 ~1 V/ L: f! x
    For factorial(5):
    5 ^$ |: [, G0 u: q3 `2 R' B: Q2 _+ I' L: i. L
    ! c: X: ]. S1 e8 i# Y6 `6 e$ V" _
    factorial(5) = 5 * factorial(4)' X$ J3 w2 g6 O" V) i
    factorial(4) = 4 * factorial(3)" v  b: K/ z% B/ l* C
    factorial(3) = 3 * factorial(2)  |3 w# F+ R/ R- T
    factorial(2) = 2 * factorial(1)
    " T) T7 j* W1 ]+ bfactorial(1) = 1 * factorial(0)0 L# u6 _, @% ^4 T6 Q
    factorial(0) = 1  # Base case
    ' o1 E9 j. ^: S  M3 V& h* y$ W
    1 _# Y4 B( x) J# h' b% b/ ZThen, the results are combined:0 z% l, T7 L- b# x9 r+ ^+ }" [

    1 N0 b/ V% T! }
    + e4 k0 y' F3 n) w! Y  l: T" Ffactorial(1) = 1 * 1 = 1
    6 Q4 o- v' V4 `& D2 j: hfactorial(2) = 2 * 1 = 2
    ; q  X) w% s, u8 R% Wfactorial(3) = 3 * 2 = 67 ^6 T0 c5 `% X/ s" h- k2 ~
    factorial(4) = 4 * 6 = 24
    " @8 A" ?% A, D3 Yfactorial(5) = 5 * 24 = 1209 ]8 k5 o4 ~+ D! f

    ! k* b* d! X" e6 K; s, F/ |/ h6 oAdvantages of Recursion- r- q' W2 p3 v$ {6 Q0 q& D
    9 Q  q. U! I! M: X& A
        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).! _' X' g- n/ s4 v

    $ _4 n. N* D6 j' t2 x- E    Readability: Recursive code can be more readable and concise compared to iterative solutions.3 Y8 x0 f: H* Y" \9 v

    * T% \8 e6 }5 l2 m: n6 DDisadvantages of Recursion" s( t) n. R: I% u% T: U; C
    & P4 ^( Q4 g; B4 ~
        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.4 w. P# `7 [+ n( v' j
    0 o9 S* a4 x  n0 \7 [
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    6 d" s% o6 J2 B) M( B% g  M" b5 }, a+ Z/ b" R" D3 b1 y
    When to Use Recursion
    , @) z. X0 z8 {9 a$ j+ ^
    * F, Q+ v- Q% E; A% j) X    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).. G6 n$ V* E$ e- Q+ ^5 V0 `

    2 t6 G5 R: O- h8 U    Problems with a clear base case and recursive case.
    : z: B5 }) i( c8 U6 ]" S' L' N- u+ [5 Q
    Example: Fibonacci Sequence
    ) A# M  P8 g/ S$ o7 v0 _. z  C
    + g) I3 \# T! v" r% ?& HThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:3 Z3 S2 d4 o1 E( c/ K# {' W" {
    * c6 [% \5 a6 s4 d0 X7 V
        Base case: fib(0) = 0, fib(1) = 1) v' ^/ ]' U2 i9 o4 ~, k

    8 F* x# ?" N( W# `/ n" u9 d1 m    Recursive case: fib(n) = fib(n-1) + fib(n-2)7 A* Z- E% M$ ~" H9 Y( Y2 {* _, r

    2 S( b1 W" D! C4 y" jpython" e/ k- p! _: ~
    . |! d& b4 {3 [% u# k

    , c# k6 r, c) ^& Z3 `2 p' U8 d# Ndef fibonacci(n):% o- U" q1 j) a. L
        # Base cases! K% G. v' t% z5 D
        if n == 0:3 h; g! f' S/ ~8 s: a1 s. I1 k
            return 0
    6 d5 M3 R3 P; [7 R    elif n == 1:
    2 L8 ?. s( m! h6 {" ~1 s6 @, v        return 12 k0 @- e/ \$ v: N: P; w
        # Recursive case
    6 ~4 m& T) {. d- i7 m    else:# [- z! ?9 _% T  D5 A7 [* k/ f/ K4 E
            return fibonacci(n - 1) + fibonacci(n - 2)
    ) K2 U/ |1 p" i! P4 F- I
    ! g- Q6 O$ x2 J4 s% Y( F3 Z2 Y# Example usage8 T+ w% Q# Q" K: c+ p; J
    print(fibonacci(6))  # Output: 8
    ( H) v2 c0 W4 X2 Z
    . D. U5 W% J( W; OTail Recursion3 _$ z% N$ G7 \) I2 O' O2 n1 }

    3 k$ X& T% T  \( U* I' y4 p5 aTail 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).
    0 S9 {# H) T4 j$ B1 X# E7 O
    & H" I( f5 j$ y+ y' a. }* HIn 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-8-19 06:07 , Processed in 0.033667 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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