- Asmworld - http://asmworld.ru -

Рекурсивные процедуры

Posted By xrnd On 21.10.2010 @ 03:50 In Исходники | 1 Comment

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

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

Article printed from Asmworld: http://asmworld.ru

URL to article: http://asmworld.ru/isxodniki/rekursivnye-procedury/

URLs in this post:

[1] здесь: http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB

[2] части 22 учебного курса: http://asmworld.ru/uchebnyj-kurs/022-vyvod-chisel-na-konsol/

[3] factorial.asm: http://asmworld.ru/content/sources/factorial/factorial.asm

Copyright © 2009-2010 Asmworld. All rights reserved.