设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    . p3 Q1 V3 {/ J( D5 E6 [% I
    ( ]. b; g, ]9 d" |& J' C解释的不错
    9 }) W; e; Q# g" ?# ?, c1 U# P5 i) ~- S( {9 `6 z& j/ e2 k
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    $ }: I1 S* K# E4 @/ n. V8 I& a8 U4 \" J5 ^4 l- K
    关键要素5 o  `$ S4 E  x/ ?
    1. **基线条件(Base Case)**5 r3 m$ I+ g% `3 N4 E
       - 递归终止的条件,防止无限循环
    ) l, Q- K1 p0 n! k   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1) F- r4 m/ f& i* a) W

    * T3 X8 p% ^* F2. **递归条件(Recursive Case)**
    ' W1 m4 N+ d. A/ e3 t1 Q   - 将原问题分解为更小的子问题
    1 z8 a4 |: }" _/ _; I' B   - 例如:n! = n × (n-1)!9 Y8 e9 b# b' _

    - v' X) ~" D4 C 经典示例:计算阶乘. p! ~- l5 u/ M; J4 a( s
    python' M( ^; s9 y! b  t
    def factorial(n):+ ?6 i; L% ?/ C8 O
        if n == 0:        # 基线条件* n8 o0 w) _2 \% l4 s3 P
            return 1( R: I" F2 C. v' V5 e
        else:             # 递归条件! k6 c% ~; c2 R. {+ I6 I' W
            return n * factorial(n-1)  y/ @, i5 u& }3 q0 ]6 r
    执行过程(以计算 3! 为例):* E! _) C& G4 k  y
    factorial(3)
    7 z$ }, p+ d) Q3 }3 * factorial(2)
    " d+ t2 A! p7 K. t8 b  ]0 N2 T3 P3 * (2 * factorial(1))
    6 n9 S4 i! @8 |' I- {. O" K3 * (2 * (1 * factorial(0)))
    6 {. [# J( V) @3 * (2 * (1 * 1)) = 6
    : A/ S; f9 ~( \+ ]: {9 {2 L1 _$ T8 d/ ~" [% w" G) `) {. z; r6 L
    递归思维要点4 P3 M2 @- E( d
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    & o0 |% ?! \: e1 z5 L0 u- G& Q2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    8 x6 A* m2 o8 J/ {" T, v. Y3. **递推过程**:不断向下分解问题(递)& N6 t( }. e! W! _2 S. }6 l- L
    4. **回溯过程**:组合子问题结果返回(归)
    % V: Q4 o8 t2 L# ^
    * {1 X4 c1 Y) V6 ] 注意事项8 T0 \  p" o5 |) j2 d! m4 J
    必须要有终止条件
    6 a6 [4 @3 P  ^, W递归深度过大可能导致栈溢出(Python默认递归深度约1000层); V1 @( o$ G$ C! I9 v
    某些问题用递归更直观(如树遍历),但效率可能不如迭代- p, \1 c# G# |
    尾递归优化可以提升效率(但Python不支持)
    $ H8 H& t; g9 I& T- B6 e0 Z6 i/ H2 n1 Y
    递归 vs 迭代  P1 R, F6 i  T( l- x
    |          | 递归                          | 迭代               |
    ! N0 u) E! @5 F8 S7 ?1 a|----------|-----------------------------|------------------|
    1 a) S( e: P3 G. ^: J| 实现方式    | 函数自调用                        | 循环结构            |& m' {& B3 i3 D! _5 V% r
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ; O: X) P1 w* t6 [7 X| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |$ E; l/ q8 [) R% y4 _
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    " W5 j0 W. D; |" c: J& [9 J( O( M5 D: \& o; d2 [% z$ N0 r
    经典递归应用场景
    ; D+ x0 I% V) [4 |& e' y0 }7 ?/ g1. 文件系统遍历(目录树结构)
    , s+ h% q! z* J  a) A4 @0 p2. 快速排序/归并排序算法
    ; G3 Y5 Z5 x( h: u- w# _3. 汉诺塔问题- D" u- l8 ~; U8 [; R! v8 t
    4. 二叉树遍历(前序/中序/后序)- W& r# W9 @( R# D3 r
    5. 生成所有可能的组合(回溯算法): f' B: g$ ^- O

    4 L. Z/ C! L% P) X0 e) i; r* R+ Y' j试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    2026-4-9 07:45
  • 签到天数: 3217 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    / C& K% O; m2 b0 b: z/ M我推理机的核心算法应该是二叉树遍历的变种。* M2 u0 N# N* V- 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:
    ; Q+ Z3 p: i7 K- FKey Idea of Recursion
    : ?5 w2 e- P6 w. S$ D; k+ p% ]) ?% u5 K, D! K' N/ c
    A recursive function solves a problem by:- \0 o' o- }8 n+ A9 W6 s) a

    ) w3 T, s6 I" g: i  {! M    Breaking the problem into smaller instances of the same problem.
    ) V, H* a) a+ Q6 S
    9 _+ @' v7 Q% q1 t0 q# \/ ^    Solving the smallest instance directly (base case).
    $ e$ q/ z" Q$ `
    " y4 _" C) l  G3 ]0 ^    Combining the results of smaller instances to solve the larger problem.
    * E% o9 j4 S! h7 d; Z6 K9 u, P+ S' K) d. Y% s" S: Y1 Z" `1 v
    Components of a Recursive Function
    : P5 J4 K2 s5 }( J" h: b$ g( \9 m" I: W/ G0 O5 D0 N# V
        Base Case:% T  l5 G- q- P+ P8 a

    / c# O: N# \; |, D- x  l        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    - b2 P" Y1 r* l, Z! X  z, }* H- {  x) o/ H( b& @+ ]
            It acts as the stopping condition to prevent infinite recursion.% N2 O/ M2 |- _1 q1 N: i- D

    * h$ A9 ]" N1 M( l# B        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.* f4 F& f4 T! c" ?
    % K! {& [% ~+ Y' j
        Recursive Case:
    ) A  O$ G; G7 L1 `3 b% o- w3 Y! e! B+ Z& _4 T/ E
            This is where the function calls itself with a smaller or simpler version of the problem.
    % Y$ X' M0 ?8 A4 I7 p" d+ F4 l3 v2 Q0 J% z* J. k) c
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).: F+ y. i2 Z9 W4 o6 B
    7 ^! f7 h3 T0 ]3 B; ~) ^
    Example: Factorial Calculation
    " v; Q. }/ D/ \8 P$ r3 ~+ v3 r$ D
    1 D7 Z! F+ g& k/ \* 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:" B7 L) }" t; i" O; _' M

    8 @- l+ y4 c6 p    Base case: 0! = 1
    & M5 S$ W( T+ s+ ~* A
    8 \" @/ ]! {3 a) S' d! l3 ^. Q    Recursive case: n! = n * (n-1)!) a1 T7 Q" \$ A, a: G
    + Q' V1 P5 d# j6 J: g
    Here’s how it looks in code (Python):
    - R& k' N# c' E8 \9 Z8 f! u3 V# p( Kpython5 v& e5 r4 V0 H

    4 P9 ]; A% N; T; A) A
    3 C, W3 w0 ?" M) F! z) E  odef factorial(n):) F- P6 S) G: p3 Q
        # Base case2 V. d1 F8 H, I  j
        if n == 0:  q4 R5 W, X( _* `0 W- C. r
            return 1
    & `- P/ w# \4 M% @4 x& p    # Recursive case
    : j. R/ H: V! y( M    else:( O: B( s( w+ j) c
            return n * factorial(n - 1)
    % A; d8 \3 Z9 j% s
    : K& N% @1 Q6 U- f- @, F# Example usage
    4 `# k6 G& N1 dprint(factorial(5))  # Output: 120" }" o% N+ g. Y' M: ?, J# F
    3 ~( h# x( g3 p/ U* b" N
    How Recursion Works( x$ G3 ~8 [: T& i; h1 i* ]1 x& E

    ; T8 Q; L, Y+ N# f# u7 w! v3 y    The function keeps calling itself with smaller inputs until it reaches the base case./ f+ j3 j* S4 V0 t; K- Z

    , L6 m( x2 W6 \$ u    Once the base case is reached, the function starts returning values back up the call stack., Z# |$ a8 x* _: z' ?9 v
    6 T/ U. k2 p2 ^& R" P2 T8 M
        These returned values are combined to produce the final result.
    / I0 M+ M1 H+ x( V4 t- D
    8 `1 n* @+ [! Y' g( g! UFor factorial(5):4 N& l6 \1 ]5 k+ G" l

    8 v8 Y2 U+ D2 h& l3 t
    , g" s& }( G. h, V9 w% v6 A! ifactorial(5) = 5 * factorial(4)
    8 G+ v' y+ f) v: h  N- |9 ifactorial(4) = 4 * factorial(3)
    : ?) w" F  E) S$ ?factorial(3) = 3 * factorial(2)& P% y, \* x& M  P* g$ s0 O
    factorial(2) = 2 * factorial(1)
    4 O: W: t0 i" U( U7 H% c, ofactorial(1) = 1 * factorial(0)
    & Y( q+ `9 n, Q( b* _# N7 [factorial(0) = 1  # Base case
    1 T+ v. D4 e4 U8 Y+ x& T. l( l$ O/ b$ W5 w
    Then, the results are combined:6 V, W4 q2 F) t$ ~4 t4 G5 C( t6 E
    ( O: k+ J4 U: y- |

    6 D& b* C, A4 C2 `. I) ufactorial(1) = 1 * 1 = 1/ k1 v1 \8 }& E: V
    factorial(2) = 2 * 1 = 2# ^1 u$ T6 ^7 r$ S4 \/ b
    factorial(3) = 3 * 2 = 6
    ; H8 K% z+ [9 ]factorial(4) = 4 * 6 = 24
    3 ~2 ~, y- w1 Zfactorial(5) = 5 * 24 = 1204 k% h/ N4 i6 k# L# B+ X. j
    6 ?, a0 O1 d$ }
    Advantages of Recursion
    ! B& s; m! F, I! D, H6 }6 H/ b/ T: K* K; }) Z4 B3 ^" M* G0 x
        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).
    , I% Q3 t% F9 `( Q
    5 {! R. C, f6 J- ]6 p) o$ A    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    9 j5 J  |" |: R, y5 L$ n; _% D! n- t( a$ R( b9 a% F# h
    Disadvantages of Recursion9 \6 t7 ]0 N) V3 O6 e5 R
    " @( K) S$ d& H/ X& G! D" W
        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.' H. Q! U& U2 _/ K

    2 x, k, ~* f- K; \8 D, O    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    : F4 r  q. o4 g) o
    . r% g4 A3 u  F$ @When to Use Recursion; i3 K" Q; f, h& ?2 y2 i" M

    * @; r: N% U, L% ^    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ! @. g  q3 e# {
    4 i6 I$ B1 K4 R; s: f    Problems with a clear base case and recursive case.
    " d2 X6 ~& I) R3 F/ Y9 R
    : V9 A* ]* E$ i) `# i% IExample: Fibonacci Sequence
    . t7 M% k, R% S. U* L: f/ \# M, N! {" ^/ K' z
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    % I. E: l+ t2 J6 ]) ~' f5 G, c' B$ T
        Base case: fib(0) = 0, fib(1) = 1. R4 L# e2 `1 O7 Z8 V

    ) ]: ]7 p" P6 q( p; Y/ ?    Recursive case: fib(n) = fib(n-1) + fib(n-2)) ]5 a" i3 q' q1 [- r: F

    ( C/ j2 C8 H9 z. L& npython
    # r) }; T: p( W* M) B9 L3 M8 s+ |7 x2 I  q8 S; d
    - B5 t: x* d# O. g
    def fibonacci(n):6 R# k+ y; Q5 V! Q8 b
        # Base cases
    % m/ U) E* p6 I2 `    if n == 0:
    $ O( v) H/ \4 y. [( x- v! x' j        return 0
    3 _) w1 _' `" R3 S    elif n == 1:( g. P. v! m6 @
            return 1
    ' F' L: l, w: M8 G    # Recursive case4 w6 S; Z1 Z/ T
        else:
    2 H% f1 \) \$ ?7 ]% h        return fibonacci(n - 1) + fibonacci(n - 2)
    ! E( R' {' S) h" z+ `' Y7 A3 o( K  x  Q( A  {
    # Example usage- s! y6 c( e; a* L* ~8 k- u
    print(fibonacci(6))  # Output: 8
    5 E/ p4 @5 v, l0 _8 A" w0 m  I/ s- E  g
    Tail Recursion9 Y4 n: ?1 N+ I  e. X

    . K$ }  l2 f3 Q+ w; o- rTail 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).
    / Q" p! l0 p, V, x! L3 q% R7 @
    ' m8 d  I6 A* Y, p4 q# xIn 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-17 07:22 , Processed in 0.063961 second(s), 21 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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