设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    6 z0 v  |0 i6 b; _( J" g0 z- h: y0 [% T6 A
    解释的不错: a" m' o6 ?7 K5 Y8 ^5 R
    5 P6 h: Q4 a: j# L* q
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    , b' K: [6 P) e) Z# r7 d, t( G) w) U
    关键要素
    8 U  R" U+ R( m: [# ^1. **基线条件(Base Case)**
    7 K* [0 `& H0 ?+ F   - 递归终止的条件,防止无限循环
    - y- u+ r7 q, l% u7 A, M   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ! e3 R% Q. g( w% X/ t) n, F: Q8 l& z8 ^/ b6 `$ d
    2. **递归条件(Recursive Case)**+ }# i0 r8 @4 ~" X$ S
       - 将原问题分解为更小的子问题( v4 F1 w" _3 a- n  ?! N2 `7 @) e. b
       - 例如:n! = n × (n-1)!9 F4 S- v+ |0 r2 }' k: w: |

    ' h3 f8 a4 ~5 L 经典示例:计算阶乘- ?7 s0 X- h- @3 [' H! R
    python
    2 S* w- @# f7 A/ f+ q& Ldef factorial(n):% s/ R+ S2 k' E- b- \/ z3 z
        if n == 0:        # 基线条件
    5 A% B8 S! n8 \! q$ K/ Y+ A  C+ i' R        return 12 h3 f  ~; f2 o# S- R$ ^( j" v5 v
        else:             # 递归条件/ h) ~7 z& g0 R5 K2 t0 Q* C% U" E
            return n * factorial(n-1)& ^9 C: U& T* _2 w7 y( B
    执行过程(以计算 3! 为例):9 N6 ?! z" `' k5 C7 @# r# [; L. I
    factorial(3)' ?% R: _5 v) f* D6 t1 Q( M
    3 * factorial(2)7 N0 ]2 {  |' b' M& z* Q
    3 * (2 * factorial(1)), o& Y! D) E2 {0 B  `( k7 i
    3 * (2 * (1 * factorial(0)))
    7 v1 M. V- d/ b$ p, S3 Y3 * (2 * (1 * 1)) = 6
    " K% h- N% J# i/ X, [
    0 M: c- @1 Z, E' Z: I 递归思维要点7 d- j8 W+ {3 ]: }
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ; E$ }- G5 j3 A5 u5 t" R! {8 {2. **栈结构**:每次调用都会创建新的栈帧(内存空间)8 a0 ?! |, p( B" q. \
    3. **递推过程**:不断向下分解问题(递)
    0 W' v3 k4 h- _7 f' ?4. **回溯过程**:组合子问题结果返回(归)
    2 @! |$ C/ k9 e# }" x/ T$ \4 y; A) I# M1 T" x0 Z, R
    注意事项# R  [5 ]7 a& \. k5 j
    必须要有终止条件
    . r& L' y3 e4 }4 l6 E% K递归深度过大可能导致栈溢出(Python默认递归深度约1000层)/ G9 K" s3 s, }. L/ S
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    1 C: H% t6 L: U' m2 _4 S尾递归优化可以提升效率(但Python不支持)
    1 A. ]3 s$ v( [; O' L5 I3 o! \8 z. K: m8 N9 C% T8 x
    递归 vs 迭代" ^8 C" A2 G  ]0 t8 R" x2 }
    |          | 递归                          | 迭代               |
    8 r. E+ r' ]1 I) b, n7 Z: c|----------|-----------------------------|------------------|
      L' C5 L: A5 Z| 实现方式    | 函数自调用                        | 循环结构            |
    . F) c$ v2 |; M& ^5 L| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |# e- a& D. K8 x7 |! s
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |  u, e4 B$ L6 J% J0 \
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |/ y. u4 d0 D9 j
    : }9 @! Y9 X9 i# X& e. ^# u* J
    经典递归应用场景6 U, p; d( ]0 Z* y$ f
    1. 文件系统遍历(目录树结构)4 `+ M  A$ u8 q! p6 G' k$ v: J
    2. 快速排序/归并排序算法9 ]& Y  F$ F+ }" u. x
    3. 汉诺塔问题' T+ {7 p5 F# O& ~$ @( w
    4. 二叉树遍历(前序/中序/后序)
    1 b$ ]* @4 A4 L0 y$ [2 |3 C" H5. 生成所有可能的组合(回溯算法)6 ^- [9 p, E8 C' `/ @( h% }( e0 b9 p
    $ _% k$ x. S* J- w; x3 j
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    前天 07:45
  • 签到天数: 3217 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ; p% A, Z8 D$ Y2 Q$ l我推理机的核心算法应该是二叉树遍历的变种。  D+ j: a7 a5 o! n" ]+ 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:
    / F# e; R* [5 PKey Idea of Recursion
    7 a# `/ q6 p4 E( D3 m
    6 d6 O) ^- b# T( L! B1 WA recursive function solves a problem by:
    & N5 U  W1 S/ ~1 Y' X; y: Q" |" y7 h& Z1 ]
        Breaking the problem into smaller instances of the same problem.0 {2 H7 Y1 Z0 e; V8 X
    6 A0 @) K# F2 u/ l7 C
        Solving the smallest instance directly (base case).  a% r, I2 O1 n; {6 x- D. z6 r, l; U

    9 C  T! U! N" d8 d& a' Y- W; p$ H    Combining the results of smaller instances to solve the larger problem.
    1 X* D- M# t+ z- P; Y2 s1 L& N+ J& [- Y6 D
    Components of a Recursive Function
    7 j( A& u  [9 \& }2 W8 b. c  n" x* y: q- c/ h4 o' B4 s/ u
        Base Case:6 T' F2 ^2 H6 K8 M2 o% W
    / H2 y: T5 C2 b
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    5 F7 ]! A& K- _' K3 v, J$ O9 q
    5 f; Q3 V: p$ W, F        It acts as the stopping condition to prevent infinite recursion.
    2 L; E8 P' i$ M- d' }, p6 h: Z- I9 M2 D
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ) R5 o: ]$ p' {$ {2 ?$ v; S2 [$ b; e
        Recursive Case:  y% _3 e3 v' x6 v4 O2 C

    0 E7 W/ _, {# Q8 x  g3 G        This is where the function calls itself with a smaller or simpler version of the problem.. h" [2 J0 w2 @- k* N7 W
    , U# c( q1 b+ F' v/ u3 Z. Q
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).& e/ x( D& ?: ^$ h7 N( N' E, O

    ) b$ j( V% }, r+ f) H5 VExample: Factorial Calculation2 }' u# F9 }9 J7 r2 x9 W1 E; r

    + t( K! i+ y. B& 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:9 s6 D: t# `0 t4 u" |

    & G, S0 r7 \8 Z8 M: a% W% p8 b    Base case: 0! = 1
    . i% h! r" [, z* l$ N# d# }' ]
    - v: A3 S0 D4 y6 d/ Y, ?& r    Recursive case: n! = n * (n-1)!0 m+ x7 a3 k4 [" N
    , [3 a3 E: t2 b: a/ [$ m2 [  I$ E
    Here’s how it looks in code (Python):
    / T( W: `+ L$ d7 x$ Kpython
    6 P6 p6 A' e1 B8 d4 i* |* ]$ q& M
    7 E+ i9 e- u- a+ u1 r" V% l6 H) K1 X+ e8 ~  b1 T. n- x
    def factorial(n):
    + U, f" ]  S( i    # Base case
    : S- O' G" i8 T  d8 T    if n == 0:
    ! f) G# `& k$ [        return 1+ D( }9 o2 ~  L; y
        # Recursive case
    % Z6 _. a2 p3 ~+ K: O    else:" o% Z. r: t# X$ p& |! i1 y
            return n * factorial(n - 1)2 ~8 [, ^9 X- n( L0 R2 C$ u

    ; A2 E6 u# x+ d5 {# Example usage
    + t2 M6 {  S) m: W4 cprint(factorial(5))  # Output: 120- g+ [4 v% P9 q
    % @3 q0 b3 h  j" G/ d3 x
    How Recursion Works; N& l2 S3 X% x# L5 _: r
    ( e/ M! }+ ?8 d  t8 _! ~7 ~0 k
        The function keeps calling itself with smaller inputs until it reaches the base case./ m2 r/ G, c0 S/ Q' v7 X  E
    ; h, q7 U' S/ c% |  ^. {4 ?
        Once the base case is reached, the function starts returning values back up the call stack.
    $ o' k' B, O" i, g: r# O& K, a# }
      m9 N( i, d. r% R0 R' m/ d    These returned values are combined to produce the final result.
    , _& ?3 B- R. T8 A; H3 m. ?9 Q+ `8 S8 {) T) o: Z! ]
    For factorial(5):; r/ A3 H" u7 O' L+ Z. R( l3 n

    0 D/ c& b' F0 }8 d( I1 m; }* c. E* E& j4 ?
    factorial(5) = 5 * factorial(4)( S& R5 ?7 n: F2 b/ q3 i/ u7 ^, X
    factorial(4) = 4 * factorial(3)
    7 {3 W$ f" S9 Y% Z8 t4 Qfactorial(3) = 3 * factorial(2)1 U1 l) X- G- M* |$ Z% w
    factorial(2) = 2 * factorial(1)
    2 P; y5 @. g# M- p; Dfactorial(1) = 1 * factorial(0)
    9 A/ M" p5 O3 G8 t2 j; ifactorial(0) = 1  # Base case$ X* z( p, k4 p2 [5 u2 D

    * r. Z; j" U* u! B* }* ^Then, the results are combined:0 W4 X$ K, B& a3 o! g1 `3 F# ^, `& L
    4 p# @3 ]: [. z# a
    # }! Q- M3 F1 m" z# u
    factorial(1) = 1 * 1 = 1
    - c9 F. @9 z) G: {2 dfactorial(2) = 2 * 1 = 2
    7 k+ I/ ~4 _% F) g1 F. Bfactorial(3) = 3 * 2 = 66 \: r2 c$ R: E' G" I3 @1 g- Z
    factorial(4) = 4 * 6 = 24
    ! ?* v" m- a) J1 f6 yfactorial(5) = 5 * 24 = 120( |) D2 q, E" r( _  a! c
    ) b8 ~3 R6 w8 y( {3 ^+ L
    Advantages of Recursion' j  q. v) c1 j# T; C8 a

    ; M) [7 s& b' X, C9 z# [6 D+ o3 v' 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)./ M7 v5 a/ x8 A# G6 i& I: Z

    : ?7 g8 C6 I( b+ h2 [* x7 |    Readability: Recursive code can be more readable and concise compared to iterative solutions.9 d4 [  M8 d& M# X5 b

    " w9 f9 M1 f/ n4 v( _- y2 UDisadvantages of Recursion
    ; {/ W% ~* l) N) }
    / p  I; L3 {. Q( ~5 z9 C    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." ?8 A2 @2 `5 X$ Z4 ^7 ?+ a

    9 h5 ]; a. p% p0 ^7 f    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).; w" A! G7 P" m* y# |7 A8 |, m

    # \" D3 |4 q; M- u& YWhen to Use Recursion4 T' l, p+ l6 k2 i! h

    " v2 k$ X+ Z2 ?; Q0 c7 t  F    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)., Z; Q% D6 G7 X# @1 m* D6 h

    # F7 o3 [5 I' ?. H& j# R    Problems with a clear base case and recursive case.
    , d. F$ [2 _. [+ H! {' C: a: _# s/ y$ l5 \# c4 G* a7 `. Q0 P3 J
    Example: Fibonacci Sequence- g) F% h( S: H0 a6 F: ?4 d* H

    7 ?2 u# _! B0 @) YThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:0 s# G  e# y4 u6 ^' O! ^
    2 U7 I# C9 T. d  x- x, F
        Base case: fib(0) = 0, fib(1) = 1
    9 c& J1 q, x1 E+ i5 y
    , p) l! S8 @% ~$ l    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    . e, [* ?5 X  \. b, \" _# [* A& i/ q( D
    python3 R& C  {: V6 X  b  f' J4 u8 y
    1 |- W+ m- |! U8 n. S# A1 \
    , S: g* k, [" V& P% p
    def fibonacci(n):
    ' r$ t" R& {( N    # Base cases
    / I1 q3 l+ J; H9 n    if n == 0:
    0 F' R0 z1 v5 K3 R( _2 d        return 0
    + L3 n0 \7 T" s' T    elif n == 1:
    * ~8 }! E" T8 W9 ^+ H        return 1' d- i! x, y! U. M5 y2 N. }; p
        # Recursive case- p7 `# o' G& E3 H
        else:
    - q5 ^' Z" _" x        return fibonacci(n - 1) + fibonacci(n - 2)
      H6 }+ ?5 s' ~( [3 M
    % b7 `# N' _( H3 A# Example usage
    & o& X* a$ X9 S, a) j% z2 `print(fibonacci(6))  # Output: 84 A" t, }- K$ P

    2 M. X: r3 Z9 e  R5 R0 ATail Recursion; s* X/ J9 {1 [- |8 \! w
    6 I& n- t5 G$ c% V; \4 _$ e
    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).6 [, k7 h, s: ~1 V3 {6 o. U- K

    5 V4 u/ J/ V# a6 o0 w; N0 eIn 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-4-11 01:06 , Processed in 0.213486 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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