设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ; y& I- l9 I+ p: c3 ^
    7 s2 v( W0 Z( {' s: s8 x7 V解释的不错
    ) F; q- I* e7 P+ |$ K9 @5 E6 p4 \4 Z' i
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 O2 p6 y# `' d

    7 W6 {; W; E4 j0 B7 z 关键要素1 u8 u# `" H' P( \4 \  F/ V2 G
    1. **基线条件(Base Case)**
    + G, |% {) J  E% n   - 递归终止的条件,防止无限循环3 Q% y# h2 s% C
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1, a' ?& v6 p4 w$ z7 f, ~: Q7 f: M

    9 I5 ]8 n2 `# O2. **递归条件(Recursive Case)**8 d8 K/ R+ q4 ~6 V
       - 将原问题分解为更小的子问题$ @! g' c! D) o. [4 F
       - 例如:n! = n × (n-1)!( o7 l$ I+ ~% u4 l5 L8 Q& Q
    0 T  u% O7 r3 y$ {6 O- u) q& X# w! U
    经典示例:计算阶乘) ]. g2 ]- O7 [5 K0 y& t0 a
    python
    * ^( }5 h' b$ b9 W, f6 B8 wdef factorial(n):7 b7 @+ N, f! N) j+ |& w9 p) Z
        if n == 0:        # 基线条件
    6 u, P7 E: u6 h9 G# s: z# A        return 1; l# m- E( C, `, J
        else:             # 递归条件
    1 @8 w( k$ k5 m8 a: m, i        return n * factorial(n-1)
    . X6 r; k7 K) z" z9 s执行过程(以计算 3! 为例):
    ; F; l7 f  F# `+ J* Ffactorial(3)8 ~& {/ K* E( e. S# H' Q4 j
    3 * factorial(2)" Q* V2 d0 L# X: e- S8 U: Y' m
    3 * (2 * factorial(1))
    9 ~+ B% O4 `9 n6 n6 r" h6 S$ x+ D3 * (2 * (1 * factorial(0)))0 J6 L6 G2 F; {$ g7 O
    3 * (2 * (1 * 1)) = 6' j$ x* G) N. x: @# I
    - l6 @! \4 H8 |4 g! b/ ]4 f
    递归思维要点6 `% j" P" `7 e  \9 V
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑3 o. Q. b, A3 r3 m+ e- c9 T
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    * v# v% Y) p' ?3. **递推过程**:不断向下分解问题(递)
      l  ]$ d* Q% A4. **回溯过程**:组合子问题结果返回(归)
    ; C2 g# z7 d; B2 F; |+ o; P- c8 R  {5 M! x
    注意事项
    * {; b9 a' ~8 i必须要有终止条件9 o' W1 s2 p; @/ U' N1 }! @+ ]2 |
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    6 k* i( P8 Z% |; h8 M: _% Z某些问题用递归更直观(如树遍历),但效率可能不如迭代: b) j& C0 h2 E
    尾递归优化可以提升效率(但Python不支持); b. I5 m2 z: y8 R* e# B

    * p/ N' H* @: T; q3 ` 递归 vs 迭代+ E4 F' x, g! N) }
    |          | 递归                          | 迭代               |3 F1 ~: [% R) E6 C) J
    |----------|-----------------------------|------------------|
    2 {. }- ]1 D8 y; Y| 实现方式    | 函数自调用                        | 循环结构            |
    & Q- Q5 ?' j8 f" k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    % a9 h& ^' D* C8 W- B| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    " C( @6 O$ q& Y0 x| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    3 ~3 N  H4 G) b5 W) I  Z& [! v
    - c3 R& v$ ?% j  f3 X4 T 经典递归应用场景, y* ~8 N8 M; N$ F# y5 h) {* h: I+ J
    1. 文件系统遍历(目录树结构)
    ) S) [4 w. K6 S' [0 `2. 快速排序/归并排序算法6 e  L, F- p3 E; w4 d  Q
    3. 汉诺塔问题
    4 `( I% p$ U( a3 M! B( `4. 二叉树遍历(前序/中序/后序)7 Y! _. A% A* h2 k+ ^
    5. 生成所有可能的组合(回溯算法)% L# T9 [& K) |% w1 q4 @7 m
    + q) c$ m! |; t! P9 z. l# L
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 11:23
  • 签到天数: 3108 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    - s* O% |2 I6 M) M+ k  H* ~8 v0 x我推理机的核心算法应该是二叉树遍历的变种。
    ) Z4 h' O2 i( p; n另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:+ ]$ D: J& B& H. `
    Key Idea of Recursion; Z) g0 C& p$ x! F4 f

    * M( z0 g! U' E+ D$ OA recursive function solves a problem by:
    9 w! E* Y6 H  ~4 P: l+ I* \- b  {( a" q9 @
        Breaking the problem into smaller instances of the same problem.$ f% g3 R! E8 E8 }2 X

    - X1 s( {$ W5 K8 p% l" n    Solving the smallest instance directly (base case).  c# ?3 T6 F4 j; b4 ?- i! E% Y9 j# C
    1 |0 b; r8 ^) h/ ^
        Combining the results of smaller instances to solve the larger problem.
    5 H8 a5 n( Y+ }6 ?0 ~7 j/ Z" ^. v- o% Z, t: B$ E
    Components of a Recursive Function
    9 a- K. F  o9 s, I0 r! W  q/ h8 Z  [4 ^
        Base Case:
    # t9 l( Q4 w: c& E8 m  l) ?7 d  W, e3 t  ^$ z. @: a
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.) f* }8 r" F) F1 d

    4 z. y: \3 b2 M+ }6 l        It acts as the stopping condition to prevent infinite recursion.
    / ~, M6 y+ F2 b  x3 J$ \7 f5 `# D! H4 D# e, @+ l
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    2 h9 i  I- \. g
    : t0 }' y( h: H4 V" ~5 O# N    Recursive Case:- M# V+ i: ?/ ]

    1 T( m: n- v4 C# Z" F/ Y* m        This is where the function calls itself with a smaller or simpler version of the problem.7 s( ^$ v8 E9 G! k, Y

    ; h  V% V( R* J0 U5 T4 |        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).9 A, ~+ o9 ]3 a) L
    # R6 P: m/ A0 p3 m5 \
    Example: Factorial Calculation
    ( s9 W' M) \- R7 [0 e$ u+ G4 h3 S5 r, z4 |  E/ h# G4 P3 c
    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:
    3 d. A9 l0 K: ?! k' n& W  n* D. W5 a: O; ^* h, s
        Base case: 0! = 1
    ( u2 Y8 J" s' s* w& w
    * ~1 {9 ~* _9 a    Recursive case: n! = n * (n-1)!# w3 F7 ^# b; |9 H9 s# R4 l

    / b( |, ?4 K! b8 w% lHere’s how it looks in code (Python):
    9 A1 q6 K: M: m! h) tpython
    " T7 j, j3 z' b9 O' L
    4 |5 m3 z& Z; z) ?# J1 Y0 j1 Y% z# @
    4 p) d# G! b* r$ @1 S( {2 ^def factorial(n):
    % A+ I- Z+ t+ C$ g    # Base case
    2 ?3 ~& @2 l6 d" A$ h2 f  s9 E: y    if n == 0:
    / c' {* b- j! g7 ^3 I. |" b        return 1; f; x3 D  `3 }6 l6 x
        # Recursive case8 |0 }& e: C( E
        else:& ^& ~' X# ?; X9 }7 g6 J
            return n * factorial(n - 1)# D! Z, N4 r0 c: Z7 a

    2 k# i3 s* f; v' ~' z# Example usage' `- y. f- b; a+ D3 b0 [" z
    print(factorial(5))  # Output: 120
    * g) ]! @! O; ]4 L- h. g2 u9 I8 @: t5 T# |9 y5 }9 t
    How Recursion Works  w6 w2 W9 Y4 }/ u9 T- h1 N; S0 A
    + p3 U% x) N$ ]+ {; p  k( L: ?& E; N
        The function keeps calling itself with smaller inputs until it reaches the base case.
    ; }  f, X$ P% n2 V" [1 L3 J
    ' i6 e) t! P) N% u- ^    Once the base case is reached, the function starts returning values back up the call stack.0 D# Z/ V2 s5 ^) l+ r
    - U: w4 u4 O, \( Q  w: ]+ V
        These returned values are combined to produce the final result.
      z- l! R7 O8 U& e/ ?' p2 x5 [- @, n6 I; g3 @' D
    For factorial(5):
    # z" _* @9 U1 y, `3 t% @- F) a- F( P4 Q( d

    6 T$ t9 z0 b) ^! L- c' x. Vfactorial(5) = 5 * factorial(4)  G  x$ h$ W( l+ g3 s- {
    factorial(4) = 4 * factorial(3)
    6 E8 W- P, j4 _0 r$ }) @7 Vfactorial(3) = 3 * factorial(2)2 I" |9 a% e) J- J+ l9 A
    factorial(2) = 2 * factorial(1): I; a$ w& m$ |# z- I0 y- X4 K
    factorial(1) = 1 * factorial(0)
    * X2 y7 U' ~  V/ @) Nfactorial(0) = 1  # Base case
    " F% Z. S* N1 W
    ' P. S2 O% r9 e) E  b, H! d& v% qThen, the results are combined:& f1 @! r& q, ?0 ?  [
    2 O1 j7 n( n6 x* V1 o
    5 Y; N) N  ^; |6 Z* B
    factorial(1) = 1 * 1 = 1( k% t+ N3 Q, b
    factorial(2) = 2 * 1 = 2
    - S0 r2 x7 f) D: d7 J. x; ^$ rfactorial(3) = 3 * 2 = 6' a: B. ^7 r. ?
    factorial(4) = 4 * 6 = 24
    8 u' {: s, p; R8 _5 G2 ~; ofactorial(5) = 5 * 24 = 120
    & ~0 C: a4 P& C1 e2 e# R9 T
    % T0 }- i! M9 A8 c' bAdvantages of Recursion/ j: S$ o+ o; J& S9 ]2 E1 }

    , X0 \8 u: H: t    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).
    " c) w& {! f; f" G' b- q' I& b
    / z. d3 ~4 F7 |6 I4 U    Readability: Recursive code can be more readable and concise compared to iterative solutions./ q- M. C; x# W8 ~

    - y4 o) t% \0 x* p) |( ?# LDisadvantages of Recursion
    6 |5 r8 ]: a1 X" ?9 B4 a; |6 H  a& A5 D6 U' z0 _+ ^
        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.% E! n$ j; a5 I5 b# e$ n- N3 z% T  ?6 S! F
    ) ^2 s6 n9 R# d* U8 V8 h2 }9 F& R
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    - B- x% C6 v. {# Q! h1 w  h1 Z
    7 `1 W7 |7 N  _  hWhen to Use Recursion) c9 v9 s. G3 F; M% |$ h
    4 F9 W- c/ B9 z' K
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    1 U/ b2 M0 v8 m. I& w2 F0 L
    * b8 Z  r# V" z5 l  n    Problems with a clear base case and recursive case.4 e' ]# s  W: h1 `7 \6 C
    0 y& i( ?7 a( D" X, t
    Example: Fibonacci Sequence
    . j; M3 t/ g) [* N9 ~( e2 @0 g* Z9 N- v8 i9 A( h
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    1 x) ~+ [* a9 `% ~$ Z' f) B. Y0 M0 j" X/ t2 ]
        Base case: fib(0) = 0, fib(1) = 1: {: B  b7 E8 h/ @. P2 a

    & a3 }  @0 U5 c! z    Recursive case: fib(n) = fib(n-1) + fib(n-2)/ s. _6 K: m6 Z/ @. H$ K* c0 [
    $ I7 c& O0 v0 K) ?* m# J/ J6 s$ ^8 P
    python/ \( ]) c" M$ O3 s
    + a5 P( U# F3 T6 d& Z" }

    8 J( h" U3 F) C1 I, G! \def fibonacci(n):
    6 }7 c* p: |! u" T0 o* \. H    # Base cases0 G+ T' @' }! Z0 D! [
        if n == 0:7 Q$ l: d- q; f+ Z1 l8 Q: c/ l
            return 03 @: C3 Y+ q( [9 M5 x: i: g2 G
        elif n == 1:: O- k6 Z6 G7 a5 T- P' G
            return 1
    " `# V) y/ \0 ?. x- r( V( \( v    # Recursive case9 s$ N5 m9 B" z0 ~( M* s% ]
        else:0 k$ j9 f: S1 ?- b
            return fibonacci(n - 1) + fibonacci(n - 2)+ X4 L5 I3 d: t

    ; H: _! q2 D- w* t9 m' C# Example usage
      D2 {$ X: m. ~5 i# O& a% e1 Yprint(fibonacci(6))  # Output: 8
    . z8 q1 V* `$ \2 R8 p+ G9 e" x6 y# {9 u
    Tail Recursion
    . C0 z# S& P# G' Q; Z; R; c% u: w2 H. g  e" R. [# [
    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).) G7 V) ^% C/ W; h/ j
    9 }& w/ c6 s) i! b, p
    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-5 03:38 , Processed in 0.033962 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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