设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 % ]9 L/ n; B8 L) Z0 [- s

    5 n' z8 M) F2 x7 [5 I! G! c解释的不错
    : R! \) x$ z1 h2 p
    7 ^5 h4 C2 c" [  v6 |: K递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。, o; F; }; y$ W) |! X7 M

    ! x! i" u$ E2 q. z 关键要素
    ! I- n9 p# o. j4 S+ p6 a1. **基线条件(Base Case)**
    5 C  ^& o1 P! f. Z: h; \   - 递归终止的条件,防止无限循环* t! I  Z# k' r
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1; W0 W7 B/ G1 x/ f8 y7 [, m

    % ^8 j" n! ~( F- ]- W2. **递归条件(Recursive Case)**4 B2 V. k' [4 G  v
       - 将原问题分解为更小的子问题
      Y, E! r$ _: T$ k9 w! A6 i   - 例如:n! = n × (n-1)!) t; D; V! W  J3 C

    2 d# S2 h+ j. ]) H/ R( { 经典示例:计算阶乘. b+ s6 M- `% B* \+ M# d
    python& V& r  B5 |! T( E& G1 i( N0 I
    def factorial(n):  Y4 R: B' C: e; a
        if n == 0:        # 基线条件7 O% A( c+ s/ o$ u# D
            return 1
    - T: G: E2 L8 t    else:             # 递归条件
    9 d* T7 ^! X: u# z        return n * factorial(n-1)
    * G& T# Z. A7 ~! A5 a' }. w2 I" @' W' Q执行过程(以计算 3! 为例):
    ; i- e4 R0 v' Efactorial(3)
    , P- I; Z, x8 X: n& o3 * factorial(2)
    . n4 x6 n8 v' N4 n: O5 I3 * (2 * factorial(1))
    - a% D- g  s5 G  F& x0 X% X3 A! {6 L3 * (2 * (1 * factorial(0)))
    ' G; I8 Z) p8 ~2 I1 Y/ Y3 * (2 * (1 * 1)) = 6
    9 D' d+ p  v9 f2 X' C3 J& [% y
    ; J6 d' W" o1 R( r% @ 递归思维要点
    8 J0 l! X, N4 G/ S1 Y1. **信任递归**:假设子问题已经解决,专注当前层逻辑& p, N: B- b0 l3 Z/ s- O6 G5 l
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)/ V6 @) w# t& A/ r: S# P9 r' O
    3. **递推过程**:不断向下分解问题(递)! G1 I  Z! n3 T5 m
    4. **回溯过程**:组合子问题结果返回(归)
    " H5 D/ I, w, e! ^; c6 H
    5 r' v. ]" b4 O  X3 m; {& d) z7 y& D 注意事项% w+ G. I) n( X1 p/ h) l
    必须要有终止条件
    , z; d6 H3 E4 n/ M/ V1 G递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ; h& Y0 P! x# I3 ?# Z某些问题用递归更直观(如树遍历),但效率可能不如迭代6 E. w6 g- k' S6 B4 ?
    尾递归优化可以提升效率(但Python不支持)
    % m# T% b2 J2 \# _4 h4 |/ o5 Q: e6 i1 n
    递归 vs 迭代- m' i4 G5 ^( l
    |          | 递归                          | 迭代               |, f" [1 n: x4 e, X# u
    |----------|-----------------------------|------------------|) w$ W. p8 m) f1 k& Y% a
    | 实现方式    | 函数自调用                        | 循环结构            |
    ; c# `! z9 Y# Z9 |: o' q| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    7 d& @2 S) a5 b5 }8 Q" W; z2 X| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    0 r3 ?7 r7 d8 X. h" ~( B/ q( B| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    . K8 o% L% d: e% L$ m
    $ ^3 U! A8 m2 }. E) u7 m 经典递归应用场景
    - }  v* |& j; ^9 m4 T1. 文件系统遍历(目录树结构)
    2 Y/ t6 h; a* c% [3 S- U2. 快速排序/归并排序算法  G& D& ]7 _* N& A# ]" x9 n
    3. 汉诺塔问题2 _, o) f" J( v! k
    4. 二叉树遍历(前序/中序/后序); f, L4 {, v( z5 z, g6 o+ t/ n7 G# i
    5. 生成所有可能的组合(回溯算法)+ }7 Y# w& J: z2 o( W( Z4 \4 H

    9 z( S+ g) H5 r. _, X试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    4 小时前
  • 签到天数: 3240 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    4 c5 i- l) u0 B' O; x我推理机的核心算法应该是二叉树遍历的变种。
    " y# H: D# F; I& A+ 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:8 l% P) c% R" K, K, i7 v
    Key Idea of Recursion
    * W1 }" @/ R! O" J( T* P2 A& z# c( q/ }0 _6 ^& v! U
    A recursive function solves a problem by:. ]" H5 Q! e: J9 D3 p

    1 ]2 a2 C% ~) i. w/ p& D. ]    Breaking the problem into smaller instances of the same problem.0 R8 w, X$ Y0 |, O

    - K. Y+ i4 {( e6 \* k$ t) C: K    Solving the smallest instance directly (base case).* U) F7 M* M1 }3 [# C, u# V

    4 }. `4 A) O+ N    Combining the results of smaller instances to solve the larger problem.1 n. l) b. r' p: G# ^2 S. {

    , n# D1 b* U$ a7 a2 a$ ?Components of a Recursive Function
      s, {3 b. P, H9 H
    / S  n, q3 J% s5 o0 [6 k    Base Case:
    ; o  K% ~# L4 U5 y- ?
      _* G( R2 S* h4 h" w        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.) r4 y$ \& ?: _5 d

    + J, n( a0 |( @1 {  e; }        It acts as the stopping condition to prevent infinite recursion.
    3 W# i$ _# N3 b
    & \: f* r& ^6 ~        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.1 {  m& f; ?  d8 P
    4 k* e) @% ?' B6 i
        Recursive Case:
    & {0 f0 y) n0 n, R9 |8 k7 d" M8 C" ~$ `) X7 w. J. q! D1 J0 O
            This is where the function calls itself with a smaller or simpler version of the problem.
    0 F' p7 N: l6 X  |& I+ y5 \
      {! T5 X8 f  \: S# y9 I        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 D7 \, q: q, F! H4 G
    ! S9 t: n# \# k' iExample: Factorial Calculation1 \6 f+ V3 \5 B4 k

    ! I  ^, ?8 \5 |$ m& g& rThe 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:% z5 [3 y# N, s$ P

    2 ~6 s/ k8 q) m$ d  `, L5 ^    Base case: 0! = 1$ E5 ?. w" J" `) X- t$ W  h

    4 }4 n/ Y+ N3 ~& ~: U0 t    Recursive case: n! = n * (n-1)!% g, |0 m. e. T3 C  O

    $ v' }* C2 m! rHere’s how it looks in code (Python):
    ' v7 z% r% W/ C7 P$ n) ypython
    9 b1 y  O, F) @1 r' M# X% }) _9 k; c

    9 i; j' D, |! H4 K+ W8 |3 T: wdef factorial(n):7 u8 o( w0 G- o6 _0 H
        # Base case
    7 @6 B% I' s8 m' Z! e- R$ ~* K    if n == 0:. O+ {3 T. h. q3 D7 b" I
            return 1) U' p7 U' p: h# P# S
        # Recursive case2 z( Y" g6 }: D1 ?! J( ?
        else:
    " j# ]  [) ~2 e: K+ w# I        return n * factorial(n - 1)' v% a. C0 I; |: T; o+ Y  Q

      c% H7 j" v; T, K# Example usage
    ) N& E8 M" _- L, m! O' eprint(factorial(5))  # Output: 120) ?9 ]( B3 @) x# G( g1 X
    $ g2 c* v2 C: B. x
    How Recursion Works
    5 O5 T8 @$ k' u% w7 O5 b+ f; n" Z) m" Q
        The function keeps calling itself with smaller inputs until it reaches the base case.2 N1 I% H* P+ ~7 r2 v% s6 D+ p# c

    - x. X+ S" j6 S" T7 \) R+ f  `    Once the base case is reached, the function starts returning values back up the call stack.0 \! d2 L/ [7 k; y& n
    , ?6 ~5 ~0 S* y$ M8 M9 B, S; F
        These returned values are combined to produce the final result.2 W5 P1 x# ?$ j3 B

    0 o6 y9 R# L* ]4 A' X; r* w# GFor factorial(5):
    & ?- u* }/ [+ f" m& S* Y3 S) a+ L  M3 N+ n9 F
    , G" q& \8 i7 v( i: g% J0 Z9 C
    factorial(5) = 5 * factorial(4)
    / c6 s$ v+ o" N) @! Gfactorial(4) = 4 * factorial(3)
    ( M$ [6 z- M) h7 d; i0 }; }! u" pfactorial(3) = 3 * factorial(2)
    ) G7 B5 r+ Z% K) _% @' Ffactorial(2) = 2 * factorial(1)% ^5 ~3 v2 Z& m% W+ s1 |
    factorial(1) = 1 * factorial(0)# R6 Y7 F. R' w# c* w' |1 e
    factorial(0) = 1  # Base case
    ; P" C" n2 b3 X) {6 f  R/ c# r1 f
    % ~) c$ |9 E+ D4 b" ~4 l! b* OThen, the results are combined:
    & M, x! M8 K5 t' C0 m! R4 H8 [8 @. g

    : P& l" R3 R4 \; E' N9 ?factorial(1) = 1 * 1 = 1' Y" w; l( Z" X* U& R
    factorial(2) = 2 * 1 = 28 t: j8 t* |' S2 f4 _" W
    factorial(3) = 3 * 2 = 62 z# Y( m) I* G3 o4 L$ c
    factorial(4) = 4 * 6 = 24" s& I, m* M4 f
    factorial(5) = 5 * 24 = 120& P, {2 p" |1 t! Q' b
    2 H/ j. U. J3 w  q8 h+ v  O2 `
    Advantages of Recursion
    ; S; J0 |: Q: {1 h; L: I: X: d( w! p/ g8 `% l5 i
        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).# K0 R. u& g* X8 Z; l1 \
    8 i% f5 t+ |0 I$ c- x! m+ V
        Readability: Recursive code can be more readable and concise compared to iterative solutions.6 h# C5 P. q7 m! ?' t
    ! Q1 I) R1 E' V
    Disadvantages of Recursion
    9 v$ L; D, L4 E$ Z  z
    8 i+ K. y% e% A, m  y    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.9 @6 v2 J2 H, z, e4 Q+ I

    / _4 g6 L0 u" W' S    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).* q4 p! P: |5 O! \1 a, w$ c. a
    ' B8 }4 f+ n* j- a8 y3 U% q4 v
    When to Use Recursion5 R/ {7 J6 G* r/ a
    9 n/ s$ C; _5 L* Y  D
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    8 G6 t2 }* ^0 \) S1 Q) M' G
    6 p7 _: t2 H; G" A% d# s  j* Y$ U    Problems with a clear base case and recursive case.9 M2 D, @! B+ t( _+ g9 y: @2 l; s, X

    & ]$ B% V5 O: @5 K& dExample: Fibonacci Sequence5 B+ b/ V5 d+ `0 h% _: ?
    ( V) c$ e6 ^  {0 `
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:8 r* L; Z# t4 y( F* M

    ( l) }& U7 ?0 X; C" [4 n    Base case: fib(0) = 0, fib(1) = 1
    , {) a5 G3 `  ^$ ?2 H* |  f! V! |: h% N) ~  y' {% E
        Recursive case: fib(n) = fib(n-1) + fib(n-2)/ e' ?4 V; h. z: Z0 w

      u; X( w1 G2 _! U, o  N; T3 _python# S% a, y& }8 e0 A0 f5 w
    7 U4 m. e" M. S. W
    % \9 A9 A4 d1 t, ~6 d  Z" E6 b
    def fibonacci(n):
    - J$ `/ B& ^) u( w: m    # Base cases
    " D& Y8 \6 Z. P  L/ z    if n == 0:
    4 L$ n, z9 Z1 T! h5 N. v        return 0
    % b# j3 \2 Y( @6 u2 b: N0 C* f    elif n == 1:' \' `* [- k4 g. Y! |( ~
            return 1, {5 u6 Y9 G" Z+ h4 X
        # Recursive case' H0 _1 A! p3 S' S) n5 n6 y
        else:' a" w  }! O# b4 d7 f7 ]/ g1 C
            return fibonacci(n - 1) + fibonacci(n - 2)' |+ z! o( }8 v# [* I

    6 v( u* @* h# W5 U4 H( {5 W7 |# Example usage* v( |' d- E$ ~  \7 i1 d
    print(fibonacci(6))  # Output: 8
    6 D7 b! K5 d, F- h( M9 v! v
    6 T2 A2 j! i8 A- P0 h3 VTail Recursion2 {. j  ~) ~+ k

    0 z" \- Z! t2 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).
    2 g9 R3 [0 ], @' c$ d2 p5 a  X% Z4 H( g7 X
    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, 2026-5-16 10:36 , Processed in 0.061109 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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