|
本文成篇的起因于社长的一条记录 链接9 ~% Q- e; @9 a
" x0 w& ^6 N' d+ c+ M. R
递归是计算机科学中一种解决问题的重要方法。所谓递归,通俗地说就是自己调用自己,它在很多语言和环境下都可以实现。以社长的工作场景为例,根据爱坛上的信息,大概是两个关键词:Unix和汇编。本人条件有限,只能用Linux模拟,汇编也只限于x86汇编。下面就是用汇编语言编写的,用递归方法计算阶乘的示范程序。
- H6 U5 d: q. w% t& v- LEN_OF_OUTPUT equ 104 o5 c7 N) q0 n6 h# Z
- ; A2 Z) Y: B8 ]
- section .data ;0 `8 \9 A9 Y& R) A2 B
- userMsg db 'Please enter a single-digit number: ' ;! T& H* T Y# |$ i$ {
- lenUserMsg equ $-userMsg ;
% W8 N9 k1 \; ]+ r) O - disp1Msg db 'The factorial of '
" `/ t8 L+ ^! h; ^9 U% ^% t$ P - lenDisp1Msg equ $-disp1Msg
# e0 }( ~! ?* j' N, F6 L" [ - disp2Msg db ' is '
3 @$ g8 z4 j+ A - lenDisp2Msg equ $-disp2Msg
7 @6 j* w. U# U - errMsg db 'Wrong input. Only one-digit number can be accepted.',0x0a
& t& \8 X/ r! _ - lenErrMsg equ $-errMsg % A" N! z; k0 J6 k+ J9 Q
- : H& @/ Z5 Y$ e4 g) M
- section .bss ;& w- h4 v: [' R: i% }5 o
- num resb 1
" _/ k0 B- ^/ j6 J% P2 P: I& R' G - result resd 17 k: _: N9 `( E# k& R3 X- T
- buffer resb LEN_OF_OUTPUT+1
6 [0 M8 v! m P- e- { -
0 b( u8 \( s0 e$ }3 v+ C" j. _) I - section .text ;) s6 ?0 {. D/ K5 h6 C, _
- global _start
1 ~9 U2 H$ X7 f v - 5 [& \; I5 {2 w% J/ U5 l1 V1 P
- _start: ;
0 E# r* I' I. D" x - mov eax, 4" g3 l3 H }2 T* j/ n
- mov ebx, 1; E5 z* U) [2 H! X; v- X& O
- mov ecx, userMsg! {5 o) r D+ ~& V6 S
- mov edx, lenUserMsg
0 M- K9 D; s1 _8 a: p - int 80h/ y" g$ O$ g1 o0 j
. a2 ?' h K) n. D* w: m' g- ; read user's input
, ?0 g' j" [3 n - mov eax, 30 }( X6 j! J( S& @
- mov ebx, 0
8 q% b7 y* L4 v! I) Q8 u - mov ecx, num
8 T4 k( |! R0 W6 v0 R# D# G - mov edx, 1 ; length of input buffer
$ s' w- o& p5 W( F: Y - int 80h
& _5 A/ v; }1 a% l* |; R% n' V' p - s, r5 R6 p: ^$ j- m1 q. @( {& [
- mov eax, [num]/ f: v0 h% i' B( o! T# A" L( a
- and eax, 0xFF
3 ?: i' `4 b6 d+ f! N# n9 a- l - sub eax, 0x30
/ \ h c, f7 q& ^, E - jl ERROR$ ^" X( X R9 ^8 t$ c
- cmp eax, 106 C/ g) M( m) q5 \/ h1 m/ _% i; a
- jl DO_CALC
$ p( J X2 ^, c0 T - ERROR:
' |! n- ], J. s4 ~* s6 e - mov eax, 4" \8 l ^' w% ?5 p! c
- mov ebx, 18 ] o7 q! A9 F4 e
- mov ecx, errMsg/ k% C2 c0 p/ p$ z3 |" _) r
- mov edx, lenErrMsg. U) F7 j8 q3 b/ d. U) V7 X% l
- int 80h
% k) i* Y6 W1 p9 N$ Z) E - jmp EXIT
% n; o4 j# f, J+ i1 {0 y) ? - 7 y6 v* A4 k, @! u i1 H
( W5 g3 |. d* M3 I$ @7 b( w, s s- DO_CALC:
1 \! e/ ? p. w2 O6 _) m - call factorial' _0 ?+ H; d7 q+ t8 P m* x
- ; The parameter is in eax. After calling, the result will be stored in eax.
6 w1 T8 C0 f( V. S9 e, d0 R4 U, U. Q" x - mov [result], eax ; Save the result# v# i/ b" f* n
n H$ d: [' P/ Z J8 |2 p, _- ; print result
; k: M# b5 T2 d. K - mov eax, 4
5 H. G" {; n& I; U6 t. K( o - mov ebx, 15 f: X5 i, I2 c5 }* [
- mov ecx, disp1Msg' _4 G3 ?0 T% E ?2 S+ F( n
- mov edx, lenDisp1Msg
5 O% w/ X9 c# u( [: u& v - int 80h
8 I7 O; S4 V# |; t, b2 b! p& P - mov eax, 42 ~2 \5 O/ Z! q* r* l
- mov ebx, 1
+ e5 Q% S' E7 y* l0 \7 @ - mov ecx, num0 ]8 O7 q: w! u2 ]
- mov edx, 18 L8 E. a) ~7 o
- int 80h
s/ n, Z4 T; Q' r/ o - mov eax, 4
( ^+ W7 q: q2 ?, V - mov ebx, 1 I' d7 W: V! T6 y$ c- [" S
- mov ecx, disp2Msg
6 M3 C' n2 [) _! O; Z1 _0 j - mov edx, lenDisp2Msg
$ ^0 h z2 t8 S* B9 w/ p& q - int 80h & u! S6 S% N7 w" A& M: [9 T0 e; D# a
- - S9 a1 Z& W4 z1 T" `
- ; output number
# v9 V. j, Y* @ w4 q; j - mov eax, [result] ; VALUE THAT I WANT TO CONVERT AND DISPLAY, T6 W6 d; X9 _! R5 w
- mov byte [buffer+LEN_OF_OUTPUT],0x0a
/ d# K- [3 H( W5 W - lea esi,[buffer+LEN_OF_OUTPUT]
- G6 y8 H+ ^1 ~" X* n9 u - mov ebx,10
2 {9 I. ]# Y2 r+ q7 D3 B& ^ - ASC_LOOP:
9 Z5 ]* e7 A9 N/ A9 o+ G - mov edx,0 ; clear dx prior to dividing edx:eax by bx0 K3 T5 f$ F# {+ ]4 G4 a4 ?
- div ebx ;DIV EAX/10$ i) @, F2 G0 E0 ~
- add edx,0x30 ;ADD 48 TO REMAINDER TO GET ASCII CHARACTER OF NUMBER
) | p, B5 z/ w) W1 p$ u1 a3 l - dec esi ; store characters in reverse order) r' ^% k1 p4 C' z {/ z7 n
- mov [esi],dl
6 c0 ?% Q( w0 _ - cmp eax,0 ( j2 J7 k* h$ @4 W8 ]2 Q- l( q
- jz END_ASC ;IF AX=0, END THE PROCEDURE OF NUMBER TO ASCII+ @, G2 [2 U7 s1 F, O
- jmp ASC_LOOP ;ELSE REPEAT
6 E ]0 Z: C1 O8 T. S$ V - END_ASC:
$ G0 w; e8 B# b1 R - mov eax, 4
. |4 G4 D8 ]! Z9 B- x - mov ebx, 1
: W+ P, E. |( ^+ b$ K - mov ecx, esi
: O5 K9 g( O' ^, v - lea edx,[buffer+LEN_OF_OUTPUT+1]$ r8 N+ B9 P7 b3 {& a* k
- sub edx, ecx
% \, O% b1 h0 }4 \- E - int 80h % w$ a* I+ G& O/ Q. s
-
0 F% F/ O! [& N- p, }3 ^4 @) J$ s - ; Exit code
( U0 |* m4 b5 S& z X - EXIT:
, D9 y0 e+ o) ?% J9 e" C- Z - mov eax, 1
! ]. q5 a/ F$ ?# Y" T2 W - mov ebx, 0 R- m7 G# Z0 \, Y* P5 X: Z
- int 80h* H6 x1 N9 @, g, T
" N; H; o) q5 R" S7 J2 S$ p
0 r) ^* p+ B h2 T" X" l9 ^! T- + x1 W# w9 h8 U$ ^+ }& T
- ; Factorial function using recursion+ S" Z+ \% d8 A5 j9 S) M7 G( Y4 G9 t
- factorial:
% W1 W+ G+ j0 B' K' \, R - ; Check if eax is 0 (base condition)- g9 q7 l7 b) N
- cmp eax, 0
, S$ J5 Z& X8 D ~/ t! Y - jz end_recursion- @! \4 @6 y/ B j8 U3 ]& `
8 p' i' H. J" x* ~2 `% D- ; Save the current value of eax( |4 l& M+ H- D8 X$ k" W* l8 R
- push eax0 T7 F4 X1 z5 ~' d, F0 f7 x
- / c+ s: g; v4 N2 n! \( j$ m$ a
- ; Decrement eax and call factorial function recursively q" |$ O" K( p; |( p h
- dec eax# B& {" g* U; [3 e
- call factorial
+ K/ o' z6 x3 @* J2 P - ) a2 t& J$ s! z" b' q$ H
- ; Multiply the result returned in eax with the saved value of eax8 N p/ `8 A' l* u7 `8 e
- pop ebx
8 T% V2 {+ o- q j, `7 K - imul eax, ebx; b2 s9 d3 W( A. i$ O
# A6 P o( Z6 y& y- ret
( ^1 P8 i- K: j- t: A6 j: F9 W' q
@8 M; p, t3 N- end_recursion:( ]. y) N! z& i( Q# w' p
- ; Return 1 when eax is 0 (base condition)9 m% l* G9 {, _) t3 u
- mov eax, 15 f! W9 c6 `7 c+ {
- ret
复制代码
+ y/ A$ E* {& m" t2 w/ ]程序在nasm编译器下通过并成功运行。相应的命令行如下,有兴趣的童鞋可以自行验证。7 y2 I/ L5 `- `7 O
- nasm -f elf factorial.asm; C) l& a+ }) Y. h( I( J
- ld -m elf_i386 -s -o factorial factorial.o9 d9 [5 u$ c4 ]# Y$ a
- ./factorial; `; A; B$ H2 l! r$ ^
复制代码
1 J% G8 t) t$ C' Q由于汇编不擅长处理I/O,所以程序限制输入仅限于一位数字(0-9),以免过于喧宾夺主。其实程序中真正紧扣主题的就最后一小段:2 B L) w7 o. U! Y$ @( P
- ; Factorial function using recursion: b" R3 g, N' a, \0 A+ p; U
- factorial:
7 X) d) o7 R* n8 |7 ]' `0 v - ; Check if eax is 0 (base condition)* U) K! r% J, }3 @; z. t
- cmp eax, 0
/ l" o2 S# z' M) {& w' Y - jz end_recursion2 M) v$ r) `! P, X m
- ; C8 u9 w0 @4 i; S& @( C I; ]
- ; Save the current value of eax
! u5 x) w5 P6 o - push eax
) l P- v6 L c
6 y# k& |- _$ G9 _$ d% q) ^: C- ; Decrement eax and call factorial function recursively
3 n" d7 {& a$ q9 W3 Y - dec eax
- u! D6 D' u# i9 j9 D6 k9 E' S - call factorial; J8 Y! c, [" m, W( t# L( d
0 r- i9 `# x% J2 q, t" g- ; Multiply the result returned in eax with the saved value of eax
* }8 r& `# q, G3 o* p- N- f4 D S6 ^ - pop ebx1 x2 ]: v" H' _3 n. x
- imul eax, ebx
# m A" [: o5 h l
1 X' t) N5 ]; c- ret
) R; T5 z: H, L. T1 J" Q - ( C. z3 ]6 j' m9 D0 X! x' D
- end_recursion:
- J! v+ X0 L) j1 J* x- D - ; Return 1 when eax is 0 (base condition)
1 i4 U0 [% J$ P" X- v" p) o% i - mov eax, 1' Y3 j( Y& |& i* k% T5 |
- ret
复制代码 可以清晰看出函数在其函数体中调用了它本身。
! t4 @3 C7 t" d7 [, A
H& k5 c* P$ o' u以上证明了汇编语言不是实现递归的障碍。推而广之,所有中低级语言都可以轻松实现递归。某些高级语言反而不能做递归是人为强制规定的,换而言之是原作者权衡利弊的结果。
( \5 z7 c% n' U7 p- v
h8 y, N. e0 I7 K8 J世界上没有免费的午餐,递归在编写程序的时候简洁优雅,但运行过程中要付出极大的代价,甚至有可能是灾难。由于是函数反复调用自己,那么所有的中间结果都要暂时保留在栈(stack)上,直到最后一层函数调用完毕才能逐步清除。这既低效,又不安全。栈式计算是一个古老的概念,它与现代的多寄存器和流水线等都格格不入,难以优化提速。递归对栈空间的占用更可怕,占用量与调用函数次数线性相关(套用复杂度的概念就是O(n)),递归次数多了之后,很容易超出栈容量,从而导致栈溢出。具体到社长的工作中可能还有很多实时任务,一大堆高优先级的中断响应程序可不会等着递归函数运行完了再启动,这会让栈空间雪上加霜。想一想某个核电控制程序突然栈溢出了,那场面,哈哈哈。
# v; D* d+ g6 }; }; e& b* d) ?0 d6 L8 z a# p# Q
这可以解释,为什么条件上有可能,但社长很长时间里都没有接触到递归编程。无论用C还是用汇编,都强调的是速度与可靠性。社长实战出发,不需要知道回字的4种写法。至于Python,整个编程思想都变了,Python假定计算机的计算速度远远超过了需求,编程者无需为性能而操心。 Python语言的设计初衷,也不是为关键任务而生,而是想让更多的门外汉用起计算机来。所以在Python程序中容易见到递归。4 M9 {) m& p0 n
7 y; Q4 ^' D7 o, M有很多时候,递归用作概念性算法表达。真到了用代码实现的时候,再换用其它方法。比如说将递归转化成迭代(iteration)。6 Q! p6 o, z( G& h7 \/ b% s9 e; R
1 a! i- A5 m, F
另外,汇编语言作为一种低级编程语言,在不考虑时间成本的前提下,没有什么是它做不了的。本期课后作业:如何用汇编语言实现继承(Inheritance)和多态(Polymorphism)?请写出示范程序。我们知道继承和多态是面向对象编程(Object-oriented programming)的两个基本点,有了它们就可以实现汇编语言的面向对象编程。
& n4 D# E+ M5 }* i% M5 @6 g' T. G; m
|
评分
-
查看全部评分
|