Заметки о рекурсии - 2. Взгляд на рекурсию изнутри.

[Anonymous]

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]

:!:  :!:  :!:

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

[Alf]

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

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

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

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

[npak]

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

[Alf]

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

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

[Finch]

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

[Alf]

Finch, спасибо.

Дополню в тексте статьи.