Size: a a a

Programming Offtop

2021 May 05

M

Malik in Programming Offtop
Почему это очевидно?
источник

VP

Vladimir Petrakovich in Programming Offtop
Потому что вся суть не-хвостовой рекурсии в том, что требуется сохранять состояние промежуточных шагов.
Нельзя взять и выкинуть это.
источник

VP

Vladimir Petrakovich in Programming Offtop
Стек для этого и существует
источник

M

Malik in Programming Offtop
Такие состояния иногда можно заменить аккумуляторами
источник

VP

Vladimir Petrakovich in Programming Offtop
Так это получается та же фигня, только руками.
Да, стек вызовов функций можно заменить своим. Но зачем?
источник

M

Malik in Programming Offtop
Затем, что тогда не забивается стек.
источник

VP

Vladimir Petrakovich in Programming Offtop
Так это уже история не про хвостовую рекурсию, а про ограничение глубины стека
источник

VP

Vladimir Petrakovich in Programming Offtop
Путём замены его на свой стек, который по сути такой же, только лежит в другом месте
источник

ML

Mikhail Levchenko in Programming Offtop
Я даже не читал (у меня же не MVI 🌚)
источник

M

Malik in Programming Offtop
Так нет, суть аккумулятора в том, чтобы аккумулировать значение. Например, два варианта реализация фибонначи с аккумулятором и без. Можно переписать обычную рекурсию с фиббоначи на хвостовую с аккумулятором. Не пойму очевидность того, что нельзя сделать так же с любой другой рекурсией.

fib(n)
 n == 0 -> 0
 else -> fib_tr(0, 1, n - 1)
fib_tr(prev, cur, n):
 n == 0 -> cur
 else -> fib_tr(cur, prev + cur, n - 1)


fib(n):
 n <= 1 -> n
 else -> fib(n-1) + fin(n-2)
источник
2021 May 06

VP

Vladimir Petrakovich in Programming Offtop
Фибоначчи - это совсем не такой алгоритм, который нельзя реализовать без рекурсии
источник

VP

Vladimir Petrakovich in Programming Offtop
Одно дело, когда аккумулятор - число, другое - когда он растёт в размере на каждом шаге. Чем второй вариант принципиально отличается от стека вызовов?
источник

M

Malik in Programming Offtop
Второй вариант - это как раз и есть обычная рекурсия, когда стек растет.
источник

M

Malik in Programming Offtop
Есть алгоритмы, которые можно реализовать только рекурсией?
источник

VP

Vladimir Petrakovich in Programming Offtop
Ну да. И некоторые алгоритмы это требуют.
источник

VP

Vladimir Petrakovich in Programming Offtop
Обычно только такие и решаются рекурсией, и да, они есть
источник

M

Malik in Programming Offtop
Ну я понял, что алгоритмы которые реализовываются только рекурсией реализовываются рекурсией) Мне интересно, что это за группа алгоритмов такая и какие есть примеры.
источник

VP

Vladimir Petrakovich in Programming Offtop
Можно тут почитать
https://en.wikipedia.org/wiki/Recursion_(computer_science)
Там в качестве примера факториал
источник

VP

Vladimir Petrakovich in Programming Offtop
Но про факториал что-то не верится, он должен тривиально преобразовываться в цикл
(ну да, действительно, там даже реализация есть)
источник

DP

Defragmented Panda in Programming Offtop
предложите алгоритм симуляции для жидкости который работает с малой точностью?

например 8бит данные на ось, для поля в 1000*1000 размером

алгоритмы которые я смотрел требуют точность существенно выше. т.е. точность на 1000 поле нужна 16...32 бит на ось

или обьясните мне почему это обязательно

п.с. я таки попробовал, но получилась фигня какая-то )
источник