设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 q# D3 B6 K! d, F, V6 s& k; a! J! }. r
    解释的不错
    4 P8 y2 X$ m# e& V/ e# o3 \$ |3 B2 D1 Q4 z/ H
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 x9 i8 V  b' }5 q% o* h4 M; t
    . ^" }7 d, d6 c6 Q% d
    关键要素; E% ]+ @0 @' R
    1. **基线条件(Base Case)**
    ! l" ?2 l& A) ]   - 递归终止的条件,防止无限循环7 [7 f/ U& F1 `0 D& o6 p
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1" g/ b  o4 i2 [8 O4 E* V$ x

    , Z! t. H6 h' V. c/ O4 |2. **递归条件(Recursive Case)**
    0 a" {) w  F+ E. H- ]' R   - 将原问题分解为更小的子问题
    8 Z4 X; X: ?, n# |# j+ B; R9 m   - 例如:n! = n × (n-1)!+ D( l2 S: \1 [0 J! u1 v" M
    & S2 M' f; s- k+ `! O
    经典示例:计算阶乘9 }6 u9 p5 L. D8 f
    python$ W: e, N4 ], Y. G- ?
    def factorial(n):, C/ \# a7 l2 ?- c4 n( O
        if n == 0:        # 基线条件1 p! z1 j2 U3 N) |) G+ T5 N9 a* j
            return 1
    4 S. [  I) U) W/ Q  n2 ~( R    else:             # 递归条件
    $ I) N/ Y% w* F" D( d9 ~" I; S0 s) D        return n * factorial(n-1)3 {# n; D  G3 x6 a. a# ^/ _
    执行过程(以计算 3! 为例):
    + ]$ [' `& U# y4 f3 |* d+ l$ tfactorial(3)
    - E& b& w0 I, U7 u6 [/ c3 * factorial(2)
    ; M) s. J# [( I5 k3 * (2 * factorial(1)); L$ d8 }6 x% `0 N! f2 ]/ p6 M
    3 * (2 * (1 * factorial(0)))
    , I! F$ E5 G2 O) n" ?# Y- l3 * (2 * (1 * 1)) = 6
    / x) B* E( M2 F) q; F3 j
    3 s, m9 A* U: k) V& x: K- b( j 递归思维要点6 l( @* H6 M% }( b
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
      C, l0 _' T& S- L. ~- j" r0 |3 x( a2. **栈结构**:每次调用都会创建新的栈帧(内存空间)" ^0 M1 @5 `  E, B
    3. **递推过程**:不断向下分解问题(递)
    - y, N" J; k2 s4 p4. **回溯过程**:组合子问题结果返回(归)
    # H( V$ J" n8 p* E( F, Z6 ]( B- p' ~
    % i* F/ P* S& F$ V5 k( {# {& V% B! E 注意事项7 Z9 ^0 A: Z) K9 {
    必须要有终止条件
    ' M+ E. w4 u" h- K4 ]9 Z6 w递归深度过大可能导致栈溢出(Python默认递归深度约1000层); ?7 h6 @* `& `& l# }$ L. i# C0 x
    某些问题用递归更直观(如树遍历),但效率可能不如迭代# \  D( o7 Z, Q6 f$ h$ v
    尾递归优化可以提升效率(但Python不支持)
    6 V, H- x5 _6 Y$ W
    3 k& p2 m' x" N) N 递归 vs 迭代7 B7 R0 F( s6 ]# T$ {
    |          | 递归                          | 迭代               |" k# K4 Z2 }! s" ?
    |----------|-----------------------------|------------------|
    * m5 t$ a! p- A| 实现方式    | 函数自调用                        | 循环结构            |
    ! _, P* [: w9 I$ i) ~/ w| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 U0 Y3 [* g5 Z
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |$ I% a4 D% @0 w/ W' I6 @' Z
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. |5 X. Z# B( y, I* ]6 O

    9 K9 b5 k8 f9 Q1 G1 R) o7 i 经典递归应用场景
    8 l& K4 @$ Y/ @% {1. 文件系统遍历(目录树结构)$ s6 |/ p, e* M7 F$ Q: t0 W" ~4 U* t7 w
    2. 快速排序/归并排序算法
    2 |; @( K. M* B# l+ l3. 汉诺塔问题2 @* B. Z. w' _+ l+ y
    4. 二叉树遍历(前序/中序/后序)
    ; `0 l5 Z4 o" J( C; h, `5. 生成所有可能的组合(回溯算法)
    ) S& Q  p, Z+ ]2 z9 Y" z. T1 I1 z1 ]
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    前天 07:11
  • 签到天数: 3150 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' p, _: O! h) g9 p' O  e& l6 f
    我推理机的核心算法应该是二叉树遍历的变种。$ D8 d4 o' _5 W7 O2 k) [
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * f9 w  D- ]1 KKey Idea of Recursion0 J: ~$ ~! }+ a! M
    : G; q/ e0 C; c# U3 P$ ]
    A recursive function solves a problem by:
    : x$ h/ t5 Z" d1 z' q  `, @' o# v& i2 ]/ S4 c
        Breaking the problem into smaller instances of the same problem.: i* s1 w! b  w2 [3 [

    / H" H6 M8 L) ?1 n# g9 g) G    Solving the smallest instance directly (base case).; Q3 p( d3 t* n# }* p& f

    6 Y2 a9 v0 m5 j* H, Y    Combining the results of smaller instances to solve the larger problem.* ]$ e( Z  y5 `' a3 A0 n! K  z4 V3 j

      U1 t1 g& F* |( `( u% PComponents of a Recursive Function9 A% C/ b( d0 Q4 Q( l, t0 h

    3 P# I) I* e7 W( D5 m9 o- N8 h) y    Base Case:
    $ m1 I% p2 B* Q- Z' V& V: z3 r2 L6 D+ |9 T0 p
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    8 }0 v: D% k  D  v# D  `/ n5 s
    $ a0 q( ]) P( q! P* I+ D        It acts as the stopping condition to prevent infinite recursion.
    ) n' g; K9 A4 v, w: F/ _  c; U+ ?* ~( b
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.! m' w# ~9 x9 o/ |. ?
    % x8 ]- C$ H7 g+ Y( k; }
        Recursive Case:0 I8 }6 v- N- F$ a( b

    6 H2 L/ @* X$ W5 Y- G% K, c        This is where the function calls itself with a smaller or simpler version of the problem.+ k( v7 w/ |! d) N# E( F# g1 V

    3 ]% a$ D+ q" r% Q) @( m        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ; {- R5 }7 ]8 ?. N5 N7 y- F5 {
    " V1 y+ z5 q4 }" u" `. j/ A3 zExample: Factorial Calculation
      l, X  y& k- f
    ; ]4 w  l& V3 g) ]0 q5 O: H  w0 DThe 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:
    5 e6 a% Y$ R. u3 v0 G1 G8 B; K* S7 ~) D
        Base case: 0! = 1
    : k$ s# x0 c9 E; _: t! |7 \
    ' L# J  [) w# V: o$ |    Recursive case: n! = n * (n-1)!
    - n/ W8 o! n+ I/ I4 e- g* F: ~$ m. ?9 x1 k, c' r) N6 h
    Here’s how it looks in code (Python):
    9 Y5 y3 f: m. Q6 ?5 O9 A* ]+ `7 Fpython! a. u) z4 V; ^
    1 d" ^) K3 w' G0 P2 m

    ! F, ~1 ~; c/ [3 c9 s8 ndef factorial(n):; F, ^. |" y9 r" b% @
        # Base case3 L$ Z2 [) f8 |+ ]6 t
        if n == 0:
    " Q! J+ }: }3 C. {% g* a( H1 q        return 1" i7 V* r/ O; ~2 w
        # Recursive case' o$ D+ p7 _- n  ~$ s& S
        else:
    ( O4 p0 B/ ]$ K3 c+ b        return n * factorial(n - 1)- Q' t* n4 G, r

    ( r2 J% r$ J$ G# Example usage
    ; m  m! [" f7 D$ h/ Rprint(factorial(5))  # Output: 120
    : J* F* U$ Q; J. G( a! L
    / B. Q0 W9 u5 n7 Z, yHow Recursion Works
    " x' g/ {- U3 ]- V8 n7 ?% f5 C* C* a( p8 j1 a
        The function keeps calling itself with smaller inputs until it reaches the base case.  j; E  b3 s0 L5 R5 O8 h
      D3 y" V5 b, I& u, p* D
        Once the base case is reached, the function starts returning values back up the call stack.' H$ ~- {( d! L5 k5 I

    ) ?6 Q5 c" t/ |) Z+ V    These returned values are combined to produce the final result.6 x/ S8 ^2 J' e
    ' l0 c9 R. ~4 o6 E" o- z- u: ?: n* `
    For factorial(5):* _) q: i+ R+ l2 |- Z5 B
    8 p. @6 }$ U& L1 G! o- ?

    . m  [- o9 z5 k5 i6 C" Vfactorial(5) = 5 * factorial(4)' W2 N* V# K& a
    factorial(4) = 4 * factorial(3)
    $ L, W: j1 P& L5 k" N0 U4 V1 {factorial(3) = 3 * factorial(2)
    8 |1 P, [6 C8 yfactorial(2) = 2 * factorial(1)
      r. {1 n' S% ?1 N- h( R; B; {' \factorial(1) = 1 * factorial(0)/ P+ n. ]+ c/ @
    factorial(0) = 1  # Base case7 \7 Q: ?1 H+ V  ]$ R) G

    # V8 r" t6 X* RThen, the results are combined:6 k3 t6 @! ]5 A$ h" A
    % s, g$ _- z" `# D

    1 N) k/ n: n" j9 o5 y4 Qfactorial(1) = 1 * 1 = 1
    $ {# Z: j1 a5 r: j6 J) Wfactorial(2) = 2 * 1 = 2  @- k  N0 h5 S; i9 a
    factorial(3) = 3 * 2 = 6
      w# C) p$ h! _& L7 P0 b9 ifactorial(4) = 4 * 6 = 24
    0 t# n% {- ?8 X9 n1 jfactorial(5) = 5 * 24 = 120
    ( i  O3 ?0 ~7 M2 a0 P1 P, q3 p7 [& `- \/ I* k
    Advantages of Recursion
    $ \3 G4 J; T( e# J$ o6 c9 F8 T: b+ X( Q+ m" q
        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).
    2 Q: l$ {; q1 j( Z. @
    ) d& m1 X$ O' Y6 H* ?* j& ?9 P/ x    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    / `3 P0 |: H9 R2 [+ K' y, _# w% A1 l. T8 u( A( B
    Disadvantages of Recursion
    5 [. }7 t$ T/ s; w+ D% }* u, X# q# P* w8 G' V( t
        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.
    3 U8 P+ L, j% C# g- g" v
    ) T: p! [: N) O% T/ y& o    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    , b* p' K, x, |- y( H( M( p' p, W/ |0 J7 {8 L6 y
    When to Use Recursion  d% ]9 l, t6 n0 C5 y

    ; z1 H, C7 D# u    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).6 |. f& f, |" c, F) K
    ! q' s& d: E# ^- s
        Problems with a clear base case and recursive case.7 M& O2 f6 Q7 i3 B  f* P' R

    . J6 o+ j! p" w4 }( B/ `8 \Example: Fibonacci Sequence
    " d) k0 v/ t; Y
    . ?& T, M( j" m0 R. `  `; @The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:# R) Q; h! t2 G& `
    9 F) y- v6 y$ K) H5 P
        Base case: fib(0) = 0, fib(1) = 1
    ( z- n+ L" B8 _% P9 z# ]6 s% x4 s7 f# C) n
        Recursive case: fib(n) = fib(n-1) + fib(n-2)6 S* h( M5 d! H1 v+ k

    2 P3 F, f+ O! t0 vpython6 R2 J( w; ^: k- {4 |) R( ~9 z2 Y/ P

    & R8 u# D0 N  O3 E& }- x. G* W9 {! e9 D
    def fibonacci(n):
    5 P! w# j4 u; Z6 {+ k' w    # Base cases
    ; r5 ]; h( B- ]( Z: j6 F    if n == 0:) Q9 b: f, k4 M( U
            return 0
    * k! U! R9 P. [# `    elif n == 1:
    8 y' K: t1 j  V1 Z5 `        return 1
    - D- }% n4 S1 x3 c: E    # Recursive case  o1 m& I5 a( S! q  c! q2 x* [% U
        else:
    ( x4 X4 _. e% C        return fibonacci(n - 1) + fibonacci(n - 2)# B, s+ _3 h- v7 Y& [0 h

    * q- V- x9 |% ~5 i# Example usage
    7 z9 ~/ w( z! Y, l% ?print(fibonacci(6))  # Output: 8& ?  ]  R& C& e) `( h

    + U0 Q/ Z; Z( X3 E2 ?" y; lTail Recursion! a& w% f% S! Z7 K, o

    $ M/ @! w" T. |5 D$ B* KTail 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)./ t* X0 g0 r) o# K4 n$ w' Q

    ; o9 l2 W, ~8 O& C0 fIn 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-1-22 09:57 , Processed in 0.057623 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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