设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    4 g4 b& |9 {  c1 n$ r, F6 q9 ?+ H
    " ?( n2 t* q$ @$ Q0 {# U5 Z解释的不错
    0 B, c2 m! g* c: M# i0 ~3 c3 G  s0 t
    " w2 t6 B5 X% v  N  g/ C( \递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ; {2 C( k: i; A# U$ E+ {0 t* {! Y3 V
      O4 g3 l1 g) s, ] 关键要素
    8 E' w. W. Z0 a, k& v, Y" w, j, ~1. **基线条件(Base Case)**
    9 M6 h# p4 ?0 W0 R/ W   - 递归终止的条件,防止无限循环
    ) O" q9 v9 t2 P6 ?1 i9 W   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    + ~  l; H& p: r
    ; [1 e! D) A! b. h2. **递归条件(Recursive Case)**
    - |: X0 D; U/ [   - 将原问题分解为更小的子问题
    " T1 p. `4 s. a/ }3 J0 j   - 例如:n! = n × (n-1)!
    6 t  J0 L. l5 L8 C: E1 W0 B5 c, V' M0 F  ]) L5 I
    经典示例:计算阶乘
    8 X, Q! R# ]/ \5 epython
    & ~; F9 k' z2 M  |& Kdef factorial(n):. F3 {. S+ N% z5 t: t: P7 @
        if n == 0:        # 基线条件3 O' t+ s; M! {0 U
            return 15 w( n3 M; z3 l
        else:             # 递归条件4 c) M$ H' O$ A
            return n * factorial(n-1)" q# X. b" r: ]  r& X  @
    执行过程(以计算 3! 为例):
    + A' w/ m0 I( \/ o% W: W) `factorial(3)1 Z' C$ j$ |% B/ J! {
    3 * factorial(2)
    7 l! g4 G* D% |# `/ l9 L) |3 * (2 * factorial(1))
    : c0 ~+ e* r) N& S* m3 * (2 * (1 * factorial(0)))0 p- {* y  k  f- I- P1 J+ r/ A3 L  C3 o
    3 * (2 * (1 * 1)) = 6
    . z/ @" N# `; C) D
    : c7 p& T, w7 [% F+ q% j5 W 递归思维要点: _4 t3 p3 x4 t; S# V7 m7 m, V
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑) z( q* P4 v7 Y# _) C* x& b4 a% |0 S
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)/ Y' A; D* _7 S! R4 D
    3. **递推过程**:不断向下分解问题(递)
    9 a- x! }4 v( x1 _, H5 ]! S4. **回溯过程**:组合子问题结果返回(归)
    4 I, W5 w" Z  f4 p! S+ C/ `, Y! Z' b. X& b
    注意事项
    ) F6 N1 a1 M4 I3 S) \0 D必须要有终止条件1 Z9 E; \4 Q3 u. R! i
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)7 J4 @5 _2 _' r- Z- ^! i. n& N
    某些问题用递归更直观(如树遍历),但效率可能不如迭代6 J, @. P5 \' ]0 s8 M
    尾递归优化可以提升效率(但Python不支持)
    : f. g) G  H! M" \$ e! i* S( r% ^: a: y
    递归 vs 迭代
    # }# v; \3 u/ }! ^9 o3 q|          | 递归                          | 迭代               |
    7 x, C8 x# W9 Q9 L6 C4 h|----------|-----------------------------|------------------|# ^, x& t. p; `
    | 实现方式    | 函数自调用                        | 循环结构            |
      D5 Y. V; q3 I" T' \; _7 R# G| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |4 s2 V: b* c9 w  i: D
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ( ]7 A1 E3 h* l7 s  H4 K6 `| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    0 s6 C6 D( `$ a# B
    3 O. {% b, c, i8 i% r, b 经典递归应用场景
    ' i6 ~4 k* B" Y6 h1. 文件系统遍历(目录树结构)* f- j/ t, U1 i7 |; Q; r0 y
    2. 快速排序/归并排序算法
    . F4 v. v! @7 j3. 汉诺塔问题- E6 N9 }: K" A& J& }: i$ ~: s7 l
    4. 二叉树遍历(前序/中序/后序)! {6 S3 y" C4 [
    5. 生成所有可能的组合(回溯算法)
    - t2 i  M" x- P2 N: @/ g
    & l9 ]' N1 Q0 ?试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,1 ?* v0 d8 a2 C8 ^
    我推理机的核心算法应该是二叉树遍历的变种。) {4 }$ f1 F; E9 C( ]7 B; ?, u
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:* _& H2 R2 W2 A- r) V
    Key Idea of Recursion
    / p, a/ e$ x* k2 o8 \- f- S  d4 Q3 ]% s0 n' c* b% Y0 G; X
    A recursive function solves a problem by:1 k2 x7 e: }" H' Y% z! W/ @$ q

    6 f# M( h! b4 B$ j    Breaking the problem into smaller instances of the same problem.
    # r9 M' @8 ~; \, |) P& H0 H) Q, _2 S. A! Y* g! r
        Solving the smallest instance directly (base case).
    * t6 b7 ~) O( v5 i6 v1 x' X8 f; G0 L' u
        Combining the results of smaller instances to solve the larger problem.
    , ^( O% W; U3 A
    + r0 Y( ?: T  p, NComponents of a Recursive Function: t- x2 l6 b9 N( x$ G8 \/ B

    # P5 z8 O* F& P! I  Q    Base Case:( S  Q% u& n# z( ~5 z0 m

    - f# @( y2 K/ _        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    . Y6 h0 T# a. j' d/ i' h
    . x  U: B) g$ H1 T1 o2 @        It acts as the stopping condition to prevent infinite recursion.
    5 u3 x2 h& p& |* G# A& m0 j8 m
    ; h* |) v6 @  a" v0 E        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ b8 @; ~2 B( }' U. t, [
      U9 K2 m) ?# r+ H
        Recursive Case:
    # h' D# Y' F7 D& i+ h3 U( ]. o' {3 O7 ?4 H& W9 h
            This is where the function calls itself with a smaller or simpler version of the problem.
    * u( C4 J5 z) @, \9 v% o' Y, _
    8 q% {! ?4 ^' K+ D  K        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    / w  M% G% l- h; _& ]! K2 h; W6 c) q( V1 X  v4 g* g1 b
    Example: Factorial Calculation
    3 j6 ]# s3 V6 u+ U. A7 x$ i9 F) x. z$ c# 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:
    6 h# |" N4 f' U) }1 k9 G3 \5 U1 n. h5 S7 b0 R: ?6 Y
        Base case: 0! = 1
    9 b, y$ ?0 j/ @9 |4 [! D5 x* G! m6 n4 o' ]! z+ U7 N0 e% i4 V
        Recursive case: n! = n * (n-1)!! [0 p8 b& z8 K
    & |$ o# N/ M  L- D4 w
    Here’s how it looks in code (Python):
    8 [3 ]9 ~9 O& @  apython
    . U) X7 P8 T  U/ K1 w- w3 s0 f% |4 ~) N  u% x
    ; ~% ?! _9 r; S, {" L: s1 G' H
    def factorial(n):9 O* c7 G) A# i
        # Base case
    ) b0 H& ]1 y* e$ l( R    if n == 0:
    % N6 z1 ?; {- K9 z" N8 F6 a        return 1
    * n3 I- r$ ^; |0 Q. g6 U    # Recursive case
    8 S+ h7 V! Y+ G( D* @    else:0 k4 t7 d  \0 q/ E3 Q  }6 N% I
            return n * factorial(n - 1)9 @6 |* s& k- j, U
    ) A! k' w; p$ ]
    # Example usage4 r7 F8 Z' i/ C! p' T+ y) @
    print(factorial(5))  # Output: 1203 f$ B' V. U% p, N* r5 O* g
    . r0 T+ W; M& n, S
    How Recursion Works) y* {% U8 Q$ p& S, G( W/ V4 A

    $ x4 [: m4 a7 E6 x+ ~    The function keeps calling itself with smaller inputs until it reaches the base case.
    9 C" u- U8 h) l6 g: A" N7 X1 t# o
    % j! [! h6 ^- O( n* m* j/ z4 z    Once the base case is reached, the function starts returning values back up the call stack.' N- |, ^7 I9 Z, Z- g+ t
    8 e3 a; x8 K# C# W. U; e4 s! c
        These returned values are combined to produce the final result.8 l, n$ k0 C1 |( m4 t
    , P4 h$ s! j/ B
    For factorial(5):
    # ^, m$ o; q- Q$ M- R' I1 f' ^& a9 o
    % C1 t- t- h& F7 s( o- {( ~6 _6 _% U
    factorial(5) = 5 * factorial(4)
    6 k- K! |* O4 ^/ z% r6 [* vfactorial(4) = 4 * factorial(3)' t$ \. E" w  _; |$ }+ F) \6 x' F6 J$ E
    factorial(3) = 3 * factorial(2)
    9 @1 O) X+ h0 q8 bfactorial(2) = 2 * factorial(1)) ]# p2 v- ^2 k3 Z: V0 X9 [! m
    factorial(1) = 1 * factorial(0); P' M! n$ g3 P2 t/ ]) o
    factorial(0) = 1  # Base case
    ; b; n" F6 C8 e) A0 e
    * N' |) q) p* `) o* o8 [9 B0 lThen, the results are combined:
    ( M8 H/ b& E+ ~  S$ X( t1 c4 [$ j; p5 U  f: N. T4 C& f* M
    7 b& X8 ^1 x$ g$ U, V
    factorial(1) = 1 * 1 = 1
    5 {+ H5 l' w) V9 I) d2 Ofactorial(2) = 2 * 1 = 2
    6 n8 n8 C2 P( a3 y& B/ ~factorial(3) = 3 * 2 = 64 O3 P: w4 p* Q
    factorial(4) = 4 * 6 = 24
    0 \  e% l* c+ V+ p7 D9 F; Nfactorial(5) = 5 * 24 = 120
    ! X  p7 e5 l8 d  D0 \; i; Z% i+ ^. z8 v& u) e7 ~% B
    Advantages of Recursion* q& H& O7 I1 N0 O5 w6 |

    6 N, @6 \9 D2 j( w  M6 b    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)., G1 D3 H- O) {9 h
    + I# }& r) o" F  _1 g! {0 n7 C/ F
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    % I  `% H( A9 T1 r/ ]# I% c& l5 W" Y1 x+ U! H) b: v% V
    Disadvantages of Recursion% I$ a4 O  J+ K; ?; o
    $ L% c% D1 b! j
        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.' e7 v* p9 C5 A" U# D
    * j4 v* J$ X# ?" {# u9 K
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    % X1 L9 F: l% n7 y/ ~1 S" O% V$ ]" ^' K# f: c' e
    When to Use Recursion
    0 n- m- f* C6 \$ t7 ~) m+ c3 k( I9 A- G; C
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)., o3 H# p7 o& j" h2 b. y1 E
    6 p, x- b+ t( D& S
        Problems with a clear base case and recursive case., ]9 O: i& D  G+ H% \+ ~
    ( y5 M1 L2 \0 X6 R! A' T
    Example: Fibonacci Sequence
    1 I4 e% ]% }7 i2 t% u9 d' H/ R0 F
    6 c* I  W6 h& \' W3 Z3 kThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    8 d: V& g- |. Z# R
    / x5 h9 B+ m/ J& P* n  A    Base case: fib(0) = 0, fib(1) = 1
    0 O" O$ M3 L4 _! ?4 @9 j9 i( l, V- |$ A8 {: j( N
        Recursive case: fib(n) = fib(n-1) + fib(n-2)/ o3 r* y9 c/ t6 N

    " W1 l% Z; U  h% r1 b2 P$ `python8 M5 V6 @+ i; z9 C& L

    " w3 L/ T7 U) a5 J5 T* G3 e) r, y
    # S; a. j. A+ b2 R# ~def fibonacci(n):5 Q( y' S; e: Y
        # Base cases7 B! `8 J4 T* a' r# z* G5 L
        if n == 0:
    8 \# t- c3 u- T* J( J! M& d  I        return 0
    4 J( U6 v& Q' ?+ ~8 B; G$ [: v    elif n == 1:
    9 G" U6 ~9 \, ?% F        return 1
    , s: I6 Y7 E, g$ {' Y    # Recursive case4 C3 T! D) K$ M  \/ W9 B
        else:
    4 B" i4 u7 @  V1 \        return fibonacci(n - 1) + fibonacci(n - 2); [1 v' [' s/ S. T! O6 H
    9 X$ c. M; q3 {( L6 z" M0 F
    # Example usage+ h( K* p: k# v4 ]% }- ?
    print(fibonacci(6))  # Output: 8. S- z6 h2 Q) Q  U; \4 t
    ! y/ U( [  @7 f# F
    Tail Recursion- K* }; H4 p/ Y1 P; i
    & N* Q  W3 L$ ~; [
    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)., j. {/ x4 ?* [; b( |, ?% A, }
    2 t2 O, H+ U4 A5 D
    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-5-27 17:47 , Processed in 0.057277 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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