用汇编语言实现递归

沉宝

本文成篇的起因于社长的一条记录 链接
4 s5 ~& [+ X6 O' l1 u
* @  J' I4 Y# T0 L$ j递归是计算机科学中一种解决问题的重要方法。所谓递归，通俗地说就是自己调用自己，它在很多语言和环境下都可以实现。以社长的工作场景为例，根据爱坛上的信息，大概是两个关键词：Unix和汇编。本人条件有限，只能用Linux模拟，汇编也只限于x86汇编。下面就是用汇编语言编写的，用递归方法计算阶乘的示范程序。
3 l8 {$ P6 N* V% t6 l

1. LEN_OF_OUTPUT equ 10
   
2. 
   
3. section .data                           ;
   7 w* K  L" i8 g; |" Y8 d
4.    userMsg db 'Please enter a single-digit number: ' ;
   & C/ Y/ X( u6 D  s
5.    lenUserMsg equ $-userMsg             ;
   0 |" I, N" s1 w/ u
6.    disp1Msg db 'The factorial of '
   - I# r9 r7 U# ]$ ]$ ~. H+ ]
7.    lenDisp1Msg equ $-disp1Msg                 
   3 D3 B: t4 N; ^* g
8.    disp2Msg db ' is '
   0 a  W4 s1 ?, q, q6 \; i3 n; D
9.    lenDisp2Msg equ $-disp2Msg                 
   
10.    errMsg db 'Wrong input. Only one-digit number can be accepted.',0x0a
    
11.    lenErrMsg equ $-errMsg                 
    
12. 
    5 k# l* }# ^( J- f
13. section .bss           ;
    
14.    num resb 1
    # E3 _1 k  k; O: n
15.    result resd 1
    * ^) ^2 A9 x) Q! v1 s7 ?( w
16.    buffer resb LEN_OF_OUTPUT+1
    
17.         
    
18. section .text          ;
    ; L4 x( ]: X' v7 H
19.    global _start
    
20.         
    , H$ M' `- S- K8 y9 \; x/ v& q
21. _start:                ;
    & }) r3 F0 G! g( j
22.    mov eax, 4
    . {( a& ^( D6 c' O* L! S  ]
23.    mov ebx, 1
    
24.    mov ecx, userMsg
    
25.    mov edx, lenUserMsg
    
26.    int 80h
    
27. 
    
28.    ; read user's input
    5 z& C6 ]& s/ e& O! |2 Y5 ~( f
29.    mov eax, 3
    - d6 R+ r8 ?- f' F
30.    mov ebx, 0
    " H# ~* l8 N, z% I
31.    mov ecx, num  
    
32.    mov edx, 1          ; length of input buffer
    % N1 G3 u' r7 \& g7 v* ]$ o
33.    int 80h
    
34.         
    ) }# _5 ]* t! l$ ~% Y" `
35.    mov eax, [num]
    
36.    and eax, 0xFF
    
37.    sub eax, 0x30
    
38.    jl ERROR
    . @8 I! `  f( `: b
39.    cmp eax, 10
    % s: l# i9 F9 W2 z( W
40.    jl DO_CALC
    ! M. D: p# u' Y0 w) I! {# E( u* |
41. ERROR:
    9 m; Y4 {2 x8 l5 C' G
42.    mov eax, 4
    ( o2 L: {5 a; e8 v
43.    mov ebx, 1
    4 b9 W2 X0 n) y) p
44.    mov ecx, errMsg
    
45.    mov edx, lenErrMsg
    
46.    int 80h  
    
47.    jmp EXIT
    
48. 
    
49. 
    
50. DO_CALC:
    $ }! j+ [$ B. H) y& \) Y: k+ x
51.    call factorial
    " N7 i% b6 D1 o0 o) W! F6 e
52.     ; The parameter is in eax. After calling, the result will be stored in eax.
    
53.    mov [result], eax           ; Save the result
    7 r! ^' M; B9 Z3 t, s
54. 
    
55.    ; print result
    ( c6 @! u) D- W# h! M  i2 B
56.    mov eax, 4
    
57.    mov ebx, 1
    
58.    mov ecx, disp1Msg
    7 x# \' \: I: a; S
59.    mov edx, lenDisp1Msg
    
60.    int 80h  
    : I! x( E. [3 c9 |: \) R( O8 K
61.    mov eax, 4
    ; f# E1 l! Q7 E: O& L  u
62.    mov ebx, 1
    
63.    mov ecx, num
    + `) \2 Q" V5 C9 w# q
64.    mov edx, 1
    
65.    int 80h
    / ^9 ^  i9 i' s# T, m" c
66.    mov eax, 4
    ; h) m9 R, f3 [2 L
67.    mov ebx, 1
    
68.    mov ecx, disp2Msg
    ) x3 x* s1 }& W6 w+ N3 v8 h3 Q
69.    mov edx, lenDisp2Msg
    
70.    int 80h  
    
71. 
    
72.    ; output number
    1 N- i$ a8 \/ j! B
73.    mov eax, [result]           ; VALUE THAT I WANT TO CONVERT AND DISPLAY
    
74.    mov byte [buffer+LEN_OF_OUTPUT],0x0a
    5 F# c6 |% C; C" ]8 ^* I
75.    lea esi,[buffer+LEN_OF_OUTPUT]
    1 U  T; s4 ?  Q% W) X+ `2 ~/ c
76.    mov ebx,10         
    $ N8 [4 [3 ^: K  w% y
77. ASC_LOOP:
    
78.    mov edx,0            ; clear dx prior to dividing edx:eax by bx
    
79.    div ebx              ;DIV EAX/10
    
80.    add edx,0x30           ;ADD 48 TO REMAINDER TO GET ASCII CHARACTER OF NUMBER
    6 J. U6 a; ^9 i0 Q3 M% Z( Z
81.    dec esi              ; store characters in reverse order
    
82.    mov [esi],dl
    6 G4 @$ n* I# A
83.    cmp eax,0            
    # E5 Q" A+ o+ m: z, `, M
84.    jz END_ASC             ;IF AX=0, END THE PROCEDURE OF NUMBER TO ASCII
    
85.    jmp ASC_LOOP            ;ELSE REPEAT
    
86. END_ASC:
    
87.    mov eax, 4
    ! ^2 {; A( o# X9 d/ o5 N
88.    mov ebx, 1
    
89.    mov ecx, esi
    
90.    lea edx,[buffer+LEN_OF_OUTPUT+1]
    
91.    sub edx, ecx
    7 i1 L7 T7 H& X& D% ]6 {
92.    int 80h  
    
93.    
    
94.    ; Exit code
    
95. EXIT:
    $ @" q9 B# O. ~2 g
96.    mov eax, 1
    
97.    mov ebx, 0
    7 w. {6 {0 G% M- X0 A4 i# ?( d4 I# N
98.    int 80h
    
99. 
    ; x/ C8 U. S9 K0 O
100. 
     
101. 
     
102. ; Factorial function using recursion
     0 h( L, x$ r, _- {
103. factorial:
     
104.     ; Check if eax is 0 (base condition)
     3 k$ s6 N6 g/ H% r
105.     cmp eax, 0
     . H0 G* j5 g: S7 f
106.     jz end_recursion
     
107. 
     7 c1 c9 i1 r6 U3 E% }3 w
108.     ; Save the current value of eax
     
109.     push eax
     
110. 
     
111.     ; Decrement eax and call factorial function recursively
     ' `8 e8 E! E' u4 t) n4 }
112.     dec eax
     
113.     call factorial
     . ^$ A5 {: y) k2 {
114. 
     4 D% t4 i) z1 y7 z& M' k
115.     ; Multiply the result returned in eax with the saved value of eax
     
116.     pop ebx
     * i. T8 _) B3 ~% ?! V4 Y  F! K
117.     imul eax, ebx
     ' b% B. |# Y7 [
118. 
     
119.     ret
     
120. 
     7 ]% _, m3 M0 Q
121. end_recursion:
     " c; s5 O. p/ N: I% s' A
122.     ; Return 1 when eax is 0 (base condition)
     
123.     mov eax, 1
     6 H0 E0 _9 T$ H: b: U* U( c7 P
124.     ret

复制代码

0 J% x  u. s' {8 D2 @程序在nasm编译器下通过并成功运行。相应的命令行如下，有兴趣的童鞋可以自行验证。

1. nasm -f elf factorial.asm
   
2. ld -m elf_i386 -s -o factorial factorial.o
   
3. ./factorial
   1 |1 k/ L4 C( z* T3 x

复制代码

; \1 q' W; ]4 x% p: |由于汇编不擅长处理I/O，所以程序限制输入仅限于一位数字（0-9），以免过于喧宾夺主。其实程序中真正紧扣主题的就最后一小段：

1. ; Factorial function using recursion
   
2. factorial:
   
3.     ; Check if eax is 0 (base condition)
   
4.     cmp eax, 0
   # P6 R, X2 j, K. v
5.     jz end_recursion
   
6. 
   * h8 ~2 W/ N+ z1 M; N9 y% _0 I! e
7.     ; Save the current value of eax
   
8.     push eax
   3 A% g- X2 l; C2 B( }- |* G
9. 
   
10.     ; Decrement eax and call factorial function recursively
    
11.     dec eax
    
12.     call factorial
    
13. 
    6 C$ m; @% w: r( G% h% A- E
14.     ; Multiply the result returned in eax with the saved value of eax
    
15.     pop ebx
    & S2 ~5 G: E- A+ H- L6 R
16.     imul eax, ebx
    
17. 
    
18.     ret
    
19. 
    8 l1 x# M$ ]8 }  k+ C  x
20. end_recursion:
    
21.     ; Return 1 when eax is 0 (base condition)
    
22.     mov eax, 1
    6 f/ ^+ C- ]' S8 s" k) H
23.     ret

复制代码

可以清晰看出函数在其函数体中调用了它本身。

# l. V! F) W; O" Z' h' s以上证明了汇编语言不是实现递归的障碍。推而广之，所有中低级语言都可以轻松实现递归。某些高级语言反而不能做递归是人为强制规定的，换而言之是原作者权衡利弊的结果。
3 F& |, {/ ~* V: H5 y% m( I3 v
世界上没有免费的午餐，递归在编写程序的时候简洁优雅，但运行过程中要付出极大的代价，甚至有可能是灾难。由于是函数反复调用自己，那么所有的中间结果都要暂时保留在栈（stack）上，直到最后一层函数调用完毕才能逐步清除。这既低效，又不安全。栈式计算是一个古老的概念，它与现代的多寄存器和流水线等都格格不入，难以优化提速。递归对栈空间的占用更可怕，占用量与调用函数次数线性相关（套用复杂度的概念就是O(n)），递归次数多了之后，很容易超出栈容量，从而导致栈溢出。具体到社长的工作中可能还有很多实时任务，一大堆高优先级的中断响应程序可不会等着递归函数运行完了再启动，这会让栈空间雪上加霜。想一想某个核电控制程序突然栈溢出了，那场面，哈哈哈。
. R# D5 Y4 T% V) Y+ Y
这可以解释，为什么条件上有可能，但社长很长时间里都没有接触到递归编程。无论用C还是用汇编，都强调的是速度与可靠性。社长实战出发，不需要知道回字的4种写法。至于Python，整个编程思想都变了，Python假定计算机的计算速度远远超过了需求，编程者无需为性能而操心。 Python语言的设计初衷，也不是为关键任务而生，而是想让更多的门外汉用起计算机来。所以在Python程序中容易见到递归。
0 \$ B% T7 U' U& R! X
/ j! [$ p0 H3 }0 ?, j' A2 E4 Y) F2 ?有很多时候，递归用作概念性算法表达。真到了用代码实现的时候，再换用其它方法。比如说将递归转化成迭代（iteration）。

另外，汇编语言作为一种低级编程语言，在不考虑时间成本的前提下，没有什么是它做不了的。本期课后作业：如何用汇编语言实现继承（Inheritance）和多态（Polymorphism）？请写出示范程序。我们知道继承和多态是面向对象编程（Object-oriented programming）的两个基本点，有了它们就可以实现汇编语言的面向对象编程。

/ ^, _2 l. y& C+ g& y. l8 W0 M# R

马鹿

原来是堆栈或者内存不够用的物理限制呀。
' p/ V- u- l( }
+ }3 d: F( ]+ @* T+ ~9 M昨天看了一眼我们用最新的软件（最近10多年都没接触新版的软件， 客户不用）， 最底层还是汇编， 只不过上面加了很多界面， 让使用变得复杂很多。。。

四处张望

fortran我不知道，事实上c以后的高级语言基本没有不能递归调用，当然实际上的确是有堆栈溢出的危险，但是一般来说堆栈溢出其实是一个很好控制的异常，尤其是现代高级语言普遍使用异常之后。只不过生产环境中的代码，的确是很少采用递归，如果有用一般在验证完成后会转换成迭代循环以减少内存使用和提高速度。

pcb

记得有门课叫 compiler
编译原理？

无言

看标题就感觉是对社长有感而发，果然

晨枫

没有注意到上下文，也可能理解有误，递归的核心或许可以简单化地理解成后向Goto？

但我觉得这里面可能有一个基本的分别：一次性执行的离线程序vs反复执行的在线程序。

科学计算基本上都是一次性执行的离线程序，从begin到end一气呵成，所有递归实际上都在这一次执行中完成，所以不正确的递归可以造成死循环，正确的递归也需要完整执行完后才释放所有的中间结果，内存占用太大。不许用递归是有道理的，所以都鼓励用for loop。
  Z6 f3 G; V, D7 V. o
3 O* A: G7 A, `# Y工控计算大多是反复执行的在线程序，比如每秒一次，每一次执行也是从begin到end一气呵成，每次递归只执行“上一次”和“本次”之间的关系，完事了就释放内存。这是有限计算，不是无限计算，不可能死循环，内存占用有限，只需要本次计算有关的加上上次的结果。这样的计算也是很多工控计算的必须。
  I& i! P0 J: x8 f0 P2 H1 [
- G1 e6 b8 P# |, \  U举一个例子：

" O% x! X$ k4 n1 k( U$ Q在科学计算里，计算数值解需要递归计算，最后比较两次计算之间的误差，足够小了就完事，否则接着算，永远不收敛就死循环了。
+ |/ {. r0 a* O5 M5 U/ ?
在工控计算里，比如说控制量计算，u(k+1)=f(u(k), additional inputs)，这在每秒一次的程序执行里就是once through，不管前后两次的误差如何，所以没问题，也必须递归，否则没法算。但只要过程还在运行，控制要求还在，还真是无限循环计算的，每秒循环一次。

沉宝

晨枫 发表于 2025-1-18 04:21
$ m7 C# `& U& F2 t3 ^9 z没有注意到上下文，也可能理解有误，递归的核心或许可以简单化地理解成后向Goto？
) z& S4 P8 w7 Z* z: G. r
0 U! Y' Z/ C- i* j- e3 W! O但我觉得这里面可能有一 ...

递归的核心就是严格意义上的自己调用自己。
* s# @/ Z' u+ I8 @# {7 C* `3 D
在计算机程序里面，调用一个函数（或者子程序）与goto来goto去的最大区别是调用函数由系统来负责保持当前环境（例如各个寄存器里面的数值），以便调用返回后无障碍继续运行；而goto则是由程序员决定哪些有用的数据需要保持（比如说存储在全局变量里）。系统保持当前环境的方法是在栈上开辟一块临时空间 ，把系统认为有用的信息都存在那里，函数返回后这块临时空间可以被释放。至于for loop，你可以看成是结构化的goto（goto的一个子集），使用它可以减少人为失误。
& D4 s1 q- B; _. s. ~
* `2 ]! x( u3 H% X$ V7 u) w8 m! I5 r回到递归，如果数学模型定义中有函数调用自身的场景，例如阶乘定义为f(n)=n×f(n-1)，那么递归的方法就是在程序中1:1地按定义编写函数f(x)，这样函数的实现代码中无可避免地需要调用f(x)自身。好处嘛编写程序的时候很省心，代价是麻烦都留给了系统。以晨大的水平，肯定可以写出用for loop计算阶乘的程序，但这只是计算结果上等价，而不能称之为用递归编程，或者说晨大找到了递归的有效替代物。

( z  Q) H* y5 m) k8 W至于在工控计算里，比如说控制量计算，u(k+1)=f(u(k), additional inputs)，你可以看成这是一个广义上的递归。但在具体执行层面，晨大自己也说了，每秒一次的程序执行里就是once through，必须保证在下一秒来临之前完事并释放内存，可能容不得任何递归代码。

小结，很多时候讨论递归专指是在编程算法层面上的，而非广义或哲学意义上的。哦对了，广义递归还可以举出什么例子？从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚，……’”

晨枫

沉宝 发表于 2025-1-18 13:26
递归的核心就是严格意义上的自己调用自己。

9 A1 r# Z8 G: i  J1 U! A7 W# F& T/ P在计算机程序里面，调用一个函数（或者子程序）与goto来goto ...

6 H  f$ ~* ~4 B明白了。
. w( ?. i4 H" L$ T% v5 k: R* c8 h! c
递归要是有一个counter，counter计数到了就自动中止，应该也没有内存溢出问题了吧？

pcb

晨枫 发表于 2025-1-19 04:32
, T% P" v1 E" W2 E+ A1 J明白了。

递归要是有一个counter，counter计数到了就自动中止，应该也没有内存溢出问题了吧？ ...

全局变量

晨枫

pcb 发表于 2025-1-18 15:07
5 ~: k3 u& \% {1 m4 p4 i全局变量

嘻嘻，全局变量好啊

沉宝

晨枫 发表于 2025-1-19 04:32
明白了。
2 X+ U! H0 s0 W" {2 G
递归要是有一个counter，counter计数到了就自动中止，应该也没有内存溢出问题了吧？ ...

$ A) C; l9 G/ J9 N0 X9 K4 K
. ~0 w, \  S% Q7 ~恰恰相反，按照定义递归常常用别的方法中止，而非counter（启用counter往往说明你正在做非递归化转化过程中）。例如前述阶乘的中止条件就是f(0)=1，程序不知道要运行多久直到遇上该中止条件。这种不确定性会造成运算规模不可控，资源消耗不可控，对于大的输入值内存溢出的风险很高。

晨枫

沉宝 发表于 2025-1-18 17:07
( N. i7 Q- P& p/ [2 J! ?  `! T+ Q" Q恰恰相反，按照定义递归常常用别的方法中止，而非counter（启用counter往往说明你正在做非递归化转化过程 ...

) n* d6 O! d+ R嗯，明白了，还是需要明确的中止条件，只是有时候这个终止条件可以在不确定的未来。

xiejin77

在编程语言的体系中，汇编语言代表着最接近机器的编程方式，它的本质是对机器指令的直接映射。当我们选择使用汇编语言时，实际上是选择了一种与机器进行最直接对话的方式。在这种情况下，引入面向对象编程的概念，如封装、继承和多态，或是应用Java中常见的设计模式，某种程度上违背了选择汇编语言的初衷。打个比方，这就好比让罗士信学习罗成的罗家枪法一样。
5 ]3 _/ Z8 E7 N: U" a6 \) C/ A
4 V1 ]9 Y: a( H7 Q7 }& t汇编语言的核心价值在于它能让程序员以机器的视角来思考和解决问题。编写汇编代码时，程序员需要直接关注CPU的寄存器操作、内存访问、运算单元的调度以及中断处理等底层细节。这种思维方式与面向对象编程所强调的抽象化、模块化的思维方式存在根本性的差异。当我们在汇编语言中引入面向对象的概念时，不仅会增加不必要的复杂性，还会在一定程度上模糊了对底层硬件的直接控制。
, r+ M: c+ ~# R: v0 J7 p. n
; x2 D2 T2 H, J8 O+ d4 y! Y更重要的是，人们选择使用汇编语言通常是出于对性能的极致追求或者需要直接操作硬件的场景。在这些情况下，面向对象编程固有的运行时开销是不可接受的。封装和继承等特性虽然能提升代码的可维护性和复用性，但这些优势在汇编语言的应用场景中往往显得不那么重要，反而会影响程序的执行效率和实时性能。
. b- G( a- e  N/ r; M5 K
4 G6 F0 {" @9 M( ~保持汇编编程的纯粹性，意味着我们要专注于机器级别的思维方式，将注意力集中在硬件资源的精确控制和优化上。这种专注能够帮助我们写出更高效、更精确的底层代码。当我们需要处理底层驱动、实时系统或性能关键的代码段时，应该充分发挥汇编语言的特长，直接而高效地操控硬件资源，而不是被高级语言的编程范式所束缚。
! V# I  k# f* w. n9 W
3 j5 o" \0 z& H0 f: q/ G因此，我个人认为在使用汇编语言时，应当尊重并遵循其最本质的特征：直接性和底层控制能力。只有让我们的思维方式回归到最基础的机器级别，这样才能真正发挥汇编语言的优势，实现最优的性能表现和最精确的硬件控制。