设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    % |: b2 r  f2 N& S0 x2 n
    1 Z8 x$ y& O  h8 e解释的不错
    3 R2 h+ k6 J% h, `! L* a7 L; q2 A$ v4 _
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ( t7 t9 ^  ~3 B2 P
    + E# S6 f( C) I! H$ f 关键要素( O( i! d3 Z3 j0 K0 Z; i8 f( X, Q8 c. P
    1. **基线条件(Base Case)**
    9 T1 P5 @$ s( @0 x   - 递归终止的条件,防止无限循环! k8 F$ j/ `  }
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 15 Z! `, `% z. F) p$ Z* p  E
    4 F: b8 `. _$ t) I7 [/ ?8 n
    2. **递归条件(Recursive Case)**
    $ T0 O, y- j) J% O   - 将原问题分解为更小的子问题/ a/ b! E+ c/ T; f- p
       - 例如:n! = n × (n-1)!
    . K8 @+ ^) @) y) p* J/ D3 m, E% J9 n  I
    经典示例:计算阶乘
    8 Q& o4 u$ K% Npython
    * m6 E8 z3 c4 \5 Zdef factorial(n):
    " W1 P/ }! u6 j% B1 _8 ~7 |2 ]4 L' l    if n == 0:        # 基线条件
    . I8 T5 C. Z' q/ i        return 17 }3 z- b  t. X/ J+ u6 k
        else:             # 递归条件
    " ^5 |+ H. h4 j7 G' h1 c/ L        return n * factorial(n-1)* r' C1 A8 i8 b8 k- G3 b" @
    执行过程(以计算 3! 为例):
    ) }/ a$ H/ I- x; g1 C& Pfactorial(3)
    ; W% ]" l4 b( S1 n/ B3 * factorial(2)
    ! Z) n6 i: J  x0 t3 * (2 * factorial(1))
    / L7 z( p+ h0 r$ C0 D/ h/ y3 * (2 * (1 * factorial(0)))$ U3 z6 j  c& r2 c+ a
    3 * (2 * (1 * 1)) = 6$ N; m& R8 v4 `9 G

    4 t1 `* `' o2 P 递归思维要点
      f+ E' ?1 _+ j* a5 ^6 I1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    8 H/ I* s6 W0 E$ c; ^( r2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    3 _9 ]$ E& h1 \- P: D: ~  {* G3. **递推过程**:不断向下分解问题(递)
    4 g( z- ]# C* N  B4. **回溯过程**:组合子问题结果返回(归), r6 g: {; d8 c+ U% d; o6 i1 S
    " V, \0 n# y* v1 U( q6 ^2 M7 j
    注意事项# A4 S# H+ o# `) e
    必须要有终止条件1 }5 |- E- U$ b, }8 U
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    7 x# J9 S7 i" ^+ |# U1 s7 l某些问题用递归更直观(如树遍历),但效率可能不如迭代0 C+ t/ @* X8 x9 T: C" J2 P
    尾递归优化可以提升效率(但Python不支持)
    8 j) |* u1 J; L, u4 m  F8 g
    # p. D1 }0 ^. e* P" [0 _ 递归 vs 迭代
    ; T, ~. \; f# W0 x9 L  `8 ?" @|          | 递归                          | 迭代               |- v" g& M! h2 Q" |
    |----------|-----------------------------|------------------|
    1 l6 u: e' b9 X$ i5 I- _# O| 实现方式    | 函数自调用                        | 循环结构            |
    + Q0 _+ j  i- N9 @- d| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    . `- c) W$ L5 ~4 m| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |: Z/ H& B& D! ~3 `4 c9 j& ~8 L
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ; \# i. z# j4 ]' d" G& s( ]' ]- V* `( J/ q; ^
    经典递归应用场景8 w% ~; R0 }6 H+ n! z) v7 B, f" W" u
    1. 文件系统遍历(目录树结构)/ Y0 @4 D- j5 C& l2 M5 H6 a
    2. 快速排序/归并排序算法
    % m. a* z5 I4 A" |3. 汉诺塔问题. W, k; x! k9 w
    4. 二叉树遍历(前序/中序/后序)& L* r+ n9 b, m' H  o+ R9 D( A# K
    5. 生成所有可能的组合(回溯算法)% g1 l% \" n' W0 I  C+ q) S
    8 ]2 [9 f4 A9 F4 \! a/ ~
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    1 小时前
  • 签到天数: 3099 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    # Q) Z" \% v' C+ L! _. u$ a: f我推理机的核心算法应该是二叉树遍历的变种。
    * _: R+ V7 m" {6 M另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    : J5 C% R; d1 D. W" q6 kKey Idea of Recursion
    / D8 C/ ^2 f# a8 L' G8 F7 a8 j5 ?9 Q* x$ F2 x& K6 n
    A recursive function solves a problem by:& A. w0 \" o0 g1 p% A
      K; u" l, R% N3 a9 X4 j  ^
        Breaking the problem into smaller instances of the same problem.2 H* q2 @: u& y1 d; b

    ' u3 _3 h6 b6 I/ s1 P    Solving the smallest instance directly (base case).
    : @% e& X9 V# u5 W  a5 K# S" k  O; a  n4 ?$ r: t! b1 k  \
        Combining the results of smaller instances to solve the larger problem.
    0 y( v: I: N0 a( c$ F: n+ ~- d, K- i7 k& w& ~! X
    Components of a Recursive Function
    ) {2 F7 v; D6 |  M( t0 B) w5 s3 h7 R9 m& e  s1 N, |3 F  J
        Base Case:
    " \5 g( I3 p5 q" v6 n# x1 }& R
    & R/ j' G+ V/ N7 x% T        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    9 Y/ Z$ @$ R/ A6 O) P3 [" G0 J  u4 B8 `
            It acts as the stopping condition to prevent infinite recursion.
    / I$ M" x2 U& d1 n3 X2 y
    3 o. o" z8 o* d8 k, ?8 F5 z' E; Q4 D9 t        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.1 l% G) N9 I' f4 _- e

    1 Z+ j! ?9 K4 y1 X* x    Recursive Case:- l# o( b2 l* a2 X7 Q

    7 y- w$ l6 g! |' v2 W8 [        This is where the function calls itself with a smaller or simpler version of the problem.
    5 o6 |  e) A2 v; n
    - E; g" o, \6 F( A9 {  E        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
      G2 \, d8 _* Z9 P0 D- _3 j1 L( T5 C$ g2 N% d
    Example: Factorial Calculation. j5 j% H$ ]1 @- l. t# W2 C2 d# }

    " O1 J/ U6 I6 R7 ]- D" hThe 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:
    * c0 I+ E$ [  f. L
    , ~+ A4 Y, Z  I6 b' d- A9 r% L    Base case: 0! = 1
    - H, k7 J# D" ~1 f/ e+ |, E" L1 y) |2 y2 f5 ^
        Recursive case: n! = n * (n-1)!
    . G) N9 n6 T& p9 p6 b: q" Z. c
    , w) \- Z6 }5 t- s! xHere’s how it looks in code (Python):7 x; p4 `' o; `( F5 M4 {. R
    python- \3 K" |4 X- z# r3 Q, V

    + j/ x5 ~/ W" S/ R
    ' Q5 p% w7 U1 r. ]) W- [2 I! mdef factorial(n):
    9 ^* Q0 C7 [, \) j, n/ `" ^) P; K    # Base case4 C6 J2 }" a% _3 {5 t/ E
        if n == 0:  O3 A4 T0 z. L5 e7 C$ ~
            return 1( m' n- R: f) _2 f% X
        # Recursive case
    . C. M9 O6 n. H' Z7 u$ Y    else:
    8 j' e& x+ n# ]% W        return n * factorial(n - 1)& o: g# y) X1 K3 L
    5 A- _' ~9 o  e  _
    # Example usage" }' c6 B; J) P2 J  }) N( H: ~3 V  ~
    print(factorial(5))  # Output: 120
    * B. v) N) }- o; Q4 p5 v( i3 f2 \, u. c6 j- u9 q; O" M
    How Recursion Works) R6 A' E9 j1 C7 D. D  g! Q
    ; S9 ^( u7 J4 m" [1 f! I
        The function keeps calling itself with smaller inputs until it reaches the base case.3 N* V! z9 X8 U7 y5 `: `/ e7 V

    7 h9 F/ _* O0 V" Q3 A* A    Once the base case is reached, the function starts returning values back up the call stack.
    1 X7 C; L4 n$ }0 J9 D0 c8 Z) \3 W8 w
    ' Q! P' k' s2 S' }% {    These returned values are combined to produce the final result.+ S. n8 `: Q3 Y
    . f0 q( R2 H1 K" V
    For factorial(5):& z9 f' B9 a! V9 z( A* W
    ) j& }+ v1 e+ T% j" \2 o
    : B  \7 ]7 a& X$ Y
    factorial(5) = 5 * factorial(4)
    $ @" x* o+ U" V! `$ n& y5 F7 k  mfactorial(4) = 4 * factorial(3)
    * X5 w$ U% N5 H! ^$ k4 Tfactorial(3) = 3 * factorial(2)7 B2 j1 f! a, h
    factorial(2) = 2 * factorial(1)
    $ J0 p. X) n2 D" H8 Ifactorial(1) = 1 * factorial(0)) w4 g6 o! l5 t
    factorial(0) = 1  # Base case0 [+ k  B- v- p- t$ \6 d) w

    ) F8 Y8 x* O9 b7 KThen, the results are combined:9 U1 Y1 |) P! {( B$ X6 y

    7 t* f! Q/ `4 w  q1 u! W( U! |
    7 ?# J& }, l  u5 R* f# Yfactorial(1) = 1 * 1 = 1
    # O! d- W7 K/ a, H* x  ofactorial(2) = 2 * 1 = 2; M% N1 e) \  `/ _% z' ^1 @: x
    factorial(3) = 3 * 2 = 6
    5 J- p4 _' c5 u4 }: i; @factorial(4) = 4 * 6 = 24
    % \, J+ s! b3 p5 U( |9 X6 q* Cfactorial(5) = 5 * 24 = 120
    4 }0 \" C2 G" O: w
    4 H) }& k: h" G1 K% j8 eAdvantages of Recursion
    $ h. i* X: E* C+ G
    $ L9 a' A& F/ l& N- i$ ]6 j    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).
    $ T8 k, p; L: E
    ' ]' D' j' j* @! e; J    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    0 x0 W- k$ i' A$ c' D
      X, ?: f! E; F# [" uDisadvantages of Recursion2 F- O( {6 o0 Q- u, |9 ~6 W0 w, K

    4 q! R# k$ F& z- v3 i  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.# Q# Y  o4 ^1 G# C% E6 r
    : d# z' j( a* @$ w
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).9 e7 y- n. f' V! }

    2 M8 \' T; q) v4 w! ]2 U- Q0 h/ eWhen to Use Recursion; W1 f. s2 g+ ]1 z4 a

    ) z7 o3 V5 V9 B7 V! f    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ! p! j5 Q( v( ~: _
    $ A: ]) ?3 W0 \4 b5 n' I9 z    Problems with a clear base case and recursive case.5 v( y# K( l. g7 i6 p- x
    3 m9 v6 h" [& `  [3 `4 _# }( ~9 B! b
    Example: Fibonacci Sequence
    6 l8 z3 b! M' Q( \* E
    . d& x2 h+ b. G/ |3 n2 o' I8 V  }The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    $ c* n% F$ d5 T! U* M9 O6 L; W/ [/ U, @# g
        Base case: fib(0) = 0, fib(1) = 1+ Q" o; d8 C+ _. t$ F, X' D3 O6 p
    " X6 Z% n7 `8 e
        Recursive case: fib(n) = fib(n-1) + fib(n-2)7 ~/ z( y/ I% b- P$ \% |2 t1 I

    : ?( Z# a( q# X3 Y2 a6 V2 Z( q* N, Xpython
    $ J5 p) G; D8 h! p
    7 b# i# J) B$ }. [" ]( q; P3 o1 C! U. x
    def fibonacci(n):: T0 X% F! V! f0 ?1 T6 w: A
        # Base cases
    * {" g7 A7 Y3 m0 Q- v. i' W    if n == 0:
    * n6 Y) h3 q6 G' O7 H1 T9 i' l        return 07 C. I; W5 S( f* U& m3 p( U! K
        elif n == 1:6 P1 u% E1 ^  L
            return 1
    4 H% @6 b6 O4 `. S+ ?    # Recursive case
    1 o' x2 H* g' z  B: y- w! |, \/ h    else:
    2 Z4 e$ X2 X! r' P/ @        return fibonacci(n - 1) + fibonacci(n - 2)0 V3 r% i% B; k$ p/ ~1 E. O

    ' ]: {0 p. p! _: g: `1 `8 D# Example usage
    ( b3 t, d6 d$ q8 n) b( Sprint(fibonacci(6))  # Output: 8$ Y5 k1 M$ K* z. J
    7 C  H$ [* d$ ^! x0 M. r; }* y
    Tail Recursion
    8 @+ h5 Y4 y/ G! q  O" F1 y2 Z; u4 L# t/ v( G' U; w
    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).
    ( @# I) I& X, Q; v
    ) F3 f8 a- o5 Q# i9 ]2 D# VIn 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-11-22 08:35 , Processed in 0.033297 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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