Хвостовая рекурсия
От: DemAS http://demas.me
Дата: 07.04.08 06:43
Оценка:
Из sicp:

'В языках типа Pascal, C реализация любой рекурсивной процедуры требует
объем памяти линейно возрастающий с вызовом процедур. Поэтому в них и
приходится прибегать к таким вещам, как циклы (что, по сути, является
синтаксическим сахаром). Scheme избавлена от этого недостатка и
выполняет итеративный процесс используя фиксированное кол-во памяти.
Это свойство называется хвостовой рекурсией.'

Несколько вопросов по написанному выше:

1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует
памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в
момент вызова процедуры в стек помещаются параметры процедуры. А если
их нет? Адрес возврата?

2) Каким образом разработчикам Schema удалось избежать линейно
возрастающих требований к памяти при реализации рекурсии?
Posted via RSDN NNTP Server 2.1 beta
Re: Хвостовая рекурсия
От: Курилка Россия http://kirya.narod.ru/
Дата: 07.04.08 06:48
Оценка:
Здравствуйте, DemAS, Вы писали:

DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует

DAS>памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в
DAS>момент вызова процедуры в стек помещаются параметры процедуры. А если
DAS>их нет? Адрес возврата?

Зависит от. Может и адрес, тыж не сказал на каком процессоре в каком компиляторе.
С практической т.зр. рекурсивная функция без параметров большого смысла не имеет.
Т.к. единственный способ выхода из ней — использовать грязные они же "императивные" фичи.

DAS>2) Каким образом разработчикам Schema удалось избежать линейно

DAS>возрастающих требований к памяти при реализации рекурсии?

Как самый простой варинат — http://en.wikipedia.org/wiki/Tail-recursive
Re: Хвостовая рекурсия
От: geniepro http://geniepro.livejournal.com/
Дата: 07.04.08 10:20
Оценка: +2
Здравствуйте, DemAS, Вы писали:

DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует

DAS>памяти, линейно возрастающей с вызовом процедур?

GCC имеет оптимизацию хвостовой рекурсии (Visual C++ вроде тоже), так что не все и не любой...

DAS>2) Каким образом разработчикам Schema удалось избежать линейно

DAS>возрастающих требований к памяти при реализации рекурсии?

Преобразуют хвостовую рекурсию в простой цикл.
Re: Хвостовая рекурсия
От: MasterZiv СССР  
Дата: 07.04.08 10:34
Оценка: 2 (1)
DemAS пишет:

> синтаксическим сахаром). Scheme избавлена от этого недостатка и

> выполняет итеративный процесс используя фиксированное кол-во памяти.
> Это свойство называется хвостовой рекурсией.'

Не всегда только, не всегда во всех случаях Scheme или LISP
от этого недостатка избавлены. А вот чтобы они были избавлены
и надо применять хвостовую рекурсию, и тогда компилятор или
интерпретатор сможет сделать ее оптимизацию и заменить ее
на тот же цикл.

> 1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует

> памяти, линейно возрастающей с вызовом процедур?

Ну не умеют компиляторы С и Паскаля оптимизировать такое.
Хотя, кстати, может какие-то и умеют ... Но для таких
языков такие приемы не являются, как бы сказать,
идеоматическими, поэтому их оптимизации меньше внимания
уделяют.

Насколько я понимаю, в
> момент вызова процедуры в стек помещаются параметры процедуры.

да, правильно.

А если
> их нет? Адрес возврата?

Да, адрес возврата, кроме того, могут быть еще какие-то служебные данные,
типа суммарного размера всех параметров (как в __stdcall-соглашении) или
напр.

>

> 2) Каким образом разработчикам Schema удалось избежать линейно
> возрастающих требований к памяти при реализации рекурсии?

Заменой на цикл. Если рекурсия хвостовая (точнее, это — необходимое
условие, но не достаточное), то возможно у функции есть
одно свойство — после передачи управления рекурсивному вызову самой
себя никакая из локальных переменных этой функции в ее вызывающем
варианте не будет нужна для формирования результата. В таком
случае вызываемый вариант может использовать для переменных
ту же память, что использовал вызывающий.
Posted via RSDN NNTP Server 2.1 beta
Re: Хвостовая рекурсия
От: SergH Россия  
Дата: 07.04.08 10:38
Оценка:
Здравствуйте, DemAS, Вы писали:

DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует

DAS>памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в
DAS>момент вызова процедуры в стек помещаются параметры процедуры. А если
DAS>их нет? Адрес возврата?

Да. Так или иначе запоминается адрес возврата.
Локальные переменные ещё.

DAS>2) Каким образом разработчикам Schema удалось избежать линейно

DAS>возрастающих требований к памяти при реализации рекурсии?

Переиспользованием. На ассмеблере при желании это тоже можно сделать Для этого надо:

— очистить стек от своих локальных переменных (они больше не понадобятся — возврата не будет)
— вручную сформировать правильный стек для вызова, положив в него параметры и адрес возврата к исходной точке
— вызвать функцию командой jmp, а не call

И никакого линейного роста.
Делай что должно, и будь что будет
Re[2]: Хвостовая рекурсия
От: MasterZiv СССР  
Дата: 07.04.08 11:29
Оценка:
MasterZiv пишет:
> Насколько я понимаю, в
>> момент вызова процедуры в стек помещаются параметры процедуры.

Я еще хотел подчеркнуть, что то, как вызываются функции, стандартом
не регламентируется, поэтому в общем случае вы теоретически просто
не знаете, как передаются параметры.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Хвостовая рекурсия
От: SergH Россия  
Дата: 07.04.08 13:22
Оценка:
Здравствуйте, geniepro, Вы писали:

G>GCC имеет оптимизацию хвостовой рекурсии (Visual C++ вроде тоже), так что не все и не любой...


А с деструкторами как?
Делай что должно, и будь что будет
Re[3]: Хвостовая рекурсия
От: WolfHound  
Дата: 07.04.08 13:29
Оценка:
Здравствуйте, SergH, Вы писали:

G>>GCC имеет оптимизацию хвостовой рекурсии (Visual C++ вроде тоже), так что не все и не любой...

SH>А с деструкторами как?
А они иногда бывают тривиальными...
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Хвостовая рекурсия
От: MasterZiv СССР  
Дата: 07.04.08 16:19
Оценка:
SergH пишет:

> А с деструкторами как?


Так а в чем проблема ?
Казалось бы, если функция преобразуется в тело цикла,
то и все ее локальные объекты становятся локальными в теле цикла,
а тут вызывать деструкторы С++ умеет ...

> Делай что должно, и будь что будет

Кстати, этот девиз и на моём "гербе" тоже ...
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Хвостовая рекурсия
От: SergH Россия  
Дата: 07.04.08 21:46
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Так а в чем проблема ?

MZ>Казалось бы, если функция преобразуется в тело цикла,
MZ>то и все ее локальные объекты становятся локальными в теле цикла,
MZ>а тут вызывать деструкторы С++ умеет ...

Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но просто довольно часто так сделать нельзя, потому что рекурсия не является "истинно хвостовой", после вызова должны вызваться деструкторы. И нужно хорошо подумать, чтобы вызвать их иначе. Ну, типа так:

std::string func(const std::string& str)
{
std::string tmp = ...
...
return func(tmp);
}


Где будем освобождать память? И про исключения не забываем.. Не, подумать и придумать можно. Осталось это засунуть в компилятор. Хорошо языкам с GC, у них таких проблем просто не стоит.

>> Делай что должно, и будь что будет

MZ>Кстати, этот девиз и на моём "гербе" тоже ...

Делай что должно, и будь что будет
Re[2]: Хвостовая рекурсия
От: FR  
Дата: 08.04.08 03:59
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Ну не умеют компиляторы С и Паскаля оптимизировать такое.

MZ>Хотя, кстати, может какие-то и умеют ... Но для таких
MZ>языков такие приемы не являются, как бы сказать,
MZ>идеоматическими, поэтому их оптимизации меньше внимания
MZ>уделяют.

Современные C++ компиляторы практически все оптимизируют хвостовую
рекурсию. Кроме того тот же VC уже давно умеет агрессивно инлайнить
рекурсивные функции, притом произвольные рекурсивные функции, необязательно
с хвостовой рекурсией, как результат быстодействие может вырасти на порядки,
конечно цена раздутый код (из 100 строчной сишной функции бывает и до 100000
ассемблерных строк)

А идеоматичность зависит не только от инструмента, но и от пользователя
Re[5]: Хвостовая рекурсия
От: MasterZiv СССР  
Дата: 08.04.08 05:25
Оценка:
SergH пишет:
> Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но

Я так и не понял, в чем же там проблема с деструкторами.
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Хвостовая рекурсия
От: FR  
Дата: 08.04.08 05:34
Оценка:
Здравствуйте, SergH, Вы писали:


SH>Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но просто довольно часто так сделать нельзя, потому что рекурсия не является "истинно хвостовой", после вызова должны вызваться деструкторы. И нужно хорошо подумать, чтобы вызвать их иначе. Ну, типа так:


SH>
SH>std::string func(const std::string& str)
SH>{
SH>std::string tmp = ...
SH>...
SH>return func(tmp);
SH>}
SH>


SH>Где будем освобождать память? И про исключения не забываем.. Не, подумать и придумать можно. Осталось это засунуть в компилятор. Хорошо языкам с GC, у них таких проблем просто не стоит.


Да в таких случаях хочешь не хочешь нужно держать на стеке временные переменные, вот для такого

#include <iostream>
#include <string>

using namespace std;

std::string func123(const std::string& str, const std::string& acc = "")
{
    if(str.empty()) return acc;
    
    std::string tmp(str.c_str(), str.size() - 1);
    
    return func123(tmp, acc + str[str.size() - 1]);
}

int main()
{
    cout << func123("Test") << endl;
}


call на себя в асм листинге (VC8) нет
Но есть хитропопоя подмена адреса возврата.
Вот VC9 фигней не занимается и делает call.

Зато D от DigitalMars, раскрывает просто в чистейший цикл:

import std.stdio;

string func123(string str, string acc = "")
{
    if(str.length < 1) return acc;
    
    string tmp = str[0 .. str.length - 1];
    
    return func123(tmp, acc ~ str[str.length - 1]);
}

void main()
{
    writefln(func123("Test"));
}



    push    ebp
    mov    ebp, esp
    push    edi
    push    esi
    push    ebx
    sub    esp, 44
    mov    eax, DWORD PTR [ebp+8]
    mov    edx, DWORD PTR [ebp+12]
    mov    DWORD PTR [ebp-24], eax
    mov    DWORD PTR [ebp-20], edx
    mov    eax, DWORD PTR [ebp+16]
    mov    edx, DWORD PTR [ebp+20]
    jmp    L10
L12:
    mov    eax, DWORD PTR [ebp-24]
    mov    edi, DWORD PTR [ebp-20]
    mov    edx, 1
    sub    eax, 1
    mov    ebx, DWORD PTR [ebp-28]
    mov    ecx, DWORD PTR [ebp-32]
    mov    esi, eax
    add    eax, edi
    mov    DWORD PTR [esp+16], edx
    mov    DWORD PTR [esp+20], eax
    mov    DWORD PTR [esp+12], ebx
    mov    DWORD PTR [esp+8], ecx
    mov    DWORD PTR [esp+4], 2
    mov    DWORD PTR [esp], OFFSET FLAT:__D11TypeInfo_Aa6__initZ
    call    __d_arraycatnT
    mov    DWORD PTR [ebp-24], esi
    mov    DWORD PTR [ebp-20], edi
L10:
    cmp    DWORD PTR [ebp-24], 1
    mov    DWORD PTR [ebp-32], eax
    mov    DWORD PTR [ebp-28], edx
    jae    L12
    mov    eax, DWORD PTR [ebp-32]
    mov    edx, DWORD PTR [ebp-28]
    add    esp, 44
    pop    ebx
    pop    esi
    pop    edi
    pop    ebp
    ret


Тут конечно GC рулит.
Re[6]: Хвостовая рекурсия
От: FR  
Дата: 08.04.08 05:44
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>SergH пишет:

>> Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но

MZ>Я так и не понял, в чем же там проблема с деструкторами.


Тупят компиляторы (как и я ) с времеными переменными.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.