设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ) ~" A2 A% j1 n9 x5 E2 I( e
    4 |( [- o. O. Q解释的不错: R7 l! p' M# G
    & S4 ^8 U/ R% e; q6 N6 K7 h
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
      b7 E! q/ z# k& k( e$ g! u, D: r! w+ [
    关键要素; n; B! M0 i$ K6 {1 O4 T7 m' a4 B" `0 `
    1. **基线条件(Base Case)**
    / ~, W  w% }/ ?4 M   - 递归终止的条件,防止无限循环
    6 l5 v0 u" ]8 ?! G0 n8 M3 ?   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1- z4 _  C+ o; }7 Z- R

    ' v- F. H! Q' x# v! w* m2. **递归条件(Recursive Case)**
    # e! T( e* \0 \   - 将原问题分解为更小的子问题
    " P2 D) q. |6 \* H) ^   - 例如:n! = n × (n-1)!
    - t- o. z2 a: X3 m# m: k4 w4 }6 I. @+ O- O1 C
    经典示例:计算阶乘
    1 {7 `7 A8 _+ _4 L/ tpython: ?2 _5 g) H+ i+ [
    def factorial(n):" E/ t5 x* b0 ^1 {( L
        if n == 0:        # 基线条件) l3 |+ w: z+ Z: z# Y" j! ~
            return 1+ f0 d# A* N" N1 L0 ~' }! Z
        else:             # 递归条件; G8 Q. C7 ^, `1 p. X2 H# @$ _* r
            return n * factorial(n-1)
    4 S( S+ N4 b3 A5 v2 Z! E执行过程(以计算 3! 为例):3 l' l6 O, E2 v
    factorial(3)
    3 g9 d4 S9 b& u- `: [3 * factorial(2). K$ a0 n; }, U) Q1 P' e
    3 * (2 * factorial(1))* D8 M. y# r' `7 ~+ w* |
    3 * (2 * (1 * factorial(0)))8 {0 K/ L2 `/ S' F6 M
    3 * (2 * (1 * 1)) = 6( A# A: ^! y  W
    1 U3 u! g! u- v4 u* ?/ d" k
    递归思维要点# D) L! ]# W5 ~9 n" N6 Q
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑$ n, I6 i0 ]+ r, g. I3 ~4 k% c
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    7 t/ ^* k6 @  ~9 W3. **递推过程**:不断向下分解问题(递). E7 }. t. Q- j6 i& Y' `' F6 g
    4. **回溯过程**:组合子问题结果返回(归)( q* O+ s) ]+ {, s

    1 N# t. N- b# o% s# l; a3 G% ]# P1 q 注意事项# v  i, {- Y: q, K8 `% F' [; \
    必须要有终止条件
    * H/ s8 _- d$ |递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    + v( D  {  S# y* X某些问题用递归更直观(如树遍历),但效率可能不如迭代  i) Z1 h2 a  t2 g( _+ ]
    尾递归优化可以提升效率(但Python不支持)
    3 i9 x( `) Q! u) `' @/ G" V8 v5 n& H7 c6 E+ Y/ u
    递归 vs 迭代2 }) c$ E+ Z- X8 q  F
    |          | 递归                          | 迭代               |1 G& W% c& F! @% ]( I9 P+ Y0 A+ a, D# r
    |----------|-----------------------------|------------------|
    & _  F) u( q8 H, ]* [| 实现方式    | 函数自调用                        | 循环结构            |0 ]# ^1 Y3 B2 i  [4 g
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 m, T  B" c) j$ K% \: W) M$ l
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    + a6 ?8 c& [8 }9 o| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ) H6 ]1 f1 w3 q' f2 s
    2 e4 s! N- K. H. v 经典递归应用场景. \2 T5 F- _( P$ `  A) g/ O
    1. 文件系统遍历(目录树结构)
    * h3 M( i/ O2 Q7 b2. 快速排序/归并排序算法  Z* ?, a  B3 H
    3. 汉诺塔问题
    ) C  s* `' ~4 M4. 二叉树遍历(前序/中序/后序)! v$ N2 y8 \2 Y! M5 x" F8 t# }
    5. 生成所有可能的组合(回溯算法). R3 H/ c; u6 i' q" A8 d9 C- ^
    , y2 Q) _2 k, Z  b
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    9 小时前
  • 签到天数: 3227 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    * c% v, h( ?; T3 g$ Z我推理机的核心算法应该是二叉树遍历的变种。
    , Q5 a' K, Q9 J另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:0 o* @! m9 ?5 w
    Key Idea of Recursion2 n# v* @; X  l' Q$ a7 D

    5 f; z/ l4 E. y! B/ NA recursive function solves a problem by:  `- R% e3 i  D- M; t/ o7 e

    ; L% K0 l, ^+ y- Z: L. v/ w    Breaking the problem into smaller instances of the same problem.
    . q+ j" E8 K& o% j" h* H
    : s0 ~! V- |5 G% l    Solving the smallest instance directly (base case).$ W+ Z$ J+ x  h6 I

    $ v" s1 e9 c. e; ?    Combining the results of smaller instances to solve the larger problem.
    - ?( A9 j" z) h% \* d
    $ h1 Y# U! @7 k9 mComponents of a Recursive Function
    " h( n7 Q1 c6 c9 i7 E& b4 J- T& W
    + }% q5 U' Q+ O    Base Case:
    " W: D: l: i5 Y8 n, A, Q3 q+ ~9 R6 h! ^7 |% s
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    3 G- U& N8 p9 k; m  @% X. [8 h( x8 c
            It acts as the stopping condition to prevent infinite recursion.
    ; g; F1 R' w5 {& J- {% q) R
    4 x) b" j3 }, x5 m. X" i1 j        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    $ K* b( N; B- h* P) m9 D# ~, _* K
    % [" h: H! f9 y4 U# Y    Recursive Case:, P# t0 a; F. }9 ]$ x+ N! D( u4 w

    - i% b. h) y$ R) @        This is where the function calls itself with a smaller or simpler version of the problem.9 v& \* J7 b+ s- I

    3 m1 o3 h6 u9 V* `/ [7 L1 `6 J) K2 M        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).% b& c8 u) r! {* Z5 z

    ; a1 P3 S( u6 I/ R  AExample: Factorial Calculation  ]  N' ~1 d- T; m0 f7 L
    : v6 D  D: M* S2 W' E, a7 @, u7 Q( M! g
    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:/ U# u( v0 g& x) `) D
    # h% J# @" W1 {+ S* x1 `3 t
        Base case: 0! = 1
    8 f$ H; [" ^' s' ]4 b2 g
    5 U5 i! Q0 m; E0 ^' W& v, K    Recursive case: n! = n * (n-1)!
    ! w, n$ \. s4 i2 M" `2 D, u4 c, N0 i! Z! _
    Here’s how it looks in code (Python):4 I- a! M$ s( j4 M! b6 j% t+ P2 O
    python
    " |$ e: j8 c' f6 L& a
    1 r. v+ h% ~2 b- t) j9 G) Z
      R% E1 r3 j8 Y1 ^& v+ ^& h3 wdef factorial(n):! u8 F, {( ~0 K5 j
        # Base case5 T% r, J5 v2 N# C' r0 O6 @
        if n == 0:- g( }- z$ R9 L$ d
            return 1
    ! T3 E1 `  {% X    # Recursive case
    3 H& r% _0 X# R    else:
    - x! L$ |) O) |# P        return n * factorial(n - 1)7 a& c9 y/ Z: a' E
    , g6 N1 _; ]* @, b
    # Example usage
    % R' J7 [$ z+ J7 ]# N# \0 z. Q$ pprint(factorial(5))  # Output: 120
    * @  h$ C8 g: D) g
    " e( R6 i1 M. d: A$ b2 q% b5 kHow Recursion Works3 w- O' C: d' Q' F3 c* Z5 T9 L
    - W% {: P2 `" g/ B8 k$ O4 Y
        The function keeps calling itself with smaller inputs until it reaches the base case.7 _" S: i1 Y  Q! z! x- V
    3 k, U! m3 {! C  n  p
        Once the base case is reached, the function starts returning values back up the call stack.  F& F. v  Q/ z& d
    . ?8 h7 o& x$ b5 e( J, k/ N5 ]
        These returned values are combined to produce the final result.
    3 J: \" \# R6 q
    $ k+ M) a( P) R0 OFor factorial(5):4 i' v% h) x- P2 B) Q5 M$ T! S: r
    - e! r, `& J' j/ m1 O
    0 g+ w3 c& s! a) C. e9 j
    factorial(5) = 5 * factorial(4)
    " S( ]- I; k2 A( L- kfactorial(4) = 4 * factorial(3)
    8 f6 c' s0 m2 Z7 cfactorial(3) = 3 * factorial(2)$ _. V. a( a; C$ U" V2 X
    factorial(2) = 2 * factorial(1)& X4 B2 ]2 @' K8 n2 t
    factorial(1) = 1 * factorial(0)
    6 f) F/ \+ Y, P' s0 l& [# R0 kfactorial(0) = 1  # Base case
    5 S' @7 ~; R: ^4 ?  J/ x8 I. n1 H1 V$ v8 r  Q+ J$ ~" l& a% x
    Then, the results are combined:3 G  ?! z- H6 ]. M  v- b" ]$ g

    0 [: N, \# q: a$ k& E3 R3 z
      j$ H' `, H; M! J4 ifactorial(1) = 1 * 1 = 1) W$ C( R9 \" F9 h$ X5 d& _, I0 T
    factorial(2) = 2 * 1 = 24 |$ q% d. l( y8 d
    factorial(3) = 3 * 2 = 6
    $ R1 O" f* _( yfactorial(4) = 4 * 6 = 24
    4 S( o4 p' D- I! O4 J# n9 cfactorial(5) = 5 * 24 = 120) z, Y8 U) u: B. |9 w: S
    2 X  \6 \: p# A0 C! X$ v
    Advantages of Recursion- F' g: j0 @6 @/ w3 n1 Q

    # m& n& }6 T- O    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).+ B6 t# b5 f- q

    3 M1 M; _, T9 L( t0 i; O1 F    Readability: Recursive code can be more readable and concise compared to iterative solutions.7 h" {; C' N+ I9 C9 h* ?

    ' }* t  p2 U! _, s1 c$ TDisadvantages of Recursion2 @+ O5 U3 s: T& H

    & g/ |& c9 W; [( ]; a3 D    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.
    9 I/ W8 _6 g! H' u9 [  m- H& n& k( @5 O
    7 L( S, B3 c, Y  w+ s    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    1 p) \0 p) f4 R. D% I1 Y# H+ r& @3 s( q3 ?
    When to Use Recursion
    ( u5 [) }; B* W/ P! w4 L3 D9 s% C$ {. w3 P
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).* d: Q" d, |/ g9 D3 G
    " z4 k; o" ^0 I) h. N& y
        Problems with a clear base case and recursive case.
    ) Z; I4 Y0 [, Q5 b4 H; K
    0 G, i" Z+ s7 F3 Q& u$ iExample: Fibonacci Sequence
    - d/ a/ B) K4 C* p
    & N: N- e1 K6 t+ ^8 T* K( a. f3 OThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:: s$ H% x8 V, C& D0 O
    4 P5 `) ^( e' b. q4 p) ^
        Base case: fib(0) = 0, fib(1) = 1' u, D/ c" J) r' x7 p8 ~

    ' J; U) M2 w, b5 H% ]: M: a7 N7 q    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ) \' z" u  T7 F5 }( ]
    9 e$ }3 r* [, ~2 Q9 }python) B1 D1 B1 z& y2 z; B
    0 F3 R$ t* g* z9 R( k; @, i

    4 Z6 P6 }% W# S% K$ N. odef fibonacci(n):! E4 \  n9 ?, P2 Z
        # Base cases
    - r' q; b  A" U% [$ u; R% \0 ^    if n == 0:
    & D1 i* w1 U) X7 L8 _& ^, \: }( n        return 0
    " G( b* g: N5 e0 m2 l. k    elif n == 1:# H# o  \  A) K" x: y( ^8 Y- t
            return 17 T0 G" n- L. N: m9 G6 b! t
        # Recursive case
    # f3 V% B" L& J, J: R    else:
    $ d% u5 j4 }' H3 W7 L        return fibonacci(n - 1) + fibonacci(n - 2)! j  c1 M7 I; \
    / c6 ~3 h' A6 S" I1 k
    # Example usage/ r4 `' H; T2 o  Z6 l
    print(fibonacci(6))  # Output: 8
    ' d# Y+ J/ r6 u* @0 d  A' l
    6 \) C" i! w$ R0 o# j8 [Tail Recursion
    / g7 f5 G& _4 k: V6 h. Q3 x
    % z8 N; H- a# M4 g- x7 X. eTail 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).( c2 z, C1 D- y- D5 t3 G0 g) x
    9 @; i; c) a3 ]# Y
    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-4-30 16:18 , Processed in 0.056947 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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