设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 / o+ k, w# f1 r# u
    / l( F& C9 j# Q( P/ }
    解释的不错
    + J4 y- k7 T( X- ~# P  ~& n7 E* X( |. P$ _% o: M# w: {' W' Q
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    , D& `: C& P9 x& S: s4 T) b0 p7 T2 z
    + D) A- w; [# h% S 关键要素5 Q# j. ^! z7 H; M( c% x: Q1 Y. C
    1. **基线条件(Base Case)**: F" m$ J- g* P; a4 p) }. t
       - 递归终止的条件,防止无限循环3 B3 n- `' H* G8 M. d& h
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1$ c; _- ^- [; k! ^' g$ d6 e. M
    , N& g& K  q" K3 C- N
    2. **递归条件(Recursive Case)**& s% _, Z( b7 Z8 L
       - 将原问题分解为更小的子问题
    - M& j' R% s1 b# P5 z   - 例如:n! = n × (n-1)!: p- g! z  m+ W* Q7 J

    ; [) U3 j8 q: k9 a 经典示例:计算阶乘# M7 I8 C  ]% D: B
    python8 ^7 r' g$ U4 x3 c1 w  F
    def factorial(n):* ?3 H6 `/ b- h$ p2 T
        if n == 0:        # 基线条件
    " c. y- T' i" z# g! M8 t! l        return 1' L: J& ]' h( h* W
        else:             # 递归条件' k' n. d  r& V+ t3 [
            return n * factorial(n-1)
    8 d/ H. S' k) x执行过程(以计算 3! 为例):
    " \: a9 Q7 i1 R: |factorial(3)
    1 c" M4 m+ a- c+ W( [0 T3 * factorial(2)
    5 T$ T8 q6 u- Q$ h3 * (2 * factorial(1))7 X" W0 k$ J  J6 |1 }
    3 * (2 * (1 * factorial(0)))6 B( b+ f3 Z; ]' F
    3 * (2 * (1 * 1)) = 6  }3 o8 z- ?$ W, b4 l: B6 u

    , B: t2 ]; _; q* O 递归思维要点0 K0 {; \6 ?! l! ~1 L
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑" e: i( @2 @; X/ D" X* q
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)) ?! T, |! @) `# ]# Z& F
    3. **递推过程**:不断向下分解问题(递)
    7 C/ a$ Z, X1 f; [% ]9 }9 f: t4. **回溯过程**:组合子问题结果返回(归)
    : i- k1 O3 S9 _* b9 k" C/ I1 e# k+ p
    注意事项
    # }4 s  x# H/ ]' e必须要有终止条件
    6 z7 ?: U8 O! i9 {8 v; Z! ?递归深度过大可能导致栈溢出(Python默认递归深度约1000层)& s! ~9 ^# C( D5 M( w" s
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    3 R3 @0 D+ K9 v1 ?* ~9 K- b尾递归优化可以提升效率(但Python不支持)
      g/ U5 p: m9 M* @* V& D
    3 [3 c( n* K" ?& o& B3 x 递归 vs 迭代
    ' ?, X) z: W" g5 O# C" K|          | 递归                          | 迭代               |
    - r2 Q2 D# k4 v1 n5 {& V|----------|-----------------------------|------------------|
    , j/ a8 m( m$ |! d3 x6 y| 实现方式    | 函数自调用                        | 循环结构            |
    $ B: W5 K8 X  Y4 y7 C| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    * O, W+ d' I$ \) P4 ]| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |( H# z6 |; v" D( L
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    2 ]( u& r% `& [0 `& g
    6 O4 V9 H- g2 j 经典递归应用场景4 U" m/ n4 N4 W3 P3 d
    1. 文件系统遍历(目录树结构)' n8 G* b0 j8 O" Z5 ?1 M. N( y
    2. 快速排序/归并排序算法
    ! }; t9 e9 d2 F; m- {6 P3. 汉诺塔问题
    ' n# P! O7 b1 N! k1 `4. 二叉树遍历(前序/中序/后序)
    , L2 v' ?& m. C2 [2 s# t" z% y5 i! Z7 ^5. 生成所有可能的组合(回溯算法): n4 x3 z& X( p4 X" I7 J

    & h! D5 Q. Y# X- P& z8 U; _试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    7 小时前
  • 签到天数: 3102 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,2 p& n0 B) O% e7 m& x* M1 S
    我推理机的核心算法应该是二叉树遍历的变种。5 K; w) s  ~9 m$ l3 q
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:  `2 |' G1 ]: K! g
    Key Idea of Recursion
    % C$ d, B& n6 R* v' O1 Y0 n+ }, t, Z$ z- Y" ]3 v
    A recursive function solves a problem by:
    - n: x: L# P1 p, t& r2 i; @' B, z, X$ ]' t+ M
        Breaking the problem into smaller instances of the same problem.
    , n" q# I% f: e8 Q. [6 B* M* L5 v" f, S8 {
        Solving the smallest instance directly (base case).' j+ ]' D% ^/ Z* _! i

    ! r; _5 F" p+ Y2 J    Combining the results of smaller instances to solve the larger problem.
    + j& h( g9 ?) B) X3 L
    0 ~8 K7 ?. K3 C6 g% Z6 q) ]) o( aComponents of a Recursive Function
    8 Y! l: \" I6 C7 S/ O& Z( b% s' Q: d% z% t5 F' T% s( c$ O
        Base Case:) t) o# R& q/ l# F  D4 l
    # Z5 F  y; R, W9 x! ?
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion., l7 M0 f; K: }
    ; ]/ K' G8 U. n5 q' L
            It acts as the stopping condition to prevent infinite recursion.
    3 ^5 x. j) P1 C# W0 T6 W) y5 b  K$ W/ G$ \9 \
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1." z2 s  E, m# f/ M1 \

    ( ^3 Z& h: B1 b& u    Recursive Case:. Y1 m6 C2 x- c7 ^/ G9 P; C" e% E
    8 b) ~0 |, g+ U4 u( {
            This is where the function calls itself with a smaller or simpler version of the problem.
    % x5 S8 L  E0 k2 {2 j4 _- Q/ w7 C- F" ]/ k4 E! s; I2 m/ ?
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).2 M. S& ?. c# p& Z, _& m+ H# w

    6 F( O8 H5 k8 y+ j# Q! Y* pExample: Factorial Calculation2 L& j3 J# @+ H

    6 x! }' E8 N+ ^) 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:% }% ^: l& R; e8 x8 l
    ; B4 {8 G0 a) G5 C3 L" e" C8 N$ {
        Base case: 0! = 1
    - Y( [: V% d; B) O9 Y! i. x! l, J0 x, K1 H$ T
        Recursive case: n! = n * (n-1)!0 m& Q) |! J$ K1 F0 a5 O7 [: v5 C
    $ W! {# J$ w- D4 _0 I/ j( |4 d, W# P
    Here’s how it looks in code (Python):+ q( F$ h( g( |/ o0 x
    python
    5 b/ O2 _; d( h. }8 e  [+ w3 @1 h6 W0 _9 [; d
    % ~( z0 x) {7 }, N+ b
    def factorial(n):
      c: Z* h, V$ }8 U" q    # Base case3 n3 y! S2 s, N# A* Q- b
        if n == 0:
    $ u) L7 Q, n# y3 M! Z0 J0 ]$ f        return 17 ?! K/ S3 A) F6 w. \! I  t' j6 [; e
        # Recursive case
    7 L0 `5 k9 K  L5 |    else:
    % k7 _' f, u8 f/ R$ ^- X; X, N        return n * factorial(n - 1)
    8 _: g8 h7 F& e3 y
    - }, \7 i8 f) p' T3 ~1 n6 {% g# V% J# Example usage
    ( o6 t3 C$ G3 [# m+ Dprint(factorial(5))  # Output: 1209 R0 v" u+ {: Q& m7 \

    / W4 x) Z4 R( `How Recursion Works% a. r! L+ u  F$ e& l& ?

    + A8 B, T2 x) _/ Z% w7 I( F" v    The function keeps calling itself with smaller inputs until it reaches the base case.
    3 q4 T- x8 D0 [" \2 k# l- N4 I! E) U+ G' n1 E& T0 T, n
        Once the base case is reached, the function starts returning values back up the call stack.  w* h2 }% v/ q# }* M4 {

    2 j2 q. _. m: t7 d    These returned values are combined to produce the final result.
    " i3 J) T  a& y, K0 j/ w4 C+ [/ Q# W( V+ p
    For factorial(5):9 W2 h( C3 |% w& [
    2 a" z- I$ g  B6 ?, M& Q

    1 Q8 m$ O! N( A/ I1 Hfactorial(5) = 5 * factorial(4)
    & k% p( Q3 H9 o* sfactorial(4) = 4 * factorial(3)
      t6 d; S# ?: ]4 yfactorial(3) = 3 * factorial(2)  u! Z! i/ J& ]* J% ^5 l. [0 _
    factorial(2) = 2 * factorial(1)4 [: ]8 p( K( G  ?3 O; e
    factorial(1) = 1 * factorial(0)/ r5 x' Q) O9 }
    factorial(0) = 1  # Base case
    " R1 V1 t* V9 e4 I  J8 n" j' J' ?
    , \0 ~7 l$ j" s7 O' Q- }Then, the results are combined:; G' n# d' f1 I1 r  o; G

    . X* R5 H* e. }: O
    # K3 F, K+ f" Cfactorial(1) = 1 * 1 = 1. ^  g- `2 M' g, V( D
    factorial(2) = 2 * 1 = 2
    0 n( {2 I4 T. Yfactorial(3) = 3 * 2 = 6
    6 R+ W: ~% T4 [% \2 @% n9 c8 C3 c( @factorial(4) = 4 * 6 = 24
    ( [! {  d3 z' `: l& S  g1 Jfactorial(5) = 5 * 24 = 120
    ' @6 `& P+ x' |4 u, q/ H1 J- X8 c
    Advantages of Recursion
    ) J& M8 J+ {- C* U% _
    $ O/ O# K: i( ]$ C! c5 G, q    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 P) t8 o, P% p
    4 A! S2 @# t  o* _" b- Y
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ; ?2 w0 x8 r) m( K4 X
      Q9 x( Q4 D! w+ jDisadvantages of Recursion. z; {9 A' y6 l+ k- A0 A; m8 s
    ; w% [: m- L1 N. h3 Z
        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* [# C2 n! W* A+ l* {! q
    + f! A/ F& i; v: ~' y- w2 W+ j
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    % K8 J# M6 d' _0 X
    9 F0 t3 W! B% A  {When to Use Recursion. ^/ g8 ^2 m# x3 l

    * I  A4 [$ W+ v2 c  Q    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    4 b, m9 I9 M$ p: w; v) R# {
    0 w) M. r& {3 e    Problems with a clear base case and recursive case.+ k2 E( X* c+ Q+ K! I1 E1 L0 _

    6 o3 h+ a+ x( S2 Q/ l0 aExample: Fibonacci Sequence6 f! v9 i5 y5 T1 @" P) k$ S
    6 u" V& V8 ]2 L
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
      n1 J1 Q3 H6 E1 V- x
    * W& N' S6 x# s1 q" D    Base case: fib(0) = 0, fib(1) = 1
    5 d1 [. v% ]0 y$ W
    5 d1 R: C2 ?9 G    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    & l' K# r6 T7 r7 W% ^2 {. k1 [, B4 m
      t% a$ N, v0 z% ?7 R# z3 s+ kpython
    6 h8 ]4 a, Z$ c0 j8 a
    " A3 I% P! J* K' Q
    ( i+ G) K$ v8 J! Q/ o. ^def fibonacci(n):! M# m% q7 O0 T+ f2 J
        # Base cases
      F, u# o# V7 o* p; N6 e$ P( H$ \" d    if n == 0:
    ( K1 a$ N2 T6 }: C        return 0% n4 p, C1 i! `5 ?6 m
        elif n == 1:
    - M2 A: Y- z3 c! n9 w1 w        return 1
    2 P+ `$ R' G) B  p    # Recursive case  r' Q; J4 y# _0 g
        else:
    ) c6 t. \& Z+ y. a+ }% g, h- E        return fibonacci(n - 1) + fibonacci(n - 2)% H% V& y+ Q  Q7 J( G! E0 j

    5 ?3 A+ O: P' T0 e' ~/ r! \( }; u4 @# Example usage8 A# A1 d3 S7 _
    print(fibonacci(6))  # Output: 8
    # V) Q3 `& G4 \2 `4 j$ p) C4 F
    % m4 i4 g8 K# C8 ?4 STail Recursion# ^4 G4 Q8 v( G% D# ~
    3 U8 W! {5 l, g
    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).5 r# Z) a& m4 U+ ?8 k
    ; B- E& `4 U$ X2 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-11-26 13:41 , Processed in 0.031807 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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