设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    3 R. R; }( O6 Q6 ~1 A( I
    * x; ?" w+ ~, u! {8 P9 N8 \解释的不错
    % L! b# E/ A7 m0 D# f& G8 v" s* ~( a! q
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。- j, Q% a$ h  h) ?% }' r! K

    " e& S, k$ o3 a* Y 关键要素: e4 {- j# @3 p9 J( m
    1. **基线条件(Base Case)**0 Q7 S' q6 _4 l) D0 d' i0 W' ?
       - 递归终止的条件,防止无限循环2 ?) ?" E7 H% ^( u; \
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - D3 ~3 m' r6 }* Q9 p6 m* d
    1 m9 @% a; B! X4 n( T2. **递归条件(Recursive Case)**. D$ H* a$ K( F0 `3 I, A
       - 将原问题分解为更小的子问题
    + U' U0 R) u* u# V2 {. e- M6 W   - 例如:n! = n × (n-1)!: d: M+ u6 ~1 G& b2 r: W

    ! @4 [& q. b, n 经典示例:计算阶乘1 J* ~( z4 T. t) V- G
    python
    7 F* D* J* e% a7 p( cdef factorial(n):
    / Q% W6 {) I$ j& X    if n == 0:        # 基线条件
    4 }# U; }! c5 n5 S        return 1+ `" Z  `  u8 }# A
        else:             # 递归条件
    % Z; `5 n+ m( x        return n * factorial(n-1)
    * O4 G3 V) w8 b执行过程(以计算 3! 为例):
    8 ~8 V" Q/ s0 x1 gfactorial(3)( w8 B/ U. y4 \/ I
    3 * factorial(2)
    " J  R* _6 H  H- P0 Z, D- B3 * (2 * factorial(1))0 w2 Z$ P. C! o% I3 N
    3 * (2 * (1 * factorial(0)))
    ' G! L8 p8 t+ g5 w8 o2 n3 * (2 * (1 * 1)) = 6; Z; c8 i2 u4 h" j7 O
    8 r* L4 x5 y8 L/ ^* G7 z% t' \; D
    递归思维要点
    8 G6 g, _# Z2 A; {+ g" [1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    0 D' D  H" T; Z! N" l- L8 j4 P2. **栈结构**:每次调用都会创建新的栈帧(内存空间): t/ M+ R) E: S. d3 L4 c% N
    3. **递推过程**:不断向下分解问题(递)+ M8 v9 W5 K$ _8 \, q1 p- \5 f
    4. **回溯过程**:组合子问题结果返回(归)
    ( a( L" |6 o; ^, y# s9 H8 b, b; p* ^2 @% D8 M
    注意事项
    4 L  D+ o+ E8 b3 w) z! q5 B( l必须要有终止条件; E+ |3 W  `8 f
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层): T$ j: {* M9 u# F& K" y
    某些问题用递归更直观(如树遍历),但效率可能不如迭代& {4 F4 B0 }& |" @6 s
    尾递归优化可以提升效率(但Python不支持)& @9 c" a- S5 s5 V- E( ~* {

    8 B) y) _; V# q7 n  u* U+ { 递归 vs 迭代% y" J, r* }" S! X! u4 b4 H* f- D% \
    |          | 递归                          | 迭代               |
    ' p- `- ~7 U5 j. D  @0 L|----------|-----------------------------|------------------|
    * |( N0 ?3 t. r% D! l& o  s# l7 ]| 实现方式    | 函数自调用                        | 循环结构            |" r$ |. A, ^5 }7 H2 z  o
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |% T' g8 E7 v2 M$ C) \* {
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |  {* l  k1 T3 P
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |: v. V/ X  P( o. g

      \' y. l' {2 ]/ f5 B' e8 B 经典递归应用场景6 p9 E2 R* j7 B  k" K' V8 ]& s, P* N
    1. 文件系统遍历(目录树结构)
      l5 R; I. _- w+ g, t3 m2. 快速排序/归并排序算法
    ( T- }! q& K/ w" \3. 汉诺塔问题
    , B3 l5 J! ?" I2 w/ n; m4. 二叉树遍历(前序/中序/后序)' `- T1 f2 |9 q& y% y4 L
    5. 生成所有可能的组合(回溯算法)
    . U9 B, B4 x' K' P4 ?0 R: s& K! i! \, J: o8 a- j
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    16 小时前
  • 签到天数: 3100 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,3 Q5 N7 S& O+ ^) @
    我推理机的核心算法应该是二叉树遍历的变种。! o- |/ `$ W8 C1 @  |) Q
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    6 C8 U6 T' P3 C) }7 F8 \- P& _, oKey Idea of Recursion+ N5 W! t: i% ~* n1 p  W3 ]
    ! c! @) z5 r4 X6 N0 U9 u2 B
    A recursive function solves a problem by:
    , e4 a6 Y. i' i' ~& A" I1 c/ n% W% l$ t. [+ a
        Breaking the problem into smaller instances of the same problem." h# R$ I" t; q! L5 x

    + y$ ?7 ~) n2 `2 ^# G    Solving the smallest instance directly (base case).
      u( e. {" ^8 t4 b( Y9 k% T' ^& s
    ; V8 P# h7 u/ A! y    Combining the results of smaller instances to solve the larger problem.
    & }+ E6 e' q1 E! _+ O1 f- @4 @9 D: j" |
    Components of a Recursive Function9 _3 s0 j0 l; C$ \0 E( Q7 z

    5 ~: X! A- s' J% H' I7 s  |  _    Base Case:5 A9 ]5 @( T" `; G9 h! N
    ( c( v- I2 d6 C* U
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    2 W, |0 Y& x* J% A) [) z
    " G1 D1 w9 B" X2 t7 ]        It acts as the stopping condition to prevent infinite recursion.7 i0 y# ]' S. d% X' K+ A- P
    . R1 y: Q7 D" ?( g3 j# W, h
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    6 W. Y* {0 T7 B  H
    $ U* A5 q) t" ?8 {8 ~% a    Recursive Case:
    ! K# v3 i$ \) N# L. }, v1 w+ Q+ G9 p6 H9 g! u' G( I
            This is where the function calls itself with a smaller or simpler version of the problem.
    2 b7 c! p2 a( ~, J2 B" `& l9 s' L& ?9 l0 P3 s
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).) K) L& K2 J# S$ d; u
    , y9 m4 R2 A6 U8 I5 _. D
    Example: Factorial Calculation
    $ p6 a9 J( e% B) z  D; y( v) v9 b* t+ y5 r  o" z7 f
    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:' m- l  P6 m2 s) h
    8 t5 d# L7 b7 p2 U. h, t5 E3 e' Q
        Base case: 0! = 1
    + }  U4 Z/ I, ~1 z  \/ D: a+ G
    2 H$ o; t6 ^& o8 n2 W  B+ O- R    Recursive case: n! = n * (n-1)!
    ( u/ T9 ]2 r) ~' a1 X- d! ]7 L7 X% c  W( i
    Here’s how it looks in code (Python):$ \" X. @8 ~$ c% `3 `
    python
    * o5 |  i; u* c2 F2 r% q* ~  s
    & C9 F% l2 b' a0 `- X
    % o0 Z8 C' ~) y4 o3 adef factorial(n):
    2 C- V6 t, }( g% r- s    # Base case2 g! G+ @+ g1 d9 j: G) X- P1 G% W
        if n == 0:
    $ T4 L7 [+ \' i( x& J        return 1
    5 N% I) t0 c+ N; K% ]% C/ }' z3 C    # Recursive case
    : X9 C1 e) R  S    else:& l2 w) w1 l4 t) Y$ ]
            return n * factorial(n - 1)
    1 ]/ [% K" t. ~4 {& `; y: i; y' v- `6 d0 y# h$ \) h& i% N
    # Example usage
    ; |5 P) d9 p1 E$ e8 m, i: uprint(factorial(5))  # Output: 1206 E: U0 Z& X* e/ G# Z1 [
    . F7 ]7 `/ M0 m3 s* j" o- O2 M: i
    How Recursion Works/ f+ [9 O( N: t# X
    ( w1 {5 C& v* g) _% C3 \
        The function keeps calling itself with smaller inputs until it reaches the base case.
    & T4 D2 [$ A% s* K# t
      R( i3 M, z+ O0 ], U; k    Once the base case is reached, the function starts returning values back up the call stack.. O% T' ^# O0 Q* }

    ' ~- P4 w1 o+ Z4 u+ Q- w    These returned values are combined to produce the final result.6 O2 f/ [5 @3 G6 S4 I( D

    & `0 u# g' `8 j; cFor factorial(5):
    3 N" h& R- ]+ i/ T% f0 O
    7 n9 Y1 y$ e6 ]: ?: r& p% M* D6 S
    factorial(5) = 5 * factorial(4)$ d" ?9 S8 N/ t/ b8 |% \
    factorial(4) = 4 * factorial(3)
    2 h3 U0 h/ i" T) Y* [) d; \' }factorial(3) = 3 * factorial(2)
    & R9 c2 k4 d0 C; E( z8 m; Nfactorial(2) = 2 * factorial(1)7 k' |6 G' a5 k
    factorial(1) = 1 * factorial(0)
    / ~" E( y6 v1 E* D4 w9 Rfactorial(0) = 1  # Base case
    - v3 ~8 V! Y+ E$ L# m1 B5 z
    # Q( g4 i* b' s3 v0 w7 F7 L8 Q6 @! TThen, the results are combined:
    * ?. ]1 l6 k% w& X9 L3 x/ b
    ' V8 b4 y3 D$ X5 K1 F
    : p  y+ h" R( B5 gfactorial(1) = 1 * 1 = 1
    1 ]9 \, g0 G! e/ |* r( w4 V% Gfactorial(2) = 2 * 1 = 23 a1 z/ \* G1 n7 i1 x( J
    factorial(3) = 3 * 2 = 6
    ' p5 }) a6 M  O1 r$ Zfactorial(4) = 4 * 6 = 24
    7 S% P9 ]& A5 N6 K' L) o4 \0 Q2 Ffactorial(5) = 5 * 24 = 120* A  S+ _4 X( }0 `( N/ V/ ^. c

    " _5 T* G$ F" r+ D# J9 FAdvantages of Recursion
    7 |5 d4 b; X: o1 l  N
    ; `8 u$ g$ @6 _0 e* e# ?/ V    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).
    5 s  ^, Z2 z( }6 V+ ]# r
    8 o. P* @' c# `7 I' v    Readability: Recursive code can be more readable and concise compared to iterative solutions.* {0 w* ^5 A' g" ~
    : H0 @  q  l' R1 j" x; s" ~2 l
    Disadvantages of Recursion
    0 q3 H, _  N+ T0 Y* C$ a- D$ a6 E( C. L/ G' X
        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.
    " \  B+ n, n; e% S
    + Y2 M8 k2 H0 h    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).& z  m8 \  c$ a/ T0 |& y
    ) }5 b. c; r# |7 G
    When to Use Recursion
    1 V7 O5 k! Y( [; J& ?
    ! j5 f+ T2 b6 S- w    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).3 l  A" `- U3 x% W! j5 ?, B

    4 Y' c1 Y4 n% a- P, n  ]* h    Problems with a clear base case and recursive case.
    % N/ @+ T: B4 f! q+ [
    2 z/ u! x/ P! t- Z( lExample: Fibonacci Sequence
    : }1 O2 g" [" M# g" F( ~3 X3 U4 l  s9 |& g$ E* E
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    6 T* N$ A5 C" _% s
    * \, y- k& N* {, {0 g    Base case: fib(0) = 0, fib(1) = 1! j3 K- v2 N; X# y2 r/ L
    + n( K1 G0 B1 b
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ; v2 q9 w- d6 P7 ?9 Q0 F- O" h. l2 N0 C  P, U5 L# ^; r4 Z
    python$ |# f9 _( A6 k
    0 R! T+ ^7 O. H: `9 p* |

    ( k: {# d% {; G1 _6 w0 \7 `def fibonacci(n):
      M) f8 @3 Q: {4 @/ ]$ s; l* w    # Base cases
    ! |5 v4 ?5 J8 {8 W9 S) }$ q    if n == 0:+ |- }2 x; g5 t1 G$ r
            return 0
    : L8 I( \9 G2 w    elif n == 1:
    % E$ w7 J  W# f9 i        return 18 H4 ?( ^! }+ U# |  z4 u; a: z
        # Recursive case$ S# M2 H4 J& c
        else:% o8 n  d3 Z! X# x5 Q
            return fibonacci(n - 1) + fibonacci(n - 2)
    ' b$ d: i1 |. p" d; U
    9 ^+ h+ ^# K" Q/ l) c  S$ p1 \+ d$ {# Example usage
    ! W( G6 d9 I$ N) }2 W) vprint(fibonacci(6))  # Output: 8
    6 o* g* D4 C; @9 I. ^
    " `4 u1 M2 G3 O5 I, O: D* OTail Recursion" \1 J1 t+ g9 Z, |
    3 e4 T1 W  p8 }) q
    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# S+ @8 i1 @
    ! H. S' Y  J4 R; 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-11-23 17:05 , Processed in 0.035283 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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