Рекурсивная процедура — это та, которая вызывает сама себя. Существует два вида рекурсии: прямой и косвенный. При прямой рекурсии процедура вызывает себя, а при косвенной рекурсии первая процедура вызывает вторую процедуру, которая, в свою очередь, вызывает первую процедуру.
Рекурсию можно наблюдать в многочисленных математических алгоритмах. Например, рассмотрим случай вычисления факториала числа. Факториал числа задается уравнением —
Fact (n) = n * fact (n-1) for n > 0
Например: факториал 5 равен 1 x 2 x 3 x 4 x 5 = 5 x факториал 4, и это может быть хорошим примером демонстрации рекурсивной процедуры. Каждый рекурсивный алгоритм должен иметь конечное условие, т. Е. Рекурсивный вызов программы должен быть остановлен при выполнении условия. В случае факторного алгоритма конечное условие достигается, когда n равно 0.
Следующая программа показывает, как факториал n реализован на ассемблере. Для простоты программы мы вычислим факториал 3.
section .text global _start ;must be declared for using gcc _start: ;tell linker entry point mov bx, 3 ;for calculating factorial 3 call proc_fact add ax, 30h mov [fact], ax mov edx,len ;message length mov ecx,msg ;message to write mov ebx,1 ;file descriptor (stdout) mov eax,4 ;system call number (sys_write) int 0x80 ;call kernel mov edx,1 ;message length mov ecx,fact ;message to write mov ebx,1 ;file descriptor (stdout) mov eax,4 ;system call number (sys_write) int 0x80 ;call kernel mov eax,1 ;system call number (sys_exit) int 0x80 ;call kernel 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
Когда приведенный выше код компилируется и выполняется, он дает следующий результат —