рекурсия и итерация

Т.е. мы можем сказать f(n) = n, или представить её в виде рекурсии: f(n) = f(n-1) + 1. Рекурсивный алгоритм - это просто вычисление ф-ции по ее рекурсивному выражению.

ты с рекуррентным не перепутал?

рекурсия и переводится иногда в итеративный вид,

Рекурсия не переводится в итеративный вид. Рекурсия реализуется с помощью итерации, от этого она не перестает быть рекурсией.

ты с рекуррентным не перепутал?

Нет. Функция вызывает сама себя? Да. Значит рекурсия.

Невозможно изучать сам объект. Возьмите бабочку, с точки зрения биологии мы изучаем ее вид, химии - вещества, благодаря которым ее окраска принимает нужный вид, физики - механика полета. Разве отсюда следует, что изучив бабочку с точки зрения биологии, физики, химии и еще бог знает чего, мы изучим бабочку? Нет, никогда не изучим. А изучим представление о ней с точки зрения этих наук.

С этой точки зрения объекта вообще не существует.

хотя рекурсия и переводится иногда в итеративный вид, но во первых не всегда

В смысле? Всегда любую рекурсию можно переписать без оной.

Я с этим абсолютно согласен, поэтому я и указываю на путаницу в терминологии, которая способна ввести в заблуждение.

ты согласен с известным заблуждением. На самом деле разные реализации дают разный результат. Потому-что жизнь отличается от теории. В жизни 2 раза по 2 вовсе не обязательно получается 4. Смотря что и КАК считать. Потому и различные термины используются.

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

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

На самом деле разные реализации дают разный результат.

Это все философия. одинаковые реализации тоже дают разный результат, есть время, есть сайд эффекты. Мы же рассматриваем вопрос на концептуальном уровне.

Всегда любую рекурсию можно переписать без оной.

Увы, нет. Например, найти общий вид суммы одинаковых степеней натуральных чисел.

Ну вот если я вас спрошу, каков алгоритм Шнитцель-Птуцера — он рекурсивный или итеративный? Вы, понятное дело, не сможете ответить, так как название этого алгоритма я только что выдумал. Но можно представить, что я дал вам два листа бумаги с реализациями этого алгоритма ну например на Си. На одном листе напечатана такая вся из себя итеративная программа с циклами и счётчиками. На другом же листе программа чистокровно-рекурсивная, где функции вызывают сами себя и нет ни одного цикла. Обе программы безошибочно реализуют алгоритм Шнитцель-Птуцера. Глядя, на эти программы, сможете ли вы теперь однозначно ответить на изначальный вопрос?

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

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

именно так. Процесс — уже вторичен. Другое дело, что мы сначала часто _видим_ процесс, а уже потом находим алгоритм для его описания. Иногда — даже неверный/неточный алгоритм, как например «теория мирового эфира». Сегодня мы определённо знаем, что никакого эфира нет, т.к. он противоречит многочисленным экспериментам.

теперь однозначно ответить на изначальный вопрос?

Чтобы ответить на изначальный вопрос не надо смотреть на бумаги, достаточно посмотреть на сам алгоритм.

Я конкретно отвечал на вопрос

Всегда любую рекурсию можно переписать без оной.

Переписать != реализовать. Что реализовать рекурсивный алгоритм при помощи итераций можно, я знаю.

Увы, нет. Например, найти общий вид суммы одинаковых степеней натуральных чисел.

Наверное, это какая-то известная задача, но я о ней не знаю. Можешь подробнее?

находим алгоритм для его описания

Ваш алгоритм для его описания - это не реализация этого алгоритма. В вашем случае, первичен алгоритм, реализация его вторична, о чем я и говорю.

Переписать != реализовать. Что реализовать рекурсивный алгоритм при помощи итераций можно, я знаю.

Так о реализации и шла ведь речь.

У любого алгоритма есть как минимум 2 варианта реализации: рекурсивная и нерекурсивная. Собственно терминология верна.
P.S. Если тупые людишки не придумали оба способа реализации, это еще не значит, что его нет.

Существует. Просто он не познаваем.

посмотреть на сам алгоритм

Так я к тому и веду: как можно «посмотреть на сам алгоритм», алгоритм — он ведь не материален. Посмотреть можно только на описание алгоритма в том или ином виде: в виде текста, кода, блок-схемы. Конечно, можно утверждать, что словесное или текстовое описание более понятны, поэтому приоритет можно отдать им. Но понятность — это дло вкуса.

Можно. Если сделать свой стэк для нужной части данных.

Наверное, это какая-то известная задача, но я о ней не знаю. Можешь подробнее?

Поподробней можно, если тебя не смущает тот факт, что здесь я уж точно перепутал реккурентное выражение с рекурсией. Мысль в том, что не всякое реккурентное выражение можно переписать без рекурсии.

Ссылка http://slovari.yandex.ru/~книги/БСЭ/Бернулли числа/
Это уже интересно:

Для Б. ч. известны рекуррентные формулы, позволяющие последовательно вычислять эти числа, а также явные формулы (имеющие довольно сложный вид).

Про существование явного вида я не знал :(

Посмотреть можно только на описание алгоритма в том или ином виде

Правильно, Вы смотрите на запись и понимаете ее смысл. В чем проблема. Затем Вы реализуете это. Ваша реализация будет отражать идею. А технически, синтаксически, что это будет за реализация, не всели равно?

Ваш алгоритм для его описания - это не реализация этого алгоритма. В вашем случае, первичен алгоритм, реализация его вторична, о чем я и говорю.

ну может и так. А какая разница? Птицы существуют для того, что-бы их есть. Выше уже сказали. Бабочки существуют, что-бы их ели птицы...

Рекурсия не переводится в итеративный вид. Рекурсия реализуется с помощью итерации, от этого она не перестает быть рекурсией.

у тебя беда с терминологией. Читай Кнута и/или других классиков. А то лично я тебя просто не понимаю. Или ты философствуешь, и речь вообще не про алгоритмы?

Нет. Функция вызывает сама себя? Да. Значит рекурсия.

ну ты привёл пример возвратных(рекуррентных) выражений. Это простой способ записать сложную формулу. Рекурсия несколько другое, это когда что-то определяется само через себя, а не через своё прошлое значение. Т.е. «масло масленое» это рекурсия, а вот «вдвое более маслянистое масло» это рекуррентное соотношение. Да, в тривиальных случаях получается простой бесконечный цикл.

В смысле? Всегда любую рекурсию можно переписать без оной.

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

Ты путаешь с хвостовой рекурсией, которая на самом деле рекурсией и не является. Этот важный частный случай _всегда_ можно представить циклом. Но не всякая рекурсия хвостовая.

Я речь вел о том, что понятие рекурсивная реализация не совсем удачен сам по себе, и вводит в заблуждение, поскольку речь здесь идет исключительно о синтаксисе. В этом смысле, нельзя путать понятия «рекурсивный алгоритм» и «рекурсивная запись», т.е., синтаксическая вариация, реализации. Это разные вещи.

Это все философия. одинаковые реализации тоже дают разный результат, есть время, есть сайд эффекты. Мы же рассматриваем вопрос на концептуальном уровне.

накопление неопределённости и потерь информации зависит от того, что ты называешь «концепцией». Т.е. в итеративных реализациях неопределённость накапливается иначе(иногда «лучше», а иногда «хуже»). Что касается разных мелочей вроде порядка операций, то это имеет мало значения, ибо компилятор выбирает оптимальный порядок на этой платформе. Если умножение намного дороже сложения (как в i8086), то _всегда_ выполнится (a-b)*(a+b), а не (a*a - b*b). От программиста это не зависит. Т.е. как не пиши, в конечном итоге будет первый вариант.

while-программы эквивалентны µ-рекурсивным функциям, loop-программы эквивалентны примитивно-рекурсивным функциям.

Тебе где-то придётся запоминать, куда тебе вернуться

И что, нельзя это запоминание реализовать в цикле?

Глядя, на эти программы, сможете ли вы теперь однозначно ответить на изначальный вопрос?

алгоритм истинно рекурсивен, если он НЕ разворачивается в цикл. AFAIK это тогда, и только тогда, когда входные данные рекурсивны.

ты ответ на это читал? ссылку дать, или сам отмотаешь?

Если я тебе скажу, что CPU не знает понятия «рекурсия», тебя это убедит?

И что, нельзя это запоминание реализовать в цикле?

нет. В итеративном цикле — нельзя. «Итеративный», это такой, где n+1 выражается *только* через n. А рекурсивный — через (в общем случае) — *всё*. В частности при обходе дерева твой путь зависит от того, где ты *уже* был. второй раз туда же ходить не нужно. Потому нужно на тех ходах ставить крестики. Тем и отличается рекурсия от итерации, в итерации ты просто последовательно перебираешь множество.

Конечно можно сделать в цикле, сделав эмуляцию стека возвратов например массивом. Для бинарного дерева глубиной h достаточно всего h бит.

Если я тебе скажу, что CPU не знает понятия «рекурсия», тебя это убедит?

нет. Мой знает. Начиная с i8080. У меня есть стек возвратов, именно для рекурсии. И команды call/ret. Вызов подпрограмм — просто побочный эффект.

Тем и отличается рекурсия от итерации, в итерации ты просто последовательно

А кто запрещает прыгнуть назад при переборе?

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

стек уже отменили?

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

Я полагаю, что имеется в виду свой стек. Тогда можно любую итерацию заменить на цикл. Часто он действительно быстрее работает.

Ок, дабы не заниматься демагогией что есть костыль а что нет.

Машина Тьюринга тоже о рекурсии не знает.

Алгоритм от этого рекурсивным быть не перестанет. Какая вообще разница, свой стек или системный?

Алгоритм от этого рекурсивным быть не перестанет. Какая вообще разница, свой стек или системный?

Тогда дай более-менее точное определение рекурсивности программы и алгоритма

нет. Мой знает. Начиная с i8080. У меня есть стек возвратов, именно для рекурсии. И команды call/ret. Вызов подпрограмм — просто побочный эффект.

Не «именно для рекурсии», а «именно для вызова подпрограмм». Но не важно.

Тогда дай более-менее точное определение рекурсивности программы и алгоритма

Я как раз говорил о том, что рекурсивным может быть только алгоритм. Реализация - это всего лишь синтаксис.

Какая вообще разница, свой стек или системный?

stack-overflow же.

нет. В итеративном цикле — нельзя. «Итеративный», это такой, где n+1 выражается *только* через n. А рекурсивный — через (в общем случае) — *всё*. В частности при обходе дерева твой путь зависит от того, где ты *уже* был. второй раз туда же ходить не нужно. Потому нужно на тех ходах ставить крестики. Тем и отличается рекурсия от итерации, в итерации ты просто последовательно перебираешь множество.

Тогда ответь на следующие вопросы:

1) поиск в глубину итеративен или рекурсивен?

2) поиск в ширину итеративен или рекурсивен?

3) алгоритм Флойда-Уоршелла итеративен или рекурсивен?

К чему я это все спрашиваю? К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

К тому, что я любой алгоритм могу вывернуть и в рекурсию, и в итеративный процесс.

Это собственно и подтверждает мою мысль.

Как говорили у нас во дворе - рекурсивный алгоритм - это алгоритм, который определен через самого себя. Т.е. если он в процессе работы прямо или косвенно обращается к себе же. Как ты это сделаешь, через рекурсивный вызов функции или же через goto - неважно. Задействуешь ли ты системный стек или будешь юзать свой - неважно. В смысле важно для реализации, но не важно для определения.

Ты не понял. Твоя поповская собака рекурсивна лишь до тех пор, пока мы рассматриваем её как рекурсивную, т.е. условно говоря «пусть х - история, тогда х = начало+х+конец». А если рассматривать её как последовательность одинаковых фраз, т.е. х = начало*n+конец*n, где n=∞, то это итеративная задача.