Comments 34
Сразу заметим, что возвращаемым результатом функции является вызов этой же функции (именно поэтому рекурсия хвостовая), а если быть точнее, то сумма результатов вызова двух функций.
У вас в примере не хвостовая рекурсия: после рекурсивных вызовов выполняется сложение.
Под силу ли побороть любую рекурсию?
не рекурсивный обход графа? не рекурсивный поиск пути? наверное можно, но как то сложно это :) с рекурсией проще
Чтобы понять рекурсию нужно понять рекурсию...
Впрочем, про ваше утверждение этого не скажешь. Оно абсолютно корректно, ибо является тавтологией. Но не на дюйм не приближает к пониманию рекурсии.
В свое время (очень давно) проходил собеседование, кажется в ABBYY, и там дали задачку по вычислению результата функции вроде f(xn)=z(f(xn-1)), где z — еще какая-то функция (не помню какая). Естественно, я подошел к решению с помощью рекурсии. И естественно, я был не первый такой умник, судя по ухмылке интервьюера. Довольно наглядно и на пальцах показал, что человечество еще не подошло к созданию таких вычислительных машин, чтобы вычислить с помощью рекурсии значение функции даже для f(5) в разумные пределы времени с разумным количеством памяти, несмотря на то, что результат вычисления находился в пределах от 1 до 100.
К чему я это? Опытный взгляд увидит из картинки автора, что f(0) вычисляется 5 раз, f(1) уже 8 раз, f(2) тоже 5 раз. Да, для f(0), f(1), f(2) вычислений почти не производится, но для f(100) что будет? И что будет, если это не вычисление Фибоначчи, а что посложнее?
Пост был бы намного богаче в смысловом плане, если бы давал представления о применимости рекурсии. Лично для меня никогда не было понятно применение рекурсии для вычисления факториала или тех же чисел Фибоначчи с диким оверхедом, если это делается намного нагляднее банальным циклом. При этом рекурсия вполне разумно подходит для поиска файлов. Но из текста поста этого ничего не ясно: бороться с ней нужно, но необязательно; бороться можно, но непонятно как.
Так это вообще скорее шутка)
И что будет, если это не вычисление Фибоначчи, а что посложнее?Что будет, зависит от того, кто делает. Например, банальная мемоизация результатов чистых функций спасет отца русской демократии (да, я в курсе про переполнение инта):
int a[100];
int f(int i) {
if (i<2) return i;
else {
if (a[i]==0) a[i]=f(i-1)+f(i-2);
return a[i];
}
}
int main() { std::cout << f(100); }
В свое время, решая многочисленные задачки типа размена монет и подсчета вариантов, я быстро находил тривиальные лобовые экспоненциально-рекурсивные решения, которые тормозили на определенных объемах данных. И было 2 пути — либо каждый раз придумывать свой отдельный другой алгоритм именно для этой конкретной задачи (что любят называть термином динамическое программирование, хотя кое-кто (и я в том числе) причисляют к этому и рекурсию с мемоизацией), либо один раз и навсегда написать абстракцию универсального мемоизатора, и скармливать ему любые тривиально рекурсивные схемы. Даже кату по этому поводу создал — https://www.codewars.com/kata/550756a881b8bdba99000348 Хотя если мы дошли до ФП, и Хаскеля в частности, то это отдельная
("Динамическое программирование" — оно про другое.)
Мемоизация — это способ борьбы с многократным вычислением одного и того же, а не с глубиной стека. А вот для борьбы с глубиной стека уже надо просто заменять алгоритм (либо на нерекурсивный, либо на алгоритм с хвостовой рекурсией).
Никакого "Принципиально другого алгоритма" придумывать не нужно. После того как вы сделали мемоизацию, достаточно просто перейти к рекурсивному алгоритму.
- Выбираем способ обхода (обычно оно очевидно)
- Пишем цикл, перебирающий параметры
- Пишем код, аналогичный вызову функции с этими параметрами, с учетом того что запомненного значения заведомо нет.
- Саму функцию меняем с учетом того что запомненное значение заведомо есть.
Вот ваш случай:
int a[100];
int f(int i) {
if (i<2) return i;
else {
return a[i];
}
}
for (int i=2; i<100; i++)
a[i] = f(i-1)+f(i-2);Это что, теперь называется "придумывать принципиально другой алгоритм"?
Вряд ли человек, который не знает, что такое рекурсия в программировании хоть что-то поймёт из этой статьи, тут какие-то обрывки мыслей вперемешку с копипастой из википедии, да и инфы-то тут никакой особо нет.
Ну а для того чтобы нормально понять, что такое рекурсия в программировании, какие её типы бывают, какие проблемы возникают и как с ними правильно бороться, вполне хватит прочитать главу 1.2. из небезызвестной SICP. Лучшего объяснения я не видел.
Можно было хотя бы разобрать алгоритмы и реализации программ, рисующих фракталы, чтобы было немного интересно. Но нет, тут только пара невзрачных картинок (даже Мандельброта и брокколи нет) без объяснений.
PS А пример на прологе мне не кажется таким уж наглядным, хаскель подошёл бы лучше, так как для подобных примеров (числа фибоначчи, факториал, функция аккермана, и т.п.) код практически совпадает с мат. определением этих ф-ций (ага, я тоже умею копипастить):
fac 0 = 1
fac n = n * fac (n-1)
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
«Я долго не понимал что такое „динамика“, но когда мне объяснили, что динамика — это „рекурсия“, а рекурсия — это „индукция“, то все встало на свои места»
когда мне объяснили, что динамика — это „рекурсия“, а рекурсия — это „индукция“, то все встало на свои места
Непонятно, как всё могло встать на места, если оба утверждения являются неверными.
динамика — это „рекурсия“
Под динамическим программированием обычно понимают решение задачи через комбинацию решений перекрывающихся подзадач меньшего размера. Подзадачи должны образовывать ациклический направленный граф.
Когда же задача выражена в виде ациклический графа, его можно считать двумя способами: рекурсивно, используя мемоизацию для хранения решений перекрывающихся задач, либо не рекурсивно, если считать подзадачи в порядке, совпадающем с одной из топологических сортировок графа задач. Первый способ обычно проще, потому что так нужно меньше думать — машина сама неявно посчитает топологическую сортировку при обходе графа задач в глубину.
рекурсия — это „индукция“
Рекурсия движется от сложной структуры к простой, пока не дойдёт до тривиальной базы. Индукция движется от тривиальной базы к всё более сложным структурам. Поэтому рекурсия — это индукция, вывернутая наизнанку.
.jpg){kind=link}
В рекурсии сложную задачу разбивают на более простые пока не дойдут до тривиальных задач, а потом объединяют полученное решение.
В динамике сначала решают тривиальные задачи, потом объединяют и получают решения для все более и более сложных задач, пока не получат решение исходной задачи.
Так, да не так. Во-первых, циклу эквивалентна только хвостовая рекурсия. Во-вторых, побудительное предложение является императивным — а потому к ФП отношения не имеет.
В-третьих, строго говоря, тут нет ни рекурсии, ни цикла — говорится же только прочитать предложение, а не делать что в нем написано :)
Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала.Вычисление чисел Фибоначчи — самая известная программисту задача, которую не надо решать ни за экспоненциальное, ни за линейное время.
Стек данных вместо стека возвратов — нет ли здесь размена шила на мыло и подмены понятий?
Суть в том, что у нас всего 1 мегабайт стека возвратов — и все адресное пространство для стека данных! :)
При достижении определённой глубины просто берём и вызываем функцию в контексте другого потока (можно даже другого процесса) (можно даже на другой машине в вычислительном кластере).
Стек возвратов — универсальный инструмент, и в силу универсальности, избыточный.
Если для вычисления рекурсивной функции у нас есть, грубо говоря, две-три-четыре точки возврата, то для кодирования их нам достаточно одного-полутора-двух бит, причём зачастую, эти значения можно даже не хранить, а вычислять из текущего контекста.
Поэтому в конкретной функции стек данных решает. То есть, мы пишем свою маленькую виртуальную машинку под конкретную задачку.
Рекурсия. Беглый взгляд