Рекурсивная процедура — это процедура, которая вызывает сама себя. Существует два вида рекурсии:
прямая;
косвенная.
При прямой рекурсии процедура вызывает сама себя, а при косвенной рекурсии первая процедура вызывает вторую процедуру, которая, в свою очередь, вызывает первую процедуру.
Рекурсию можно наблюдать в многочисленных математических алгоритмах. Например, рассмотрим вычисление факториала числа, который задается следующим уравнением:
Fact (n) = n * fact (n-1) для n > 0
Каждый рекурсивный алгоритм должен иметь конечное условие, то есть рекурсивный вызов программы должен быть остановлен при выполнении определенного условия. В случае факториального алгоритма конечное условие достигается, когда n = 0.
Следующая программа показывает, как факториал числа n реализован на Ассемблере. Для простоты примера мы вычислим факториал числа 3:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
section .text global _start ; объявляем для использования gcc _start: ; сообщаем линкеру входную точку mov bx, 3 ; для вычисления факториала числа 3 call proc_fact add ax, 30h mov [fact], ax mov edx,len ; длина сообщения mov ecx,msg ; сообщение для вывода на экран mov ebx,1 ; файловый дескриптор (stdout) mov eax,4 ; номер системного вызова (sys_write) int 0x80 ; вызов ядра mov edx,1 ; длина сообщения mov ecx,fact ; сообщение для вывода на экран mov ebx,1 ; файловый дескриптор (stdout) mov eax,4 ; номер системного вызова (sys_write) int 0x80 ; вызов ядра mov eax,1 ; номер системного вызова (sys_exit) int 0x80 ; вызов ядра proc_fact: cmp bl, 1 jg do_calculation mov ax, 1 ret do_calculation: dec bl call proc_fact inc bl mul bl ; ax = al * bl ret section .data msg db 'Factorial 3 is:',0xa len equ $ - msg section .bss fact resb 1 |
Результат выполнения программы:
Factorial 3 is:
6
Оценить статью:
(12 оценок, среднее: 4,08 из 5)
Загрузка...