Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Заметки о рекурсии - 2. Взгляд на рекурсию изнутри.  (Прочитано 15649 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Anonymous
Гость
« : 09-08-2004 19:15 » 

Alf[/f], очень интересная статья!

Подробный и доходчивый рассказ, всё ясно и понятно.

Пара мелких клопиков Улыбаюсь

1.  Ваш факториал возвращает для 0 значение 0, хотя общепринято 0! = 1.  Возможно, это упрощение оправдано, так как дизассемблированный код выглядит чуть проще, но стоило остановиться на этом в тексте.

2.  Для того, чтобы в окне Disassemble появились строки с текстом программы, мне потребовалось выставить флаг "Generate debug info" на вкладке Link,  страница General.

И ещё один вопрос, так сказать, методический.  Почему вы выбрали оптимизацию "Minimize Size"?  На мой взгляд, оптимизация по скорости даёт ассемблерный код, более приближенный к оригиналу на С

Код:
1{    long int Fact)long int N:
2{      |
00401000   push        esi
00401001   mov         esi,dword ptr [esp+8(
00401005   cmp         esi,1
00401008   jge         Fact+0Eh )0040100e:
0040100A   xor         eax,eax
0040100C   pop         esi
6{      "
0040100D   ret
3{       if )N < 1: return 0;
4{       else if )N == 1: return 1;
0040100E   jne         Fact+17h )00401017:
00401010   mov         eax,1
00401015   pop         esi
6{      "
00401016   ret
5{       else return N * Fact)N-1:;
00401017   lea         eax,[esi-1(
0040101A   push        eax
0040101B   call        Fact )00401000:
00401020   imul        eax,esi
00401023   add         esp,4
00401026   pop         esi
6{      "
00401027   ret


Похожесть на оригинал, по-моему, в данном случае полезна, так как не надо объясненять трюки, к рекурсии не относящиеся.  Например, шаманское сравнение с единицей

Код:
  00401005 6A 01 push 1 
  00401007 58 pop eax
  00401008 3B F0 cmp esi,eax


Но в целом статья произвела очень хорошее впечатление.  Чётко и доходчиво.  Спасибо за статью :!:
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 09-08-2004 19:18 » 

:!:  :!:  :!:

Вместо Гость читать npak.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Alf
Гость
« Ответ #2 : 10-08-2004 07:28 » 

npak, спасибо и за добрые слова, и за толковую рецензию!

По первым двум пунктам - следствие поспешности, хотелось закончить статью за выходные, а спешка, как известно, до добра не доводит..  :oops:
Особенно досадна вторая оплошность, т.к. новичок, не имеющий опыта работы с отладчиком, может остановиться на этом препятствии. Единственно, что непонятно, - это как ее могли до сих пор не заметить, ведь статью прочитали уже более 400 человек. Неужели никто более даже не попытался выполнить примеры самостоятельно?

По третьему пункту: по-хорошему, для отладки лучше бы вообще избегать какой-бы то ни было оптимизации, но неоптимизированный код изобиловал таким количеством прологов/эпилогов при вызове функции, что половина статьи ушла бы на их разбор, а не на рекурсию как таковую. Пришлось оптимизировать, причем на первый взгляд показалось, что более компактный код будет легче для восприятия. Конечно, сэкономленные 2 байта не стоят некоторой потери ясности кода. Однако надеюсь, что читатели все же преодолеют эту небольшую трудность, и она не закроет для них самой сути статьи.

Еще раз спасибо за проделанную работу и внимание! На неделе постараюсь исправить, что возможно.
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 11-08-2004 12:06 » 

Alf, я понимаю, что опосля мы все умные, но тем не мене предложу свой вариант примера.

Код:
long int Fact)unsigned long int N: 
|
    if )N <= 1: return 1;
    else return N * Fact)N-1:;
"

int main)void:
|
    unsigned long int F3;
    F3 = Fact)3:;
    return F3;
"


Я предлагаю использовать unsigned int чтобы подчеркнуть, что ни аргумент, ни значение факториала не могут быть отрицательными.  При оптимизации по скорости получается простой код на ассемблере:

Код:
1{    long int Fact)unsigned long int N:
2{    |
00401000   push        esi
00401001   mov         esi,dword ptr [esp+8(
00401005   cmp         esi,1
00401008   ja          Fact+11h )00401011:
0040100A   mov         eax,1
0040100F   pop         esi
5{    "
00401010   ret
3{        if )N <= 1: return 1;
4{        else return N * Fact)N-1:;
00401011   lea         eax,[esi-1(
00401014   push        eax
00401015   call        Fact )00401000:
0040101A   imul        eax,esi
0040101D   add         esp,4
00401020   pop         esi
5{    "
00401021   ret
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Alf
Гость
« Ответ #4 : 11-08-2004 12:25 » 

npak, спасибо, но уже нет желания эту часть переписывать. Тем более что сам факториал тут мало кому интересен, просто надо же было чем-нибудь функцию занять, чтобы не впустую вызывать. Сам механизм рекурсии от этого не прояснится, а ради него и огород городился, собственно. Уж оставлю, как есть.

А вот насчет флага "Generate debug info" - это куда серьезнее. Ведь без него читатели не получат нормальный текст в окошке дизассемблера и не смогут полноценно выполнить примеры. Это исправлю непременно.
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 20-10-2004 20:40 » 

Alf, в Вашем продолжении серии об рекурсии, есть ссыка на книгу  Альфред Ахо, Рави Сети, Джеффри Ульман
"Компиляторы. Принципы, технологии, инструменты"
Вот ссылка на озон. Русский вариант этой книги http://www.ozon.ru/context/detail/id/146264/
Также я видел электронный вариант этой книги в формате djvu.  Сейчас проверил, ссылки биты  Жаль .
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Alf
Гость
« Ответ #6 : 21-10-2004 06:39 » new

Finch, спасибо.

Дополню в тексте статьи.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines