设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 0 A7 z9 z' j* L" p) i

    ) x& j' V) N( B# }3 i9 m解释的不错. j8 I4 `9 O2 K$ \' D! }( D
    . }1 L( ]8 F7 N1 ~) Y
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。' b4 z7 j' G% q. l% r
    # F% h' j* H. Y
    关键要素
    7 ?+ @) U: H8 E# Y' q2 w2 `, Z1. **基线条件(Base Case)**
    . A; n/ R2 N2 p- ]5 A  w+ @   - 递归终止的条件,防止无限循环
    3 w7 N- Y* f% G   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    8 P3 F4 J  G9 O# T2 y% J; J
    ; a5 B/ Y& h# N5 F+ L9 L, m3 ^2. **递归条件(Recursive Case)**
    - \: d! q) [, O4 f; }9 V   - 将原问题分解为更小的子问题
    * m  ]5 `1 x1 e+ Y   - 例如:n! = n × (n-1)!" I8 u- h- ^5 T" C( \- y

    : `# Y# I$ i; t! C) G! c 经典示例:计算阶乘) K4 Q4 b& b- J  y
    python7 @6 y- a9 O( J$ N; @" S
    def factorial(n):
    4 {9 M0 s+ O- Y" D* @    if n == 0:        # 基线条件4 T9 ^/ C5 z: E% v. T
            return 1
    & u+ k$ a. U4 o' \) n    else:             # 递归条件
    - f. V+ W4 y7 O6 n4 ?        return n * factorial(n-1)
    5 P6 `$ r9 m( a) X+ i执行过程(以计算 3! 为例):
    ) p" ?. F9 n7 Xfactorial(3)
    , X; O, h$ p; u" H  _" r3 * factorial(2): ]6 l4 B  g/ Y& @# v/ o
    3 * (2 * factorial(1))
    / o6 M; z1 e; T. p2 d  K( F3 * (2 * (1 * factorial(0)))" l, u+ M: \% O9 m/ K. D) A; h/ r1 _' j
    3 * (2 * (1 * 1)) = 6
    & @7 G6 B% i" D6 l
    / A1 @: N$ k- u# Q( m! {2 ? 递归思维要点
    / O( j6 f% ?* @& E7 N8 }1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    5 r1 h+ b; w* B3 {2. **栈结构**:每次调用都会创建新的栈帧(内存空间)/ Z8 {+ ~5 d3 p' q
    3. **递推过程**:不断向下分解问题(递)
    ( W& x0 w3 E5 ]+ M( q4. **回溯过程**:组合子问题结果返回(归)( z" Y8 G4 d% y$ ?0 T* w* r

    % q# k- s5 ?1 S( X& H 注意事项8 H1 i( n4 F' H# ?8 D/ R
    必须要有终止条件( w' |4 |6 a9 z3 t2 ?8 y* g
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    5 |, H: }: R, X, O某些问题用递归更直观(如树遍历),但效率可能不如迭代9 e5 W1 ?% w2 p0 D" L7 @
    尾递归优化可以提升效率(但Python不支持)2 @" _- x5 P* \' d) N

    9 o7 ~$ \' Y( P1 X 递归 vs 迭代3 M+ ?2 _& }' ?9 k
    |          | 递归                          | 迭代               |% U. `6 I/ E9 A$ ]
    |----------|-----------------------------|------------------|
    & e  T- k6 g( F- Q% r% u/ M| 实现方式    | 函数自调用                        | 循环结构            |
    $ C6 n7 ?# |- u# R7 || 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |' ]' h; X- V- k- F- z7 W" \
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    $ I$ `0 c5 S+ f| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    0 K4 R& g' J. w3 F" B* [( n7 }* G
    5 `7 Z( G+ e/ [6 W; Q9 t: N' F 经典递归应用场景
    $ d' X! z. ~7 N' o2 t1. 文件系统遍历(目录树结构); B1 l7 k! ]- U- x' H
    2. 快速排序/归并排序算法0 _4 k' @) j+ ~6 m4 w8 \7 B
    3. 汉诺塔问题
    ! h8 ?3 n3 U. m: m2 f4 V9 N8 I4. 二叉树遍历(前序/中序/后序)
    ' M; P, M& h* w# `/ T5. 生成所有可能的组合(回溯算法)+ ?; y* [  {% [+ p

    ( b( i8 K+ y1 K. L! u试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' O7 I5 P  U: r+ o! O/ C
    我推理机的核心算法应该是二叉树遍历的变种。
      u; D+ R' p) R# x1 R另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:1 Y4 Z, n" _' q7 u" G8 S; R
    Key Idea of Recursion# s$ v1 s# U2 C) i& |6 l
    : `/ `. D. ~: h, Z
    A recursive function solves a problem by:
    3 V  I/ n5 G9 c. {
    3 f( X+ t5 S# a. c6 ^) Q    Breaking the problem into smaller instances of the same problem.
    3 Z. _) _8 \$ [" f: b6 u
    / N3 v! |4 o. x# B    Solving the smallest instance directly (base case).
    2 A9 w3 P9 E7 e7 Q1 U
    1 b0 M* R; s2 O/ I. L    Combining the results of smaller instances to solve the larger problem.; r7 O0 U& [4 r- C# N( w) {
    * v0 j# J! p5 ?: V- E% d  z
    Components of a Recursive Function
    , D0 H; I& [/ o: b9 |4 `0 c  [% ]' I. c; U$ R
        Base Case:2 l. g1 \& |1 V2 U3 t( \# O+ M
    5 M% r9 r  r* v) ~$ u0 I, I
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.' B$ e% o" o' N& j
    - I1 G) H7 t& Z6 u
            It acts as the stopping condition to prevent infinite recursion.
    + T% ~( q' ]) @4 Q# \, @
    1 j/ d5 x. |3 I# C6 v9 F8 y; U        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.3 Z! r! T5 `7 j' V7 e: E3 u

    3 P! i/ s& K! {" g- e- L8 H/ w4 ^    Recursive Case:
    % W& M0 o- ^, l' D: c3 d( w/ A. U8 A; m6 `$ S5 ~( Q& o, b
            This is where the function calls itself with a smaller or simpler version of the problem.
    7 F# I/ A& k; a1 K8 a2 C' s0 W! m( H" M! \1 ?
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ( K, M! x6 ]: ]. h4 R4 Z+ Z) C# V4 S7 l
    Example: Factorial Calculation
    0 l! G, Q- S1 }# Y7 I! T
    ( L) g# v: e1 q' y4 L5 F1 C  MThe 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:/ v6 j; V, u' d
    # _0 u3 g1 h+ y- Z* n# [/ e: b, Y
        Base case: 0! = 14 @( e' I$ ~" w  T
    5 R9 @0 B) G# ^2 x* c. @0 e
        Recursive case: n! = n * (n-1)!
    * d2 D2 T; F& V& w. g3 r1 m. S" H, Y: m) y# m, q% T
    Here’s how it looks in code (Python):
    / {' U8 D* j( g. v1 Bpython
    " K5 Z. R" Q5 W8 m, Z
    1 }* X$ V( r/ ~+ x7 k6 m0 |
    0 D2 @0 }( N4 ^, y$ M% Xdef factorial(n):
    & B4 Q9 p6 C1 w2 `' c+ I    # Base case
    3 b, X) c/ E. o/ a4 V* T; G    if n == 0:/ u  c# P: M: |$ F  }% O; d
            return 1$ m+ M$ v9 b- P7 k2 M1 D
        # Recursive case0 B& [1 U; g& @" Z1 ]" J# V: U/ r) |
        else:, d# L7 w5 G$ T3 e0 v' N
            return n * factorial(n - 1)) U: k5 w; N& K( e( R

    9 n" r! S) d  R# b# Example usage- m" f  L1 u9 W/ @( @; C, m
    print(factorial(5))  # Output: 120
    # ], I/ O0 B6 X1 p! D. _
    5 Q+ R  O$ a+ V* ?5 z, _How Recursion Works
    " Y, T: _, ?- B. e# @9 f' @$ d
    . q& r$ \; Q# X* l    The function keeps calling itself with smaller inputs until it reaches the base case.
    : ~$ b3 z5 J  \, p$ j3 Z+ F9 V; a+ C9 H* l3 Z$ y1 U- q
        Once the base case is reached, the function starts returning values back up the call stack.
    ! I( H* @0 f" u2 C* D
    + X% v1 I4 f* q8 K, n# i3 Y    These returned values are combined to produce the final result.3 f# h; \8 k2 S: n5 p) c# K  K* _6 s
    , A( z6 _1 j! |5 r
    For factorial(5):& v9 e$ s6 Z3 m  [: q, \
    . B( J8 V8 C/ Y; S( P, j( k7 O) ^
    : [( \& L+ G5 W; i5 y0 N
    factorial(5) = 5 * factorial(4)! n: L* s6 R+ h
    factorial(4) = 4 * factorial(3)
    1 B3 ^* q$ M8 o% q  l/ B1 u* Q$ Y* Nfactorial(3) = 3 * factorial(2)
    1 d3 D2 U. M5 {. S2 a, M/ p  ^factorial(2) = 2 * factorial(1)! [" e6 d# X6 q. J
    factorial(1) = 1 * factorial(0)9 {* ^$ N8 n/ [4 K! |" C
    factorial(0) = 1  # Base case
    ) D; C* C) s1 K2 K& D* s4 B! @2 M8 S9 ?* h1 a6 U1 \& q7 C* c/ `$ M
    Then, the results are combined:
    : D  _; v, M$ r4 X% d& e- L4 R/ {
    ( t- r1 \0 ^' r6 C9 {! [% O3 V$ n5 D* a4 S' u5 R4 P5 l' C
    factorial(1) = 1 * 1 = 1
    % V! C8 i" H1 E( L$ R2 Gfactorial(2) = 2 * 1 = 2  ~& Q. h) c. \7 E1 t% Z1 G7 o
    factorial(3) = 3 * 2 = 6% P3 x0 x3 q2 K& f- Y
    factorial(4) = 4 * 6 = 24
    / b' L" S! Z# I! H- D7 e/ ffactorial(5) = 5 * 24 = 120# f# I+ g( _3 d9 X) O1 H8 C, A5 ~2 L

      q# K* [8 A0 w: X% `: \* }Advantages of Recursion3 n) U$ U5 O  ^% ]# i7 V' A
    0 n# }) W. C$ Z4 Z
        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).
    $ c4 i: T+ y& N$ e
    $ y1 n7 n# a; t( i    Readability: Recursive code can be more readable and concise compared to iterative solutions./ Q& ^/ r+ o7 J" R6 X

    - C9 P0 l/ n- m# HDisadvantages of Recursion
    ; K6 x- i0 l5 i0 l3 p0 o4 R) X- w* ^' C" n5 F/ n9 G
        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.
    : R6 Z$ q. L0 O! g  k7 K6 T, M4 ~+ G# @# L% M4 J
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    % w) G4 H) c: ^2 X- v
    5 M" B: s9 `7 E% @When to Use Recursion1 C# b- E3 D) v) `, q+ u! L
    7 Y# x0 K% L& g* v
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    % d& N/ F0 G2 E# }* T7 M! n
    # G. [! ~1 y6 S) d" M    Problems with a clear base case and recursive case.
    + f6 h4 i7 M) ~+ W) U
    ) B6 O( X' J( V7 ~$ iExample: Fibonacci Sequence! d" i3 X& {% B$ w+ X8 E" p
    4 N& e) ?( `! m9 I& j4 h& S/ i
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, W2 C9 Q8 N/ ]+ f( T) h

    8 |5 L2 w5 m3 H; H; i    Base case: fib(0) = 0, fib(1) = 11 C: A' p$ x; z. X& g
    + g2 Q1 |2 x* k
        Recursive case: fib(n) = fib(n-1) + fib(n-2), [; h$ @. x/ E4 M- O, s+ g

    * f1 z0 F! J5 A  V% Jpython
    + `8 V) c* r# `3 h8 Z# d1 T) B  I2 y$ N

    + S. B/ {! U2 Cdef fibonacci(n):
    ; A* a- ?7 z9 Z0 J" B+ e/ y    # Base cases
    ; g  R- D5 J+ k    if n == 0:3 A- f* {3 n1 h6 L, l
            return 0- T  y1 }4 g- u# p' T3 ?9 A
        elif n == 1:- C, Z9 M4 ^" ]; y
            return 1
    + t+ o9 C  t* f2 P  Z% I    # Recursive case; `' R; v  X9 }6 ~' j
        else:: }7 p: ], z& Z  U
            return fibonacci(n - 1) + fibonacci(n - 2)" F* S: G* F/ l0 G& O4 }

      q9 h) z$ `8 Q) B+ ]# Example usage
    $ I& \1 l% N3 S8 M$ |. s$ e1 @! yprint(fibonacci(6))  # Output: 8
    ; t8 o* U. i5 T( w- f
    / |+ H. m. z4 L% E& Q; iTail Recursion
    # i2 @3 k) W9 Z& y1 \4 ~2 d$ V0 g! e- M4 ?8 \; e$ S
    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).2 a3 ~* e" t$ J* S6 ^

    & K2 T: t/ m; O. dIn 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-2-12 09:09 , Processed in 0.060509 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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