设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 Z( H7 \% K8 L8 Z
    ( P+ ]" q+ r& x! ~8 c$ R" z2 I* a) W解释的不错
    ( s- A1 L) e5 z7 x; \" C2 j# S& z) d+ B- S
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    $ I3 D& E( p( \( ]$ U% m+ O# }5 e) I# e5 C
    关键要素. o! Z5 P0 C: ?. ?9 w4 j) A
    1. **基线条件(Base Case)**
    ( f; |, f' ?- ?1 v  |, n   - 递归终止的条件,防止无限循环. f4 L: B- u* [/ Q+ j" r$ P9 u0 X7 X
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - q1 t; _, v$ W0 @
    7 J! R( l, ~3 x* f" J2. **递归条件(Recursive Case)**5 i- }6 z7 L: D0 j
       - 将原问题分解为更小的子问题
    7 q: Y0 j# {+ |* \6 K, @   - 例如:n! = n × (n-1)!
    8 j! p8 L& i. [" d2 a2 s6 s6 S/ V$ Q
    经典示例:计算阶乘3 ^2 \. I. Z0 a& X4 {" d9 H
    python
    9 \. g# n/ Q2 d# u: S9 y: x( Ndef factorial(n):
    2 _! @, V( z  w) Z. N$ \8 K" ^    if n == 0:        # 基线条件$ b# o6 W5 A% `1 X+ J
            return 11 J9 t& f7 m* c7 I1 D
        else:             # 递归条件
    " s* S( E% y( n' @% b+ N( W* v/ f2 w        return n * factorial(n-1)
    ' V/ r5 t0 Q. d0 R3 }6 z( \, R6 g+ u执行过程(以计算 3! 为例):' K* z2 x! b7 }$ |: p7 @# U) l1 ^
    factorial(3)
    4 q6 o3 Q% A: k: p. u. p3 J3 * factorial(2)
    9 S! E! J' B' J! Z  I3 * (2 * factorial(1))2 I& p# M7 _9 |$ s) p
    3 * (2 * (1 * factorial(0)))2 Z% ?8 J5 ^9 B8 B0 j
    3 * (2 * (1 * 1)) = 69 l# ]: _7 s* Z' A% k
    * Y' s0 ]: L0 _6 x8 i, H) J
    递归思维要点
    1 l  c* m' T; X# L1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    5 J& u1 m: ?, z4 J* T% g, T2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    1 j" o( K. S* x+ M- m8 q: S& u3. **递推过程**:不断向下分解问题(递)
    ! `& s/ [6 n" S- r  q/ ?& Y4. **回溯过程**:组合子问题结果返回(归)
    ; x4 b( t0 s6 h  x2 t. ?( K/ u% i6 O  W' [/ ?
    注意事项
    2 e0 |4 ^, f) f1 P8 O5 k2 ]必须要有终止条件8 h# l; \' U/ b. E1 K8 p
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)7 r) V. B2 X  m/ _0 u: `. S/ T2 g
    某些问题用递归更直观(如树遍历),但效率可能不如迭代9 F. B2 O/ I( r% c6 `: d2 Y. q) f
    尾递归优化可以提升效率(但Python不支持)! n: k; A" i/ C+ z
    * K$ d% x, S6 k
    递归 vs 迭代
    % D$ n5 X2 C- u|          | 递归                          | 迭代               |1 L* P- Z( G# c, r
    |----------|-----------------------------|------------------|! n: F( v1 P5 P6 B
    | 实现方式    | 函数自调用                        | 循环结构            |
    $ j' L! C! [* h% ]1 p| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |1 W% t- {  {  }
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |: h5 C3 U2 b7 H0 Q, e2 z$ `9 t# `
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    * E4 L9 {# \2 c0 Y8 k! R+ b3 z0 I
    ! ~0 b. R) c" L5 l/ ~ 经典递归应用场景
    * j8 d3 w: ?, \! y1. 文件系统遍历(目录树结构)
    - h1 R4 T' l) W2. 快速排序/归并排序算法0 X" H% l0 @  _3 ^1 J, ]9 }
    3. 汉诺塔问题# _# P) ?6 a2 C; P* [5 B. U
    4. 二叉树遍历(前序/中序/后序)- h5 k* G0 O1 s3 L) K
    5. 生成所有可能的组合(回溯算法)4 d  _  ?! Z* r* n  W; F0 }; R5 ]
    & x) y9 M8 [' H5 o8 a+ _  r
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    昨天 14:35
  • 签到天数: 3132 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    / B( f9 x7 m% R+ x7 k1 W. w我推理机的核心算法应该是二叉树遍历的变种。
    ; {: ]1 E$ Q( w另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * l7 [% c) W' x; F9 aKey Idea of Recursion
    ! |# Q3 Q. A# E; ^; t/ ?  h. V% d: M
    A recursive function solves a problem by:$ K' x6 s9 D6 J0 o
    6 i; n% L) @, [5 r4 T' q) s
        Breaking the problem into smaller instances of the same problem.
    . ^9 R! F+ v$ r8 f2 o+ E6 k3 i
    : x- R) q/ Q# ?8 N    Solving the smallest instance directly (base case).
      l  x+ J6 u% o- A
    ; I! o, U2 C/ n9 T8 f; M! V  ~: b    Combining the results of smaller instances to solve the larger problem.
    & T( W; f$ Z& ]6 c/ v4 h: p
    " ^* e% ]7 h% i  d) p. {Components of a Recursive Function6 ~+ S7 e8 `" k) V9 X
    8 x' Y1 J/ x  R- p5 W( ]
        Base Case:
    . s' \% ^: R' r& [
    3 T) t6 b; F0 M3 q# p1 \  ^5 h3 m        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.. j' K8 W3 u, V0 r+ I" z+ `% j
    ! a/ p% y. k6 y6 n
            It acts as the stopping condition to prevent infinite recursion.
    ) x/ U( `6 j+ D  \
    * r7 [( `/ \0 P, c  N        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    : b  n& j: Y( e; U" v) t- l6 ?% P2 l9 W/ T! A
        Recursive Case:
    ! c2 x- {& p0 C5 [" G+ J, X4 y! I7 r) w
            This is where the function calls itself with a smaller or simpler version of the problem.# Q/ b' s4 K8 [3 z3 ?0 c

    & ~+ C, b- H9 X+ I8 X% L        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. Y; u# U/ R7 R
    + L. n8 y" S( O9 x+ U  t
    Example: Factorial Calculation
    5 m+ V% S/ k' {" K" |3 o
    5 M+ s1 G+ B! [3 eThe 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:
    8 X, @; z% W5 \+ f0 h: e
    : x8 G! E: R8 b- e7 G5 k% d    Base case: 0! = 1+ D8 R+ i1 Y9 g: V2 a/ e
    2 ^- M' y# G! C
        Recursive case: n! = n * (n-1)!4 o! L- Q( z+ O8 P
    ( g! P+ Z, y! x  R* E  T+ k+ ]3 }
    Here’s how it looks in code (Python):, A; U  Q* _3 }# w" W
    python
    : I# A' F( r9 ^9 T$ b0 r6 A
      w& v: X8 h# {" v' `$ U* Z" n! \6 p8 j
    def factorial(n):
    6 |4 x& m/ L9 q    # Base case
    ( a! a! O" A! Z* r$ ?) B1 O    if n == 0:
    ' S( W$ X( k6 M! d' @        return 1  o, Q: a/ P: O, n  ~5 t3 }7 o
        # Recursive case4 O! `. z# x' a, q6 [( w1 |
        else:* N- h; `* m1 |7 i% O; K
            return n * factorial(n - 1)
    4 \3 S- E! h4 |% t8 G' V+ d+ L1 z/ t: n. Y+ j+ ?
    # Example usage& U0 c4 v+ L9 \' G& h
    print(factorial(5))  # Output: 120  L9 |& n3 E8 R6 S
    : [3 R  D- [! i
    How Recursion Works' _( m9 E! t3 p) R) z4 h1 X# R, L
    6 K2 `+ c  Z$ j
        The function keeps calling itself with smaller inputs until it reaches the base case." ~7 {/ _) M( w" h/ M
    9 e: d2 i' w6 n
        Once the base case is reached, the function starts returning values back up the call stack.
    9 H; g( Y7 v+ u  p' s% p) h& w3 `
        These returned values are combined to produce the final result.
    $ W7 {- m9 F# u7 J+ |. f' ]  H: k; e. u5 k) M
    For factorial(5):
    / }) R& W0 N: {( ?* L; F" W6 U* K- g0 p# d
    0 e: j0 X1 p/ M( C1 ]: c# ?
    factorial(5) = 5 * factorial(4)
    3 n: s% v; e7 z6 u) k# `# Sfactorial(4) = 4 * factorial(3)3 z  x0 f* d* `  a( K
    factorial(3) = 3 * factorial(2)
    2 |" m9 w( Q& i% Jfactorial(2) = 2 * factorial(1)$ I8 Q8 P3 N; S' t- G5 E* f
    factorial(1) = 1 * factorial(0)& E9 C9 b1 E: t2 ]* n. m
    factorial(0) = 1  # Base case
    % u$ {. y% F# F' [  B1 Z* Z5 c# [3 ^
    2 F0 [0 Z4 x* G  [' |% Y. @7 b" \Then, the results are combined:
      G8 ^4 ^! m" {9 a# L% N7 @0 p& H+ b0 k+ ^1 ?7 h

    % {3 D; ]+ L! `0 H, tfactorial(1) = 1 * 1 = 12 p# @; u- t& w
    factorial(2) = 2 * 1 = 2
    ; R3 [  y( O! h# cfactorial(3) = 3 * 2 = 6
    : @* |4 z; Q% P9 n4 Rfactorial(4) = 4 * 6 = 24
    2 o1 z: e8 `( W7 Q" ufactorial(5) = 5 * 24 = 120
    . I  J3 J: M/ Z, M) @
    # X8 U8 z6 s7 wAdvantages of Recursion
    * U4 i3 U. e" R9 I1 a. ]
    4 y+ J; T9 B; B9 b    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).
    2 b4 O) @/ F+ E' x5 Q2 e: S
    & i" t6 i$ q% k  e! \( y9 M& L    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    + n. |0 S& k* \% e7 q6 }0 a* B0 z0 r1 E" T
    Disadvantages of Recursion
    . O, O( V/ z: o; z9 F! M
    5 C1 @" t% u! d7 ]9 j7 @% O: `    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.# B. T$ m% v( H- j, v* t- Z
    1 Y3 [( [8 T5 y1 h. c
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).* d. f) U6 z$ z; {" {- U$ J+ e
    + R' Y, t* [* ~6 }
    When to Use Recursion, e8 B$ g; p% O+ }7 S; A8 C

    2 D. D! k2 E% m% U8 `2 F9 f( [    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    2 k, x" l  J7 _/ |/ J  o
    7 Y) T, Y) U0 `3 o- I    Problems with a clear base case and recursive case.
    : f+ E2 o, K0 {' A4 I/ I  j9 G8 C5 E0 ?. F2 W: p2 S
    Example: Fibonacci Sequence
    ! @5 `& h4 {, ^' A9 `. H/ h# g8 s5 I/ `
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    % T5 o7 ]3 p0 y7 D! r
    / h. K1 L: C8 {/ c0 l. _) q, N    Base case: fib(0) = 0, fib(1) = 1: ~1 h% }) ]  L) A2 A( N

    * h  ^+ P3 s% F    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    5 ~2 f' M5 t- w5 B; \" d* g7 [) Q: ?# p, A( i0 n  z" W
    python
    $ c- y- {# J* [: u  z  ~0 Z+ R1 k. D/ Q

    $ R4 Z) U) G/ h1 B5 |0 f5 jdef fibonacci(n):
    % \& s0 j. F, q1 v7 c2 o    # Base cases: D  t: N8 F1 c6 c
        if n == 0:" ^3 i4 ]# P0 e% h2 U2 c) v) S
            return 0
    " K# e$ o+ S1 x, \, W    elif n == 1:- k2 }, R# e$ U& r# o
            return 11 I+ m/ t$ ]* w/ |$ B2 c6 A/ x
        # Recursive case
    ( L7 m: C$ f' b, Q1 V0 p    else:
    4 _. T; x$ u$ k5 m: |0 c        return fibonacci(n - 1) + fibonacci(n - 2)# m1 M' r5 Y; W
    9 K0 z! }( V* @# g
    # Example usage
    % k! s* P- @0 a4 x0 jprint(fibonacci(6))  # Output: 8
    / E4 h( O; ?8 l* V' g* ]4 @: P
    ) d0 n. b4 _: l3 l% a7 DTail Recursion
    ( o9 ?' r9 \7 V3 N5 {% o% l8 x" }) K% {
    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).
    7 c. f. r: C9 w) R) X/ r8 `
    6 l( S& x6 X7 F5 |0 o1 Y- a+ R8 uIn 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-1 11:32 , Processed in 0.036517 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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