设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 2 }5 |) S+ U6 ~; U( a

    7 c9 Y- ]& [1 y解释的不错
    ) Q' ~1 a) m, H6 x
    ) L: M/ t4 B( X/ X* L- _6 X递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    & k; \! `" ^; j7 H& r, Z4 U& m- i/ B0 {; Y# u( ^! Z& I% o0 O
    关键要素
    & y! s$ _1 i' t% ~8 E2 Z5 B1. **基线条件(Base Case)**
    ( H  H4 H3 o) _( F. d0 `. ~5 M' y   - 递归终止的条件,防止无限循环
    % P/ F$ q1 ~  B2 {  u6 M- I+ K' l   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ) Q7 ?8 H% {9 N4 A
    * {3 r7 L9 \# N/ l& A2. **递归条件(Recursive Case)**+ A6 j! W" G8 V9 c6 p
       - 将原问题分解为更小的子问题& j/ f% B3 O" r3 E' h/ M# Q
       - 例如:n! = n × (n-1)!
    * S" A4 h- J5 u/ S3 e2 Q8 s' S, ^
    5 |6 e4 w% {; [7 S 经典示例:计算阶乘& b0 P6 a8 {: u. }" b2 T
    python1 \* k+ n8 B3 [0 ?4 N7 b
    def factorial(n):% o" u! \; n! x: T  r9 B# W
        if n == 0:        # 基线条件1 ], J. P$ m: ~; I
            return 1
    2 ?: D0 @8 B  T8 P/ C* H3 J: I    else:             # 递归条件  i6 `. u/ Q; J  X$ m. M
            return n * factorial(n-1)
    ' l1 n+ {# g% ~8 e' U4 I" A3 ]! K* b7 J执行过程(以计算 3! 为例):+ g' Z3 @4 i# d" d: P
    factorial(3)
    . ?& d2 A3 U- ^8 y1 h$ s$ U9 R. d( C3 * factorial(2)
    2 L, t* O  x3 W7 [$ s" k6 i3 * (2 * factorial(1))0 N' {7 B9 V  h# |- R  |
    3 * (2 * (1 * factorial(0)))
    9 ?9 r% I  w' h# Z- K  h3 * (2 * (1 * 1)) = 6
    : A7 O9 K  c# D: |: \+ ^* h0 b& U; \, k+ R5 z0 r! ^
    递归思维要点
    - g/ f6 H1 M& W& B5 t8 a0 \( d$ s, y1. **信任递归**:假设子问题已经解决,专注当前层逻辑- O; x$ F$ p+ N/ e& H: J% A: J
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间). ]: p& V5 W0 N" |0 T
    3. **递推过程**:不断向下分解问题(递)  k3 h  g" ]* a0 y
    4. **回溯过程**:组合子问题结果返回(归)* ^7 G1 n. X# M( D) X; i
    - M* D8 Z* [  {
    注意事项+ m# T9 h$ r3 V4 E
    必须要有终止条件
    % u; X9 i6 Y5 F. e递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    8 X% E' ?: t# P0 O, _5 Z5 X某些问题用递归更直观(如树遍历),但效率可能不如迭代  a1 g; a/ L2 i; c7 j- `0 L* y
    尾递归优化可以提升效率(但Python不支持)
    5 j( \# W2 x' u' v9 a( H
    , E  l9 n( d- H; N 递归 vs 迭代
    ! ?! o- p! m5 ]) b5 r|          | 递归                          | 迭代               |
    ! D% c/ N3 ]6 {1 `# s  m|----------|-----------------------------|------------------|
    $ r* W/ O) h; X: l; I| 实现方式    | 函数自调用                        | 循环结构            |" P, q6 G4 ^5 v, k7 `, P
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |) A8 F- z7 y3 k7 F" r, ~
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 _" b, P0 T# u' V6 {| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    7 T0 @6 \* h2 ~- ?1 |/ l/ P5 q5 V( |6 H  j2 D$ C- }) D
    经典递归应用场景
    * {- }2 V; o/ @( c1. 文件系统遍历(目录树结构)
    $ g% L4 ?& \, x9 [# G# m2 A2. 快速排序/归并排序算法: k* d, ]) e9 ]4 X. Z
    3. 汉诺塔问题1 ~" f# X$ q/ Z( T0 [
    4. 二叉树遍历(前序/中序/后序)( _$ U* f; r! y9 c7 I' L9 y
    5. 生成所有可能的组合(回溯算法)
    " A- A1 C5 x- A3 P0 m/ ~0 k
    # Y$ N; H, v3 p* {9 g: T" B试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    15 小时前
  • 签到天数: 3190 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 F3 u" F7 _+ L& A9 k
    我推理机的核心算法应该是二叉树遍历的变种。
    1 R$ F, O# U" P; X另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:) [$ Z8 ?( B) J( z
    Key Idea of Recursion  ^8 M5 u7 h- r; M
    ( i; L$ Z+ g( U/ Y* M
    A recursive function solves a problem by:
    * i! k0 l( o, c
    5 a$ ?* X0 \! P9 z* f) @+ a# ]' ^    Breaking the problem into smaller instances of the same problem.
    7 i4 K# w) q- r% ^! i+ l3 _4 X9 `! S& k, [: m
        Solving the smallest instance directly (base case).2 v- _4 l( w2 V; ?' }: N
    5 O2 B. d9 m# \- i- {  Q
        Combining the results of smaller instances to solve the larger problem.: Y) Z2 O/ }. Y$ n5 d& J, F

    ( ]% v- P9 n8 ]* D2 |; f; PComponents of a Recursive Function
    & @  L) P0 y6 N* m! D
    / ~" p8 T+ H; D! n" f( r% V    Base Case:
    * v  l2 \5 k; O5 Q( g: n
    / k! r- l# F7 C3 e7 a0 y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    3 _8 h2 _: A$ D9 S; e
    8 G- }2 V! E& p1 z        It acts as the stopping condition to prevent infinite recursion.
    7 y: k  r' d- Q5 O: I8 j1 m+ _# a# J8 v
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    3 T5 b" W# s+ ^' v% N4 s; ~$ n
    " Q  b$ a7 J4 u/ Q3 Z( S# Q/ k    Recursive Case:2 i5 z/ U6 V1 f2 g3 v  P; T

    0 d5 ~. B) M8 }0 N6 {7 e6 u        This is where the function calls itself with a smaller or simpler version of the problem.: A- R7 s! j% u( d* u

    % H9 f0 N$ @( D  L8 B        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    6 `. D) j0 o! v/ b( O2 w  U4 d3 ~; d0 H5 n+ ?$ ^; D
    Example: Factorial Calculation
    - c$ }: ?$ h' I7 o, b. d8 I# b+ V! Q% ?& D7 a8 a* D9 F& o$ J# O
    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:  K( u. D, i1 }" Y. m3 I( z
    3 y" m5 L" N: H+ ?% r6 n! g
        Base case: 0! = 1
    : I2 `/ Z7 [7 ^& U: }  @* R" I
    / |9 B" H* v' ]1 \* `$ w    Recursive case: n! = n * (n-1)!
    ( ], z7 F0 e1 U  D: E: Q3 p5 B
    5 c8 L+ d! E# h9 ]$ d; KHere’s how it looks in code (Python):% `" D0 P# y) [- `( P' P- `
    python
    : @; E% ~& q" ^% H$ A& v. g; W/ `- x: U/ q/ \' h
    $ h2 W9 d% H0 |, [! v8 j$ K9 J
    def factorial(n):
    $ _% }8 j8 t4 F9 @    # Base case) M  K9 y, D$ X
        if n == 0:
    9 `; J2 w& P; Y4 b) A        return 1
    - A0 a7 f% W" D1 f    # Recursive case! X  D; l  ~5 L8 x4 o
        else:
    / f" a  j" o" {( {5 z2 ^; K$ l        return n * factorial(n - 1): c& W( `( ?7 m( ~
    * t' A9 Z& f9 f+ L: p
    # Example usage6 k. j# Q) t# P- w
    print(factorial(5))  # Output: 120
    - J2 B: W/ Q8 O5 |. Z  H2 d6 ], |( A! P7 ]: E8 s5 q
    How Recursion Works
    ' r( x. e6 U) L( K  u+ b: C4 N6 U* e) C! B' D. H" l
        The function keeps calling itself with smaller inputs until it reaches the base case.' B! ~! a8 U9 E. M) d7 R
    , N! ^- R' x1 ~2 q0 z' U
        Once the base case is reached, the function starts returning values back up the call stack.7 ~5 i/ O5 W+ N! P
    $ z; @9 i- p8 j0 a: n7 N
        These returned values are combined to produce the final result.
    , o! s9 B. _* y0 J' l' L- X. _; B+ A3 X" k1 |- s
    For factorial(5):
    : u. x+ W" _( I
    9 H7 |' G. h" s! y( [7 N! F3 l3 C' b
    7 G7 }. y$ Q8 J* y7 r+ Afactorial(5) = 5 * factorial(4)- v6 C6 p9 P% l% h& `
    factorial(4) = 4 * factorial(3)* n7 A1 l3 s5 K; u
    factorial(3) = 3 * factorial(2)3 c; D  m: \3 v) Q1 n( F0 Q# y7 h
    factorial(2) = 2 * factorial(1)
    7 b$ Q, c7 w2 hfactorial(1) = 1 * factorial(0)
    2 Q7 K5 t5 E, [* }factorial(0) = 1  # Base case
    ; h, l0 R8 X7 _2 m" Z  n' Y
    7 L- R0 v: T. j# }* X8 Q8 {9 JThen, the results are combined:
    $ d; s' l9 \8 f5 C
    7 _% t# B) ^; [6 W' b6 {5 l; Y5 ~5 J% \- d* C
    factorial(1) = 1 * 1 = 1, Z4 b  K) N+ X" o( [
    factorial(2) = 2 * 1 = 2/ h4 ~6 K3 R; X+ W8 }
    factorial(3) = 3 * 2 = 6& u3 A/ V2 Q; F* b. x8 @, L
    factorial(4) = 4 * 6 = 24
    ' b5 `1 W  O# J9 z8 q  Afactorial(5) = 5 * 24 = 120& S2 D' l; J/ n7 Q- x% q, m

    5 Y8 A2 V0 K( e& h1 fAdvantages of Recursion
    9 n" H' A! e8 p
      e0 z6 o: w. f. Z# 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).6 O+ q( S3 x: m3 q7 q5 Q  g$ Z# \0 C
    7 N# z- b1 b* ^( s
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    2 [. \( i0 A" ?+ H5 r: }
    ; w& B" B. h: i( K: nDisadvantages of Recursion; ^1 r. }2 @  M' d+ m0 p% y4 |: p& @

      Q/ K; n1 B7 x    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., r1 h' H( f3 G; Q- R3 D3 R! G
    * U& z' \, r# h; M+ @' @4 I
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).' r! {7 V! a, y
    ( p8 P) G6 [+ N" n4 f& d
    When to Use Recursion' a+ Q7 v; q3 z% t

    8 U7 c6 J! e. B5 L: r( z, K5 x    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    7 N2 U) u. ~$ A7 D* M# I
    4 \5 i8 Y4 A2 w% W3 z4 F& F" ]/ o) f    Problems with a clear base case and recursive case.
    ! c( \3 \/ ]( M- g0 v8 q- b  r" j. F2 v2 S
    Example: Fibonacci Sequence; }& s2 o; F4 R7 n9 }1 ]
    % v: J9 x3 ^6 Z( ^- V' t8 Z
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ) f, g9 a9 ~$ V: }! \% H; X7 w1 l- k. v
        Base case: fib(0) = 0, fib(1) = 1
    4 P* Y9 @+ D! {2 c
    9 w5 E, ^- v" [- P    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    8 E: N) j/ w0 q2 J
    1 V& v, ]) X# l4 D5 y0 g1 w7 {, Kpython$ r" }3 Z5 M1 `% X# a5 o6 D

    # j; T  l7 |  y! h! K8 j: O5 ]$ G- S* {1 v% r
    def fibonacci(n):
    5 b% F; G, r% w% S" f# e+ X; [    # Base cases! i; }$ c* _) \0 _+ j7 s# x1 G5 ~2 W
        if n == 0:
    0 x: `) C6 }3 b) X5 h1 j* N        return 0
    : ~' S; h0 a. D0 N  t    elif n == 1:
    $ R0 h2 ^# a$ e% I! d0 Z) e+ q- Q; F        return 1
    ! F# o% o5 O  t' f- A% D    # Recursive case
    8 e% a/ D; @8 a2 y    else:1 B1 G+ ~7 m5 j, D+ _  [7 Y
            return fibonacci(n - 1) + fibonacci(n - 2)
    " g2 v$ n# F" h4 D# G" H* e& v
    3 L( A. P  R, o4 l: K# Example usage
    * U6 `( Z! i" b  N4 rprint(fibonacci(6))  # Output: 8
    * W% o! m' Y) p+ h7 ?
    & [" G9 e3 r# o) wTail Recursion! B& v; F4 b$ q5 \4 \
    4 q) x" m2 j& k9 t' B  _- M8 ^
    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).' D- V2 f" V  {; P# j% _
    * W: [! T8 |8 J3 @' B% e
    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-3-3 23:52 , Processed in 0.061864 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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