设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    5 {9 ~1 Q' T- E
    8 X9 U# o6 A: C, X0 m! ]解释的不错
    1 j& P3 l# A1 U. [4 H, b- T1 @* y
    : @: Y# L1 ?! A. z2 o; O递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    9 B# v2 M) E9 a) U0 W( |
    - b0 V7 V* r- R+ C, g 关键要素- y8 l0 w& n' i2 V: e# V
    1. **基线条件(Base Case)**
    , N7 i; z) W; \2 v3 Y+ t   - 递归终止的条件,防止无限循环6 z1 Q6 ~+ |: m0 h  N( T
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    8 `9 Z. o$ \$ u0 @8 D3 |1 t% H- F6 a2 ]3 \; G
    2. **递归条件(Recursive Case)**
    5 d0 i* m  B& ^   - 将原问题分解为更小的子问题1 `% ]: H$ x* Z! G1 b7 \1 Y
       - 例如:n! = n × (n-1)!6 Z4 O- m7 Y/ k! o% u/ d* p
    " o9 F9 N& r) k
    经典示例:计算阶乘- u1 \% g; h- J7 f9 ?7 o9 g1 |
    python
    ! Z1 e3 Q( F' S) Hdef factorial(n):
    3 r7 O: C8 k) M; ?: @    if n == 0:        # 基线条件
    0 i0 S% ^3 Y* f% h( F3 v3 ~        return 14 I) O& j; [7 R% U# A: z% D# x6 p0 w
        else:             # 递归条件
    5 c( z3 T; L" F( H1 _: T        return n * factorial(n-1)
    + c5 l! |4 b1 I- I3 p# Z4 f+ x8 Y执行过程(以计算 3! 为例):
    9 D1 }3 d0 a+ ?, a# Z* V9 rfactorial(3)
    6 f# _& N9 \0 d1 w3 C9 G3 * factorial(2)
    6 d% J7 T+ X; d! Q3 b3 * (2 * factorial(1))* p# l* x+ H. G# F( I8 b; f; J
    3 * (2 * (1 * factorial(0)))
    ! T# }7 Q. V  ?5 N' G3 * (2 * (1 * 1)) = 6" }3 B1 c2 B1 m1 N! x
    " z. |. F' r2 r$ V
    递归思维要点
    0 J1 `& `! D/ M" H* B1 c1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    : n# J$ P. v" x" l' I6 D% G, U2. **栈结构**:每次调用都会创建新的栈帧(内存空间)- Z4 }7 \; n9 b9 m5 s
    3. **递推过程**:不断向下分解问题(递)- E: k2 C$ C' U
    4. **回溯过程**:组合子问题结果返回(归)
    $ _4 M" S* v4 F; N( @) F% `% Q0 M* I4 o) W) U4 E" k  d' |+ f" u
    注意事项
      p+ t, E  U9 ]) S- L" |) E必须要有终止条件. D3 k8 S2 d( y6 _6 Q# @
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层). O9 |0 u0 R/ H0 b+ O
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / ~( n8 U: L6 C/ h2 e: |尾递归优化可以提升效率(但Python不支持)7 B6 h" I( w( f6 Q+ @
    5 Q3 v  m, c2 n. \7 B% b) Y; A  p
    递归 vs 迭代
    # {6 o- p1 [4 {$ P0 `' k/ S|          | 递归                          | 迭代               |4 j# |0 b( K( w, ^, y
    |----------|-----------------------------|------------------|$ y" X* M  `- l/ Z
    | 实现方式    | 函数自调用                        | 循环结构            |
    2 C  |6 \* \2 B, Q% @, [% u- X2 h| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |$ Z& d4 o2 C  S$ d* M5 r# b% R
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ) j* W9 Z$ E' s| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    + M1 f2 C& L; U
      r5 k& n* J% U( I  f! ^, e* F" V: F 经典递归应用场景: o4 p) y! l+ Q6 `5 k
    1. 文件系统遍历(目录树结构); ?+ I& l' }( S. O
    2. 快速排序/归并排序算法
    $ M, Y, X, q9 d3. 汉诺塔问题6 l3 b8 X+ ?( d5 \. u3 ?5 d9 q
    4. 二叉树遍历(前序/中序/后序)
    : o. g$ ^7 L% C# N6 i8 \5. 生成所有可能的组合(回溯算法)
    & R5 W, i) L( K/ U' N
    ) Y' I2 \4 H7 ~* A/ {# s" H! U试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    前天 06:54
  • 签到天数: 3210 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    1 g( k+ @- e, `0 e' f# |我推理机的核心算法应该是二叉树遍历的变种。
    $ u( C0 J" Z/ @* i& T9 J/ o另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    . [, l( p) s+ ]( gKey Idea of Recursion
    " C3 V: I7 q' J4 s% k  O
    ) t$ A! k; |9 M8 ~' a( A  [7 ZA recursive function solves a problem by:# H) J6 g0 r+ ^
    + S# S- Q" X& ^) O  Q; m* s
        Breaking the problem into smaller instances of the same problem.4 j* n8 {$ f, ]' ?+ F4 B. p
    0 {/ W% r, |3 V# V9 d( ?
        Solving the smallest instance directly (base case)." H5 L% F3 a: I2 a# j" d

    ( z/ d: q( y* I9 j8 q4 c) r    Combining the results of smaller instances to solve the larger problem.2 T" T6 k4 p  G0 G

    # b, f) I0 F" M* x: S" XComponents of a Recursive Function. j+ {& l7 d/ m4 f! Z2 p, u

    % T2 a6 c$ N6 C8 s9 R- ?/ D! R    Base Case:
    0 ^, w+ @" x" G! e" v* q5 f$ e- l: Y2 ?7 O2 K. k
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 c1 c1 B  T- x& T+ A
    2 g# G$ G/ `% M: z! m, o0 U        It acts as the stopping condition to prevent infinite recursion.
    % ]# f% A% y1 c, i
    * n5 R$ d$ O8 C! ]2 x        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.1 D7 J0 l1 e5 {# X5 d4 J5 p- M0 ]4 Y
    1 m# E+ e* C2 R0 L  u+ G7 \
        Recursive Case:* b1 q3 C0 i, E- W8 X8 M1 g

    / P% A/ l6 n% Z/ `9 V+ r# b& e        This is where the function calls itself with a smaller or simpler version of the problem.; w" u0 x3 F; M! N

    $ m% ]4 g/ u& Z( h        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ; B& y) d  }: ?9 V. |. ^  _% m7 t' j/ U4 k
    Example: Factorial Calculation
    0 T0 W' i9 A6 U) U
    1 @, W' @( z' A! p0 ]( `; nThe 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:+ a. b# {% p# M0 g* y- R
    & W/ i& j8 l( k
        Base case: 0! = 1) a0 q/ r8 P3 L2 {  s: k

    2 p# ?) Y2 [* P+ @    Recursive case: n! = n * (n-1)!
    & a* _' R& Y& D  x$ ^
    / S/ {) e1 `% t! T9 H9 l" t7 QHere’s how it looks in code (Python):
    % }9 D! k2 ]$ {python- y1 P- L/ S. ]1 c& l
    - a. e* h! Y' q! h

    3 b- r+ p+ h9 X& ^9 N  L: Ndef factorial(n):
    % b% A5 ~2 X) [6 L2 y; K" z& j    # Base case
    0 @( K1 b4 X* r! K    if n == 0:
    4 P- W; @2 F+ J7 j        return 1
    7 M5 [7 q' j! r    # Recursive case& U' e( _% ?" x: N
        else:0 `+ m3 d& ?. k
            return n * factorial(n - 1). L* t: I: r% K4 |" c
    ' V. `" k8 ^$ j( l9 O
    # Example usage4 _1 {# c( _) ?
    print(factorial(5))  # Output: 120. z9 B; m$ T4 [, T% y7 b

    * j9 |5 Y5 |( E* m3 N' Z4 pHow Recursion Works# D* ?$ Q9 F% C1 ?9 P6 z

    5 w) r, A% b7 B+ a$ E    The function keeps calling itself with smaller inputs until it reaches the base case.7 P8 `! W; w/ ]' n

    : D4 C3 _4 w/ ]9 Z: z% U    Once the base case is reached, the function starts returning values back up the call stack.' A" x  p3 l& @/ @4 |) P8 j0 C% t( G

    4 ?1 F0 o$ b" ~- d- o( q    These returned values are combined to produce the final result.
    8 S- I# l# q. \; h. Q! }2 }
    % A" L) Z1 \" x8 m, H- C, D- sFor factorial(5):
    : }% x, F2 k6 N: A0 E  q5 S/ Q8 }! \4 N- D

    , }. V% O- ^3 I6 M% mfactorial(5) = 5 * factorial(4)
    ; b. q# ~1 R+ X; Z. ~! |) `factorial(4) = 4 * factorial(3)
      w- Y( S$ G1 d; S" Bfactorial(3) = 3 * factorial(2)1 b& ?( c0 X, Y* W, k, |, b
    factorial(2) = 2 * factorial(1)! A. c: L/ [  X) s( G6 C
    factorial(1) = 1 * factorial(0)/ i6 X9 X- ]. ~1 y3 X. V
    factorial(0) = 1  # Base case
    4 j( o) P: W$ g% R& e6 W
    8 O1 d2 E: R( w& y0 pThen, the results are combined:/ ^, ?: G# D- A, a2 [) D  A$ h: t

    3 H0 A" I. U6 m# Z0 W% {
    , F9 g9 m/ e/ \8 P6 mfactorial(1) = 1 * 1 = 1) j) ?8 o8 n5 ^1 i: |
    factorial(2) = 2 * 1 = 2
    * ~/ d) t; R& m2 e& @% ~factorial(3) = 3 * 2 = 6
    & Q$ J* c( S, x3 B- B( `factorial(4) = 4 * 6 = 246 d/ {; \1 E- \$ `2 Z! y8 [
    factorial(5) = 5 * 24 = 120) s1 l/ _1 ?- G- \2 s( Q
    3 ]' \9 `  K( O3 G( p( P4 f
    Advantages of Recursion. o8 k5 k7 R8 p& ?

    ) b) V( b* S$ H+ k: m$ 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 p. \3 ^- r* i* z
    2 }; T) j, j+ M5 n# i    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    . q9 i1 `5 S0 N" x5 X( X2 ?" M1 a7 V4 h7 q+ y8 m
    Disadvantages of Recursion
    ) ^  S# ]5 M2 i$ Q- b! K
    " x5 ]4 y# Y. V1 r    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 G  J3 B  v9 O- n7 W( G' W/ Q
    " m9 p5 C6 p/ ?    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    - x( {5 O% a0 ?9 C4 d7 q% _9 D" D! `# u5 _! |7 m; H2 T) J
    When to Use Recursion0 M( P: m% x2 s& k

    1 o1 ^9 M6 N( N( b+ V    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).) l4 r) B# a) J
    , q6 {& j1 q% t
        Problems with a clear base case and recursive case.
    , F. X0 l  t6 U) m2 t- d: O# V9 D8 T, o' p) K6 G! f: M' P
    Example: Fibonacci Sequence
    4 w! [- V4 @/ ^: q3 M
      l/ z" T% j" v& y: e0 Q8 OThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    - v7 l) {& P  v4 p3 L  |
    5 R1 \3 f8 ^1 n0 `. g, s8 [    Base case: fib(0) = 0, fib(1) = 1& G; a, x% v3 B; }2 a

    ; r0 G  _+ ^. L* {5 t    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    $ ?6 A  k0 F2 K& i$ p
    8 U4 ~1 e8 l# xpython
    " d) \8 c- e' X  o  H3 F( @7 F' n" ]3 A2 l

    & ]/ V& P+ S' t& J# L1 Kdef fibonacci(n):
      J1 }% `/ X  L2 D    # Base cases
    8 G4 |9 x- m6 t' E' t7 p& a- ]    if n == 0:
    ( u  y* g) r( ^2 A* H( E  |% m        return 0
      A8 U- C* \+ M! _; R    elif n == 1:
    . ]* R/ f' G! Y4 U( H; D        return 1- ~2 [. P. e# `7 g- T& K' x) `
        # Recursive case
    9 r: w* {  a6 Q$ Q6 h- k    else:& \, _9 j1 l7 g9 n
            return fibonacci(n - 1) + fibonacci(n - 2)# X: [. P% A, M# |  W: g/ S
    3 k) \/ j' h7 n
    # Example usage
    . _8 R9 q. ]# |; F1 @( j- E. o5 Mprint(fibonacci(6))  # Output: 8
    * s# J$ M0 K" `' g1 f0 D# E( h  f8 w$ d2 L: d  I
    Tail Recursion
    . G' i1 ^8 E' a8 O6 _) p/ }: c- n+ p" p; ?' 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).
    5 l' Y! U/ x; |3 k: E& h3 W! @
    / G( z% V2 Q* q+ V" w# C5 V5 TIn 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-2 20:57 , Processed in 0.058040 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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