В программировании рекурсивной называется процедура, которая прямо или косвенно вызывает саму себя. В этой статье мы рассмотрим классический пример рекурсии — вычисление факториала.
Что такое факториал? Это математическая функция, определённая для целых неотрицательных чисел. 🙂 Обозначается восклицательным знаком (n! — факториал числа n). Факториал натурального числа равен произведению всех натуральных чисел до него. Факториал нуля равен 1. Подробнее можете прочесть здесь [1].
У факториала есть такое свойство: для натурального числа он равен произведению этого числа на факториал предыдущего натурального числа. Иными словами, факториал может быть определен формулой:
Теперь должно быть всё понятно, можно писать код 🙂 Наша задача — создать процедуру, которая будет возвращать 1, если параметр равен 0, иначе уменьшать его на 1 и вызывать саму себя!
Поскольку факториал определён для неотрицательных чисел, параметр процедуры и возвращаемое значение будут 16-битными целыми без знака. Параметр будет передаваться через стек, а результат возвращаться в регистре AX. Вот что у меня получилось:
; Рекурсивная процедура вычисления факториала
; вход: CX - число без знака
; выход: AX - результат
factorial:
push bp ;Сохранение BP
mov bp,sp ;BP=SP
mov ax,[bp+4] ;AX=параметр
test ax,ax ;Проверка AX
jz f_ret1 ;Если 0, вернуть 1
dec ax ;Декремент AX
push ax ;Помещение параметра в стек
call factorial ;Вызов процедуры для предыдущего числа
mul word[bp+4] ;Умножение результата на параметр процедуры
jmp f_ret ;Переход к возврату из процедуры
f_ret1:
inc ax
f_ret:
pop bp ;Восстановление BP
ret 2 ;Возврат из процедуры
Факториал — очень быстро возрастающая функция, поэтому мы не сможем этой процедурой вычислять его для чисел больше 8 (результат просто не влезет в 16 бит). Если вам нужно серьёзно вычислять факториал — используйте числа с плавающей точкой (хотя результат будет не совсем точным) или многобайтные целые (потребуется хитрая процедура умножения).
Для наглядности я добавил в программу цикл и процедуры для вывода чисел в десятичном виде (из части 22 учебного курса [2]). В результате получилась такая программа (вроде считает правильно 😉 ):
Скачать полный исходный код примера можно здесь: factorial.asm [3].
Недостатки рекурсии
Основной недостаток рекурсии — это большое использование памяти в стеке. Рекурсия здорово ест ресурсы! При каждом вызове процедуры в стеке сохраняется адрес возврата, используемые регистры, параметры процедуры, а также может выделяться место для локальных переменных. Кроме того, на работу со стеком тратится дополнительное время, что может сделать рекурсию медленной.
К счастью, во многих случаях можно заменить рекурсию циклом. Старайтесь делать это везде, где возможно! Тот же самый факториал лучше вычислять в цикле. Сравните следующий код с рекурсивным вариантом:
; Процедура вычисления факториала в цикле
; вход: CX - число без знака
; выход: AX - результат
factorial_loop:
push bp ;Сохранение BP
mov bp,sp ;BP=SP
push cx ;Сохранение CX
mov cx,[bp+4] ;CX=параметр
xor ax,ax ;AX=0
inc ax ;AX=1
jcxz f_ret ;Если CX=0, выход из процедуры
f_lp:
mul cx ;Умножение
loop f_lp ;Команда цикла
f_ret:
pop cx ;Восстановление CX
pop bp ;Восстановление BP
ret 2 ;Возврат из процедуры