Итеративные и рекурсивные функции

[Alexu007]

Alhimik в сообщении #781082 писал(а):

Короче, Википедия рулит. И таки для любой рекурсивной функции существует итеративная.

Существует, но во многих случаях рекурсия проще програмируется - нужно меньше кода. Например обход дерева. Рекурсия "умеет" самостоятельно вернуться к месту ветвления и таким образом обойти всё дерево. Цикл так не умеет, програмисту нужно запоминать точки ветвления, выделять для этого память, писать дополнительный код. Не запутаться при этом. Цена вопроса - большее быстродействие и меньший расход памяти в ручном режиме. Так ли это актуально в век гигабайтов и гигагерц?

А вообще довольно странная постановка вопроса. Любую функцию можно реализовать по разному.

[iifat]

Alexu007 в сообщении #781629 писал(а):

Так ли это актуально в век гигабайтов и гигагерц?

Товаришч! Ви таки умеете отличать гигабайты памяти в компьютере — и размер стека, который вписывается компилятором и отнюдь не гигабайтен?
На всякий случай: тема таки не про необходимость этого шага, а про возможность, нет?

[_Ivana]

Joker_vD Все вы правильно (и тактично ) говорите, просто здесь уже моих знаний недостаточно. Я не занимался исследованиями насколько умны различные компиляторы при разных своих настройках и могут ли они разворачивать вызов функции не только в CALL с сохранением контекста в стеке а, допустим, в RJMP. Если они действительно настолько умны, то я не исключаю возможности, что при разных настройках они одну и ту же написанную функцию или кусок кода могут реализовать как рекурсивно, так и итеративно. К тому же, я не сталкивался с термином "корекурсия", да и термин "рекурсия" при такой глубине рассмотрения для меня начинает терять ясность своего очертания.

Alexu007 в сообщении #781629 писал(а):

Цикл так не умеет, програмисту нужно запоминать точки ветвления, выделять для этого память

Что сложного выделить массив char-ов длины $N$ - получим все варианты дерева глубины $N$ с 256 ветвлениями в каждом узле. Зато без хранения $N$ контекстов с ограниченном (как уже не раз писали) стеке.

Alexu007 в сообщении #781629 писал(а):

Так ли это актуально в век гигабайтов и гигагерц?

Вынужден регулярно на этом форуме писать примерно следующее: и в наш век, когда космические корабли бороздят и все такое, существуют микросхемы с килобайтом флеша и несколькими десятками байт ОЗУ, которые вполне себе применяются для своих задач.

iifat в сообщении #781640 писал(а):

На всякий случай: тема таки не про необходимость этого шага, а про возможность, нет?

Да, про возможность. Которая, как выясняется, всегда есть. И вроде бы тема на этом исчерпана, но она затрагивает имхо интересные для обсуждения вопросы. А необходимость уже определяется всеми сопутствующими факторами.

ЗЫ в наш век гигабайтов мой Матлаб как-то мне отказался выполнять одну программу, написав что я превысил глубину рекурсии в 500 у.е. Не помню, наверное предложил увеличить этот параметр в настройках (если он вообще меняется). И что вы думаете я сделал?

[arseniiv]

Переписали на другом языке?

Насчёт компиляции рекурсии: сейчас многие компиляторы умеют оптимизировать хвостовую рекурсию, заменяя циклом. (Ведь этот случай так и просится!)