设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    8 Z8 I- X4 v$ B' M0 ?8 |
    ; w' Q+ T5 V  E: e0 U0 m解释的不错
    : B" b# [9 D$ T! D: q: K4 ?% F  u& x5 P% L7 C
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。& l  f& M* Q4 B3 M

    / Q! v) {8 J; H# @6 A0 g5 Z! q 关键要素
    4 s" Q5 J3 P% q; L1. **基线条件(Base Case)**
    6 t' h! Q3 Z) c3 ~   - 递归终止的条件,防止无限循环
    ( K: }) h  ]7 y" N   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    0 ?5 F2 _9 C+ O  d1 w5 k2 _& T- y( p' \7 _' C  v% F8 A2 G5 ?
    2. **递归条件(Recursive Case)**. `9 M) }" H" w! D
       - 将原问题分解为更小的子问题
    2 {9 ~1 [, i  Z$ i7 A; ^6 e6 @   - 例如:n! = n × (n-1)!4 I. W( k3 L) w$ u- u2 e( q

    1 N5 m4 O! w: X' z. j' K5 V 经典示例:计算阶乘
    0 ]3 W" C$ t& _! ppython
    ( W6 W3 z6 j# n7 S9 W. b" Bdef factorial(n):
    6 `3 \1 n& v  j; j    if n == 0:        # 基线条件
    " y  l* a+ p6 g) U        return 1% z) a5 F7 U* L3 V4 T& Y( T# k
        else:             # 递归条件
    ! C+ ^6 u( @. G  G        return n * factorial(n-1)
    $ E! b. E1 y5 n执行过程(以计算 3! 为例):
    ; ^- H4 N$ H) C, I) A& G' }# }factorial(3)
    # [! j( a4 n) {- {; ]8 ]- D3 * factorial(2)
    ) \0 c. o3 p- K6 L" M3 * (2 * factorial(1))
    9 h( V1 Z( }6 c7 k8 n8 C3 * (2 * (1 * factorial(0)))' n; N" ?3 d# v" F$ ]1 \
    3 * (2 * (1 * 1)) = 6" l- o" A* [: Q3 p; M7 [6 k& G
    , o$ u3 Y( M8 G* _
    递归思维要点
    & t* [$ c7 U; J$ f5 O' P+ t1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    3 ~3 T4 V0 d- K8 v3 \* n2. **栈结构**:每次调用都会创建新的栈帧(内存空间)' _( y0 u  C$ g( L! p1 K
    3. **递推过程**:不断向下分解问题(递), ~5 Z6 \7 {( }8 n2 C7 H# t
    4. **回溯过程**:组合子问题结果返回(归)
    $ w3 @+ k/ w9 m2 Q+ r
      i  o6 @5 T& b* r; C- ~! ` 注意事项$ S7 s8 c; j8 M1 _# O
    必须要有终止条件$ |- g" o, Z$ V% x+ w+ k
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)6 G0 y' b2 ^2 L7 n
    某些问题用递归更直观(如树遍历),但效率可能不如迭代  K, }. p/ g2 C& |. M
    尾递归优化可以提升效率(但Python不支持)8 ^5 j) e$ I% b. K6 ?5 Z) o
    . \* N, {" d5 ~/ h4 k" Z: }1 j
    递归 vs 迭代6 Q: [& ?1 o+ e" R1 }. K
    |          | 递归                          | 迭代               |# x8 C9 w) H0 _& I, ^; d
    |----------|-----------------------------|------------------|4 G: }  C- l$ {; Z) ?/ g/ ~) w  ^
    | 实现方式    | 函数自调用                        | 循环结构            |2 S4 r* W8 ]; H
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |  |/ M# Q/ P$ r
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    " b  A2 f0 w6 _6 ^| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    8 v$ L  k: s( ~& A+ b  V1 f, x4 G3 z( `9 }# L1 a) i# `
    经典递归应用场景9 k% p4 o2 x4 Q- g& E% Z" \' r4 ^+ G
    1. 文件系统遍历(目录树结构)
    3 j. J! }7 g2 W. E5 i- f& \2. 快速排序/归并排序算法  @: h' f3 g& c/ \' k* a. |% h
    3. 汉诺塔问题7 c! n9 U1 }" V( @3 w9 P7 L
    4. 二叉树遍历(前序/中序/后序)
    3 m' w7 {% X# F, y# N' f. ]5. 生成所有可能的组合(回溯算法)8 x6 }& P6 L" K2 H8 @+ @
    8 B. u: ^5 k5 v; e$ k
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    13 小时前
  • 签到天数: 3149 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,  F4 l" Z' N3 Q/ T, V' B. @! Y
    我推理机的核心算法应该是二叉树遍历的变种。3 I2 r3 _" V0 B
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    # f8 {9 ?5 Z. PKey Idea of Recursion3 U# K: Z) O* l( d  P' ]
    # `! D; a& F" \, h: x
    A recursive function solves a problem by:
    ( ~" ]$ l* E: l* Y
    * I- M3 S- Q  V3 p7 A, Q    Breaking the problem into smaller instances of the same problem.
    ' b  E7 O# H( i+ K. C; v
    ; k% H; l, `' Z6 X    Solving the smallest instance directly (base case).
    + U- q$ g/ Z) y- m% q5 P9 ^9 N
    8 [( E7 s; n' C1 z6 s    Combining the results of smaller instances to solve the larger problem.
    6 G6 Y. D/ {& u) j/ C: p+ f$ [) K. t9 y) n1 _" M, o4 \4 H% Q, G
    Components of a Recursive Function% R9 o; o: S' ~% g" b7 p2 W

    + R6 G2 \) V2 }  P# a4 Y    Base Case:
    5 k8 }( S3 G: c7 S$ A" K; k. @  |$ Y, ~/ H6 M" s
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    7 Q& u- f2 E; x
    2 Q& a. B- m: t+ @        It acts as the stopping condition to prevent infinite recursion.
    2 {$ B6 {; `. Y4 ], M2 M6 c" h9 i- b* s% W! ~9 N
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.( x. Q+ l& \6 D) \4 n8 V, B

    ; w: z1 ^; N& n2 Q; ]% ~, q0 A    Recursive Case:, q5 Z) j8 }9 ?* ^

    , m3 d! Z! k- M0 H0 B! L        This is where the function calls itself with a smaller or simpler version of the problem.
    5 z1 Z2 _! l: W' n5 F3 G! P' k$ B1 Z; t  D. C" W
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    9 O6 `8 B; \4 ?6 O. A6 [
    0 h- u" k8 g; ZExample: Factorial Calculation
    " ~5 A; x. F: v& }
    3 ^& v& m( `7 z$ H" I0 yThe 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:* Z4 A/ f/ J$ o
    - _/ d5 p# {& h- f8 o9 {
        Base case: 0! = 1" {9 P7 X  `, D
    , a( c7 w' y$ V* x( B# X* B
        Recursive case: n! = n * (n-1)!) U1 N& g' y; w8 I7 |) o5 e
    3 e, U5 W+ f" Y- ?8 O
    Here’s how it looks in code (Python):
    / J8 k0 `# a/ `: B% T2 `8 jpython0 r1 a+ E0 V) t9 S2 R) S# G

    ( M7 I+ O- @$ z" b' {6 k6 ^* ?8 Q; s! \6 S- r0 J
    def factorial(n):
    5 B0 h* W% r! O. \: }    # Base case" G- F1 l! T' L" S  z2 Z. {, f8 @! j, J2 n
        if n == 0:
      H% {" D" z* P; z& {0 i6 C  `        return 1
    5 X+ Z5 g* m. ]& l& ?    # Recursive case4 s) o9 m" ?# |# w' h" @
        else:  e7 r( ^" [) _4 E* |5 W; |
            return n * factorial(n - 1)! I  l, r6 L: G* N! ?! E% W/ L2 Z; _
    3 [2 q  K, X( f
    # Example usage, c+ i$ o! |4 _9 _" m9 s' h
    print(factorial(5))  # Output: 1200 u+ t, [% R: }  f
    - W' x7 C  D" i4 J$ C
    How Recursion Works( W" g7 z9 u( p* S" q( B  O
    ! b3 J4 q, h" {; t4 ~7 u3 S
        The function keeps calling itself with smaller inputs until it reaches the base case.2 L4 g# U. m5 Q' J- h
      C4 |& K# k( F2 A& w
        Once the base case is reached, the function starts returning values back up the call stack.+ W6 K' Y5 Y' D7 B- l! A; p
    8 g* _3 b8 @1 o8 O! l
        These returned values are combined to produce the final result.2 p. W- n& Z( \( O/ L
    / P7 D2 j" a2 L' u1 I' i$ G: }
    For factorial(5):' z, p1 t% F6 c! J7 Q& S1 P
    3 t, [$ |1 |5 t
    9 W1 C/ k% b6 R; \) R. k( w3 Y" L
    factorial(5) = 5 * factorial(4)9 Z8 g4 V; r$ `# v% I
    factorial(4) = 4 * factorial(3)
    8 V# G) X. p, D1 ifactorial(3) = 3 * factorial(2)
    3 X- ^) z7 Q. l7 V! afactorial(2) = 2 * factorial(1); {/ y* }% W9 _, C: ?% w, i
    factorial(1) = 1 * factorial(0)
    2 }% w+ x1 }% u( m% C; ~factorial(0) = 1  # Base case- D3 y: G( {" u% P

    , O. o( W0 ]- }' L6 j* C! fThen, the results are combined:
    " i% s! }+ n/ @+ s
    ) [% M% {7 F! x6 D$ L. v: C' ?) G9 u- _6 Z0 e! ^
    factorial(1) = 1 * 1 = 1
    , z( n6 V7 A2 e' z% D/ Q. ~1 n) }factorial(2) = 2 * 1 = 2& t" G; n1 _+ X9 h
    factorial(3) = 3 * 2 = 6$ W, {( R, @- ^. M; h
    factorial(4) = 4 * 6 = 24
    " _" Z; z/ a( ?6 E; Rfactorial(5) = 5 * 24 = 120( J8 g/ `9 b4 B" W

    2 g$ t' ~) D/ z9 U7 S5 f3 dAdvantages of Recursion9 x& I3 _9 \: d5 |8 d; ~0 p" {

    ! X# @  p5 w( s' ~    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).# l* I/ ~; Q! E- L" s
    $ T$ j6 ~8 v( Q$ t" s! w- I
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    1 y. N+ {3 H8 x* a. w. r1 B1 H3 q- H1 d1 g; s) q( ]1 L; b
    Disadvantages of Recursion
    9 n+ q3 N* _+ }! L* W/ J
    ! Q6 w1 `4 f+ }+ [2 j8 a    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.
    . F7 Z$ v" @; B. ~4 t. Y2 f/ c( u* I  @& x- f/ _, l( i
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    + Y1 P9 {0 M; |( A/ T  \7 ~. d. c+ w& J  t/ a8 J1 ^& N
    When to Use Recursion
    % n4 I; N7 N5 _/ q2 g$ i. Z3 v2 }" E9 W7 v: h
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).* D. Y0 k1 }5 P- q8 I

    6 i; A& Y1 W6 q3 f9 Q    Problems with a clear base case and recursive case.4 O8 p/ T& ?$ u# ?; V+ r

    5 U" V4 q: h# w5 Y. E+ wExample: Fibonacci Sequence
    ) |" d" U: Z( g. L5 N2 `9 Z9 A$ _
    / G0 c$ s" }; B3 |5 IThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    3 x/ a8 ?; T: k8 J0 a  C
    " P: [9 G/ N& R    Base case: fib(0) = 0, fib(1) = 17 \# S+ M* P6 P+ z

    / m+ F- [* I- z3 e- u4 T( O( }    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    . n: ?* _+ M7 H7 V% @, c- n/ W/ O2 t, d. u% b3 S8 ^& z: ~6 ?% G3 H
    python3 R+ _; d8 l1 V+ P
    & h1 K2 Q: Q4 A: r7 y  E/ e

    ! Y% \& v- P3 Z. l2 S" l  \$ |def fibonacci(n):
    6 D! C: m4 b4 W0 c    # Base cases
    8 \# E: n# b3 r; q9 ?: e; j8 p0 @    if n == 0:
    ( D6 U( T9 d1 p# L6 F/ Q, m        return 0
    . @6 N  n1 V2 ^# P    elif n == 1:
    4 i3 v( S7 N( z/ F# p; J        return 1* s8 M# T% y! {5 D
        # Recursive case
    $ E. ^0 L( O% c' t    else:
    3 C5 l2 A/ q& s1 o7 |+ I- i        return fibonacci(n - 1) + fibonacci(n - 2)
    ) R$ T$ r$ z; P- }: t
    ! r8 }5 L% y1 J0 L/ b0 S- Q7 D# Example usage
    / k$ b* J6 O( S# _7 J. \3 eprint(fibonacci(6))  # Output: 8# ~+ \0 T: n( i9 s% L7 \, a1 s$ c
    . V1 ~  R# r; w7 ?+ P: D8 Y
    Tail Recursion' F  X) R0 h0 u3 b2 \

    * M" s/ @& U8 o7 c4 {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).9 W- p0 m) Y5 z/ z% `3 a& {/ Y2 L8 P9 Q

    9 H% L( Q$ a1 k- O4 j0 I9 o6 E* a& ?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-19 22:28 , Processed in 0.037368 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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