设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    6 f' ~7 G' `/ m
    " p: _+ j* P- [* J3 |3 e解释的不错
    - F- S  j' @$ ~  g& G( h# w# A. J* C. x+ T' Y
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。+ p. `9 s! [% Y& A% r

      ~8 d( ?- j" g* [& `8 u# | 关键要素0 T, l3 D+ Y' A$ q0 E4 S. [3 S
    1. **基线条件(Base Case)**) h/ S+ T& K! X; Q+ F# L
       - 递归终止的条件,防止无限循环
    / C" j  B" `& u* P3 ~4 _   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ) h! i4 m$ y. \9 w4 `3 _% H% }! E' J
    2. **递归条件(Recursive Case)**. j9 a( Z3 w6 b& X& h
       - 将原问题分解为更小的子问题1 h' O- C" U- w* Y
       - 例如:n! = n × (n-1)!" @# V* |* M& A1 d: d/ N$ X: Z

    - w7 k5 M* P+ ]$ R 经典示例:计算阶乘
    8 W! `# }" j; T+ d4 G1 Fpython, P2 Q! d6 G" k9 o
    def factorial(n):* G3 D6 f# C: j  N1 J  {4 u; u
        if n == 0:        # 基线条件& V  V7 B0 _9 }2 }
            return 1' Y: ?, Z5 {/ Y, e* I
        else:             # 递归条件
    * @: p  }1 z# H. J4 t/ c# l7 m        return n * factorial(n-1)
    ; g) |2 y' N- z7 s8 L& d执行过程(以计算 3! 为例):6 ^- ?4 f  ?% E1 _5 y+ ?
    factorial(3)
    + H  u/ B# _( ]6 i& J3 * factorial(2)) m% U' K8 }2 m4 g0 o. d* ~& S
    3 * (2 * factorial(1))
    , T% y- V! G7 c6 S3 * (2 * (1 * factorial(0)))
    2 h: I# o1 X4 Y/ h: z8 I3 * (2 * (1 * 1)) = 60 A& Z9 X0 P/ R8 b$ ^

    8 f( q, K" o# ^3 j$ x; `* G" b 递归思维要点6 M/ J: g( P0 h# s
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑  r. f0 }# z* o& }% g2 z
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)3 I. w( }" n8 `) a& ~" e
    3. **递推过程**:不断向下分解问题(递)9 G# ~" n! i9 N1 \
    4. **回溯过程**:组合子问题结果返回(归)
    # L: D$ i# }5 @) t) @" ~1 X3 C, L8 n
    注意事项+ J, j( A7 n( t& a
    必须要有终止条件7 W1 r3 R$ Z5 Y- O5 p) ^3 }% H
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    6 ~4 ^0 p0 j5 s某些问题用递归更直观(如树遍历),但效率可能不如迭代
    & w9 z! ]* D( B, s% D尾递归优化可以提升效率(但Python不支持)
    : k6 `: f+ w4 a+ }- u( M  y' l; f5 _7 v: R# E+ I3 E/ r
    递归 vs 迭代
    ' ?! E, t% @- r5 s7 G6 x|          | 递归                          | 迭代               |8 i2 @4 ^0 H+ q! W1 s; C0 t
    |----------|-----------------------------|------------------|
    ( t8 O1 ^* d& P4 n# `2 E% j4 n4 L| 实现方式    | 函数自调用                        | 循环结构            |
    / b2 t( k0 z' g$ i) w/ M| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |8 m5 h) l1 d% E- F* ^
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |, F5 P# f5 J$ b$ L
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    8 ^- D+ f5 b, l
    ( F1 m9 U" G( D0 F/ Z 经典递归应用场景
    : R$ {# L$ b2 p0 v7 S) N; w1. 文件系统遍历(目录树结构)
    ! ]! v; ?* [1 r1 N, Q2 ~2. 快速排序/归并排序算法( y7 b' o0 y- H4 R) F3 V
    3. 汉诺塔问题
    # f+ v1 o7 G' s2 c, X8 t* ]3 q4. 二叉树遍历(前序/中序/后序)# g# P/ K* c$ t5 t3 N: Z
    5. 生成所有可能的组合(回溯算法)# L. ~) P& N. C$ s. k& p

    & a' u7 z- P' W: G试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ) s: x1 F3 V* n# Q  U0 A我推理机的核心算法应该是二叉树遍历的变种。
    * E6 p5 q# F+ Z( f' y, C, 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: E# y  o4 y' x  Q+ z
    Key Idea of Recursion
    0 k6 ~6 G/ f% o/ k/ S" Z. S" ~  }( Z2 C6 I( G
    A recursive function solves a problem by:
    ' y" w( j* V  C/ y
    & j" b6 T7 X4 `    Breaking the problem into smaller instances of the same problem." \- X4 ^- Z0 v0 c& O
    * b1 Q9 B& d* z3 `
        Solving the smallest instance directly (base case).
    & Q1 o% I- P; n( y6 _# o( f
    . c) [: y0 W6 w! S% G& W    Combining the results of smaller instances to solve the larger problem.
    # U2 g! f# B, w+ D% S7 a
    7 Q, K$ D( A9 D" |5 w/ C& EComponents of a Recursive Function
    ( L# w5 X3 @3 ]9 x
    + P' [7 t) y+ I9 }. l    Base Case:
    + `* s0 Z% p: {- O
    ( r+ T4 ]  i+ u( {        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.+ x& k$ T% ~$ b9 z+ X2 a
    . E% ]  v0 p2 a/ y: h
            It acts as the stopping condition to prevent infinite recursion.
    1 }& s# \( g: `2 A% i; K1 N) l1 @, z6 m6 t
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    + r% Y" D. D8 O, O: ]6 I7 {- b4 @6 i& k" W, G/ t* r6 j
        Recursive Case:' F* q# q8 T7 `: h& s: z

    4 i9 p/ ?3 W# M0 x0 S        This is where the function calls itself with a smaller or simpler version of the problem., Z) X" E" y0 E4 l
    , {# Z9 m! d) x( {; C- O
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).9 B% L/ r: T+ A6 n2 t1 S. F# `8 U. i
    $ p. ^; Y+ ?/ a
    Example: Factorial Calculation
    7 m# K( [! d! ]9 |( w
    - e  w& b8 J( F8 V6 gThe 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:7 q+ q. X$ m  @, Z
    ! _, I! Z. |, U9 b- W5 k5 Y0 g4 Z
        Base case: 0! = 1
    9 p* N! \$ g: C/ b( U5 g4 i
    ' o; a6 j8 g% t0 T3 c    Recursive case: n! = n * (n-1)!
      [7 I! s1 ~( E  _0 |, W$ p
    # a: [1 ~" V2 `4 I; OHere’s how it looks in code (Python):, o3 j0 A: V* H
    python
    / d% [+ D( M' \, c, _' S7 ~* v  O) a7 K
    / P7 @7 A" c$ h
    def factorial(n):( Y& K- a5 Z6 O
        # Base case7 w- |% a) u9 ~% y+ y8 t
        if n == 0:: _3 b) [6 X8 Q+ N* q7 q9 Y( I
            return 19 B1 M# T$ H! B1 h' c- X
        # Recursive case4 u+ f* R* y# A, p! j, t
        else:
    + D3 z2 _5 \2 `7 F' V, ^" A/ o4 T        return n * factorial(n - 1)
    8 A/ S1 X: D% v( }$ k1 r# T& n% T; w/ w1 s, ~
    # Example usage
    . K( B8 {$ S  I" `7 zprint(factorial(5))  # Output: 120+ O# W& @0 S; O) B" P5 ~! P! w
    - E4 q/ H  ]+ H8 b$ Z
    How Recursion Works
    ' g% E9 \( x: j- Y# A7 R7 U, L2 L4 R# o# a
        The function keeps calling itself with smaller inputs until it reaches the base case.& ?; ^9 K4 ^2 a; K1 K

    / ~  q+ a0 m" x7 ?+ b. [# G    Once the base case is reached, the function starts returning values back up the call stack.
    0 `7 }+ x8 u$ O& R6 Q3 [2 X. O/ D& D2 R
        These returned values are combined to produce the final result.! o- Y6 x$ R- R% X5 _1 O
    1 o4 u9 \5 v1 ?2 T2 d
    For factorial(5):
    9 C4 P  u  j7 M  b- r0 `* e
    3 E# k0 |1 w( ^
    + D6 Y% i8 ?( Q( p+ B2 E/ S% Gfactorial(5) = 5 * factorial(4)/ |+ Y& d4 a& I& `: z
    factorial(4) = 4 * factorial(3)
    6 X+ A0 p& k' tfactorial(3) = 3 * factorial(2)
    0 o* x4 n( j/ a% ]  ^( Ofactorial(2) = 2 * factorial(1)1 e9 M: w7 F! c, j, a3 e
    factorial(1) = 1 * factorial(0)6 @. z- J4 z# P7 t7 [" ^  k
    factorial(0) = 1  # Base case6 l) L1 k, L0 h

    1 \" j7 H2 t" ]  N+ H0 y7 z' DThen, the results are combined:* _8 [2 f, F) k5 K) x3 @/ V+ i' t6 {
    0 _8 e7 F1 `6 y( W; w
    " H7 `9 Y" }) u+ F0 e! U- S- a
    factorial(1) = 1 * 1 = 1
    ' O4 m) t0 a$ c( yfactorial(2) = 2 * 1 = 2
    4 e  T; d2 b( O# ~* ?+ |+ w# @factorial(3) = 3 * 2 = 6
    % S( |( P8 d; B8 Lfactorial(4) = 4 * 6 = 24; P4 p. f8 G3 A& E2 r: {  t! _+ l" b
    factorial(5) = 5 * 24 = 120
    2 i; J+ O. K) l( [. M+ u0 o  Z$ d9 i& @8 r1 {' m
    Advantages of Recursion$ L! Z: u- }, X& [' W
    ' J' o2 [) |$ v$ u
        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).
    $ Z7 v3 T3 D( v3 I, F
    ; j% O6 v8 v' i1 e    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ( [9 k6 w/ J6 U% j$ q) p7 O- T$ ?: ~0 _+ M1 m* x  c
    Disadvantages of Recursion& d$ b" P+ }' ~: W+ H0 B( X; P) d
    " z. l4 n2 L0 ?
        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.
    - p+ i' [+ V1 a+ u' |0 d2 w
    ' V  M1 X7 q  T4 t1 o$ D    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    $ I6 K/ n9 w7 g3 ]) a
      @  a% `; c+ Y- _/ \When to Use Recursion
    1 [# R1 t  o3 B0 \$ u  q3 r2 w. F" w* L* X( g  L
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    $ r( F7 a1 g/ O$ t) c- w. I# \' S) Q3 S( A) G/ y
        Problems with a clear base case and recursive case.- H0 |0 @4 B) |& E. j
    9 x" q( n- @3 d0 d8 ]
    Example: Fibonacci Sequence
    ' b- \: I' P5 D; h% j5 W1 b$ `- S3 _1 Q
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:1 d( o5 A5 O2 I. v

    6 Q; u; W, v1 N1 ?    Base case: fib(0) = 0, fib(1) = 1
    , W* ^$ }+ Z- ^
    ! V9 U, J2 b/ c+ b) F  o) q    Recursive case: fib(n) = fib(n-1) + fib(n-2)( ~* D' J; T/ m" {$ l2 b0 C
    : V/ R3 l& l7 }* S9 z
    python- O2 {  G$ U6 d3 Z. @

    . M' {/ K; O, V/ C# y8 h9 I1 \
    8 D. ^2 \9 B# fdef fibonacci(n):0 X- q7 e  Y7 N" ~+ `4 X
        # Base cases
    ; {5 n% w) L1 M% A$ s9 ^! q$ x$ R    if n == 0:
    ! z" [+ o7 r: y  L+ j        return 09 x/ B3 U  [# i3 _6 s& t
        elif n == 1:
    9 J0 _" M4 \! f! T  K5 w        return 1) {" T4 M  x; X+ W+ r7 _: M
        # Recursive case
    & ]( o* {5 ]! Y, `, q    else:# Q; E- Q/ D& L
            return fibonacci(n - 1) + fibonacci(n - 2)1 M2 [5 a7 p) t0 g

    ' C; L. X$ @' p- M$ ^# Example usage1 v/ F3 h6 N) P4 P1 r' Y6 R
    print(fibonacci(6))  # Output: 8
    ! o! M' y) M) x9 \' p+ x! h7 }  K* F+ X0 N9 _$ C. B9 o% D6 C
    Tail Recursion$ f& h7 m9 z: R8 u. i: @2 h
    1 K6 T& M- V! ]: f" e4 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).. f  s/ A* }) |
    * {; K) e2 K. u, {
    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, 2025-12-10 17:05 , Processed in 0.030716 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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