设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * K/ _0 z" B8 c

    2 G; W" {8 |, c% J解释的不错
    5 p+ z6 a! s% F6 U. e9 x
    3 B, W6 N3 n: O- ^7 ]+ W4 B4 Y" l递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。6 K% m; V* h& W$ o

    " z2 y. a# a1 W 关键要素6 R( ~2 h$ c+ q0 I% C
    1. **基线条件(Base Case)**9 N. \' F% h3 O7 c3 [
       - 递归终止的条件,防止无限循环: y+ n1 F& B" |2 s; C
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 Y3 j3 L: }4 T9 A) z# @

    ; E, b$ [) j! ?2. **递归条件(Recursive Case)**& o6 o0 }' M+ e/ z$ Y
       - 将原问题分解为更小的子问题# z6 c# h/ O  [. i& b  V# P
       - 例如:n! = n × (n-1)!
    $ ~" H7 q6 p( u0 o8 G
    7 f7 b: D2 B2 D: y. W: e" t 经典示例:计算阶乘
    ! G' o9 C5 E% j4 G# ]python
    : _7 Y; M7 y/ `) zdef factorial(n):9 P0 t7 q9 ~  g) M0 T% K
        if n == 0:        # 基线条件
    " N6 H; o# Y3 ^, [% U8 a) m3 P0 s  H        return 1
    & r9 Y* G) z- [! y1 X0 B    else:             # 递归条件
    * s. O0 G! B* A$ t/ l        return n * factorial(n-1)/ C1 `! i( q" X* r. a
    执行过程(以计算 3! 为例):
    + O& |5 J+ M6 T( L1 V1 zfactorial(3)
    8 z! ^9 u1 k, b# V4 d; ~7 P3 * factorial(2)# U& U- l. D  P5 M
    3 * (2 * factorial(1))+ q+ ~% ~( M0 F) K
    3 * (2 * (1 * factorial(0)))# T2 h* {! }6 W# A* H
    3 * (2 * (1 * 1)) = 6
    ! P6 y$ A3 k( q& l* m, s1 O
    5 X! @* A- N3 g8 M4 j 递归思维要点
    8 E) N, x3 j" Y* _8 L" z' l2 M1. **信任递归**:假设子问题已经解决,专注当前层逻辑. i2 c) W, {, h* Q8 d3 p
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    3 P5 _- k% _: b3. **递推过程**:不断向下分解问题(递)9 W" ]3 u" _4 Q7 s$ ^8 K9 l+ ?
    4. **回溯过程**:组合子问题结果返回(归)
    ( Z. ~) u6 V  ?1 X
    7 _3 `  b# c! o. U) l" R" ~1 [7 c 注意事项3 d- {  E2 v1 n
    必须要有终止条件, g% ^; D( o3 M6 l
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ' R: I5 E7 s8 ^* Y  I某些问题用递归更直观(如树遍历),但效率可能不如迭代0 `- c" ~! d& `+ y3 e
    尾递归优化可以提升效率(但Python不支持)- j3 B  g) j8 E" s; B/ i

    ! V+ j9 n. o; y( R8 z. N 递归 vs 迭代
    ( M# I+ S' A# ?9 O5 a1 t, h8 ]|          | 递归                          | 迭代               |
    ' K  ]2 Y5 {. [4 s|----------|-----------------------------|------------------|; N% W8 Q$ O  P8 t  \
    | 实现方式    | 函数自调用                        | 循环结构            |4 I3 v! J% D# j  k6 g% }8 s
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    " u* x9 L+ v' t| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 n5 b7 d: n: o' }" M; c. T) `| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |# V* n: O3 L& G4 ?3 D9 S
      W, t( L6 a! c( u# b2 {
    经典递归应用场景7 I+ b- u5 |% C$ G# @) n' l( |
    1. 文件系统遍历(目录树结构)1 l" V( J) U, t" J9 V+ |7 `, Z6 N
    2. 快速排序/归并排序算法7 i8 a* ^% R) ~% @3 o
    3. 汉诺塔问题
    ; _3 X: s+ A3 Z  ?9 D/ W# _4. 二叉树遍历(前序/中序/后序)5 e2 S5 P! j, f9 f# V, l" }
    5. 生成所有可能的组合(回溯算法)
    3 ?  l- J- O4 ~! J# ^" s% e5 P/ k; y- J, W8 W2 c* N+ T, W
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
      @0 A- M8 n& ?' o. z" i我推理机的核心算法应该是二叉树遍历的变种。1 g2 J$ w  Y7 E; z; O# z
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 Y3 ~" L6 M9 M. M6 \6 \
    Key Idea of Recursion
    * T  @1 h9 x$ X1 H# c: o% C1 D8 F$ ?2 V; I! z
    A recursive function solves a problem by:2 k3 j0 z" s9 S( D4 Q* a+ a4 s

    # H; o  u) a) Z( ^; H! O$ i) b2 i    Breaking the problem into smaller instances of the same problem.
    ( I) l& h8 Z% u) C* T/ ~+ r( T9 V2 e, h- y" u. u
        Solving the smallest instance directly (base case).
    $ i% f  @4 v$ @3 {) e$ |. G1 p' y* L
        Combining the results of smaller instances to solve the larger problem.
    $ v1 I: I. E( q5 f: o/ C: z7 f8 {" B6 \$ Z
    Components of a Recursive Function
    " W2 i6 r6 m' a2 K  L, V
    8 r% m' }# N; k1 R    Base Case:
    ! g* n  P- \# @1 j* M6 f# h
    - v4 I6 A  l& h& S% A4 w: P# x        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    1 ^+ S9 B4 n! a. l% n5 w8 Q4 |5 c) L! v% H% \! S6 O
            It acts as the stopping condition to prevent infinite recursion.
    - d7 J/ k/ O; _4 h: t( ?9 i6 ^- k" O( s+ g3 R$ s9 P
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    , {* }$ q) _* A& \& c- l3 Z6 @! |2 V6 k9 H! w& j, F
        Recursive Case:% ~$ S$ A) s9 k1 J: q% f0 Z

    2 ~% ?6 j" |, l        This is where the function calls itself with a smaller or simpler version of the problem.  k# Q+ V& t' M3 H; C
    4 N. C! C! K, F& y$ A7 o* m
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    3 a. t) {' i" H% ?8 Z
    " n$ c/ O4 g1 O/ N. @Example: Factorial Calculation! z: B' `+ v- _: d% j3 _
    $ i8 h, a2 k5 p1 ^# M4 q  l
    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:1 R4 X6 S% k& g0 n  C

    6 m/ _& ]8 ^. v. ^* y% s    Base case: 0! = 1! d! Z3 L# F; |1 s: W$ O

    , g) T9 m) D7 q" I* P+ o/ }% \% P$ |    Recursive case: n! = n * (n-1)!
    , R  |1 v& V3 A! H* j. @6 I7 D8 Q( a# R6 T* W1 k
    Here’s how it looks in code (Python):
    + W- M( i# F; K" Lpython
    ; X+ I/ k( F8 G) D
    ( Y* i  c( u: ]' r0 Q1 m7 P, q: z" H8 K* P+ y
    def factorial(n):
    . L3 e3 l! t' X9 e9 H# i    # Base case
    / K" X# ^6 V7 u9 n* t1 ~    if n == 0:: e9 A! l' D+ w8 K4 u
            return 12 c- h: l- K" ]" A$ ]+ ]- q( F3 o
        # Recursive case- d2 g% ~7 `+ {
        else:- L/ S- H/ k: A8 a+ l. @+ v# j& r
            return n * factorial(n - 1)
    / ^* l- \# `% v% ?) e. v# U  z4 }: B- A5 @2 A* x3 j
    # Example usage( Y, n' y: f# f) \
    print(factorial(5))  # Output: 120
    2 Z2 V& z$ a6 o
    % G1 k3 W# L  N/ z: X& A% {% `! HHow Recursion Works: G, e9 A  g- W' P5 w
    # h& j4 J: Y# e$ \
        The function keeps calling itself with smaller inputs until it reaches the base case.+ \( i6 \* ^& u+ I, X
    & k% o) }. r/ F" @7 b6 S0 m
        Once the base case is reached, the function starts returning values back up the call stack.
    ; [( d' I. q1 I7 k& o
    # e( _8 i! C& R    These returned values are combined to produce the final result.
    / m8 v/ ?, w: r6 I8 F: l  ~: L# V) z
    For factorial(5):# s  b6 f! y2 v/ x5 A

    , Z& j& E& O  n; S1 B1 l4 p
    $ Y# W; q( }. I) }factorial(5) = 5 * factorial(4)6 {5 j$ l' C: v, M; B6 I
    factorial(4) = 4 * factorial(3)
    . s  D+ y6 _, O; I4 N6 `0 u+ R4 S: pfactorial(3) = 3 * factorial(2)
    ) t, S! j4 c  m8 ?& ufactorial(2) = 2 * factorial(1)
    + w) {8 F+ j) u7 j& Vfactorial(1) = 1 * factorial(0)
    ; Z* G7 R. o2 ]) Ofactorial(0) = 1  # Base case
    ) w( V6 j+ x- l0 }& Z/ G3 T  n9 |0 h
    ; p+ ]: {/ s+ K2 ~- N" ?Then, the results are combined:
    & i* C. g& D8 G6 S/ r  s2 k- Y1 v% |' e, _' z3 |: d/ n0 h

    2 @/ ^' P  [3 k4 [/ Z5 n4 Yfactorial(1) = 1 * 1 = 15 |/ J3 x  a- e) K5 B# S! U
    factorial(2) = 2 * 1 = 28 U: r& b4 B6 _! `# }
    factorial(3) = 3 * 2 = 62 H& ^' c6 \) ]/ d4 Y
    factorial(4) = 4 * 6 = 24
    4 \1 U1 H9 ]' t0 @. K5 Yfactorial(5) = 5 * 24 = 1203 T" ]$ c5 b; `# \! ]2 N* ?9 R$ A

    " S: o8 A$ k. i: u& n$ E% gAdvantages of Recursion4 a6 S9 @, W+ L, ]) G
    ! Q% P/ k& l- ]9 e0 v+ h- B- H
        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).4 ?; w( {, ^# C9 O

    1 J; \! i) @4 X  c7 O5 ]: E    Readability: Recursive code can be more readable and concise compared to iterative solutions.4 \  E2 j; F7 T' w  y" |

    ( u4 \. }3 p' @2 T. [& ODisadvantages of Recursion
    6 |6 Y% Y/ [: a" y, X9 o: P6 ?4 |. s" M2 \+ _, V" E
        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.- k+ ]& |" ~; F, _' }; E
    8 n' @* O. j0 d) w
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).6 a1 A7 t3 S  V! G  [6 S; D
    ( X4 F1 `$ c; ~( H# g9 f- t
    When to Use Recursion* a; v8 S  E0 ~: \- t

    3 ?1 N7 `2 G8 n% q0 u  q# E% l* c0 {    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)." n$ \; b* `% \1 {
    / ~. {) }5 ?6 b' q3 E( D7 Q% S
        Problems with a clear base case and recursive case.: ~; s, _3 H+ n; a  T7 ?
    " R3 V, c- w( l; N0 X6 S0 @
    Example: Fibonacci Sequence; O- G5 k0 y1 g4 u7 E7 c7 I

    7 g, j4 ?( Y# Q8 xThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    : P; B/ m- B: Z0 h/ g4 p" p
    6 J9 W3 Q: `! }. N    Base case: fib(0) = 0, fib(1) = 1. b* \0 ~. x5 s% E/ O
    ( M" K# z+ H  s( j$ C2 a. t
        Recursive case: fib(n) = fib(n-1) + fib(n-2)2 o$ [# j: J4 z( O, k* w6 s

    + T, j( f2 F: f/ e! s6 Opython1 j& M  \) l9 n' ~. m  K

    / L7 I6 J! y$ G) Z( J# e" m6 e
    def fibonacci(n):4 j; Z% g. G4 k
        # Base cases; d- g) W# a5 C5 ^7 I* Z
        if n == 0:- i) C9 Z. `, c% A& ]$ `
            return 0) j! r- E) a3 b$ S2 `
        elif n == 1:* M! r- i5 A0 _* v9 A1 S# S+ _* T
            return 1; d7 Q8 u: }# \) T0 U* I8 r
        # Recursive case4 X+ X/ ]: r5 ]- a9 r2 Y
        else:2 k( v, R$ C9 S# s# u
            return fibonacci(n - 1) + fibonacci(n - 2)% m% |# K8 m4 m- y0 v4 w, {

    - Q/ n' a2 F" b2 o# Example usage2 i0 w" V, \& @& m$ i4 M( c8 h
    print(fibonacci(6))  # Output: 89 a, S( m% s/ [5 g$ {  R" r. m( p

    1 E. E1 l0 S# b; S2 g/ n7 a+ u8 PTail Recursion
    ) f  ^7 W" p- x" H$ R( [1 W9 C0 Z0 v5 k4 \; B9 x
    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)./ R$ W5 C. S1 X6 z: E9 z# q8 k

    . h5 d# Q3 Z4 i* ^  ~7 U8 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-3-16 19:55 , Processed in 0.064233 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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