FasmWorldПрограммирование на ассемблере FASM для начинающих и не только

В программировании рекурсивной называется процедура, которая прямо или косвенно вызывает саму себя. В этой статье мы рассмотрим классический пример рекурсии — вычисление факториала.

Что такое факториал? Это математическая функция, определённая для целых неотрицательных чисел. 🙂 Обозначается восклицательным знаком (n! — факториал числа n). Факториал натурального числа равен произведению всех натуральных чисел до него. Факториал нуля равен 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 учебного курса). В результате получилась такая программа (вроде считает правильно 😉 ):

Скачать полный исходный код примера можно здесь: factorial.asm.

Недостатки рекурсии

Основной недостаток рекурсии — это большое использование памяти в стеке. Рекурсия здорово ест ресурсы! При каждом вызове процедуры в стеке сохраняется адрес возврата, используемые регистры, параметры процедуры, а также может выделяться место для локальных переменных. Кроме того, на работу со стеком тратится дополнительное время, что может сделать рекурсию медленной.

К счастью, во многих случаях можно заменить рекурсию циклом. Старайтесь делать это везде, где возможно! Тот же самый факториал лучше вычислять в цикле. Сравните следующий код с рекурсивным вариантом:

; Процедура вычисления факториала в цикле
; вход: 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                   ;Возврат из процедуры