любая рекурсия может быть привращена в итеративную запись

Я правильно понимаю, что имеется в виду что-то такое?

fun qwe(arg) {
if (...) qwe(arg+1) else arg
}

fun qwe(arg) {
r=arg
loop {
if (...) r = r + 1 else return r
}
}

Если б такой тул существовал, создатели этих языков давно бы уже бы его туда запилили, они ж не школьники как ТС

Они и запилили. Называется TCO.

но при этом гарантированно работающее на совершенно любой входящей рекурсии, а не только на элементарной tail-recursive

А у него там в примере, кстати, не tail.

А вообще, можно написать транслятор, со специальным синтаксисом, явно указывая рекурсвные вызовы. Но для такого переусложненного говна как ++/java, это вряд ли.

А у него там в примере, кстати, не tail.

fun qwe(arg) {
if (...) qwe(arg+1) else arg
}

это хвостовая рекурсия.

Насколько я понимаю, у хвостовой рекурсивный вызов должен быть в хвосте, как и следует из названия.

я не понял, что вы имели в виду под хвостом, но такая рекурсия - хвостовая. вот что-то в духе этого - не хвостовая рекурсия:

fun qwe(arg) {
if (...) return 1 + qwe(arg-1) else arg
}

А разве не имеет значения ветка, в которой записан рекурсивный вызов? Ведь компилятор всегда смотрит на хвост функции, а в этом варианте рекурсивный вызов не находится в хвосте.

вот что-то в духе этого

Кстати, давно хотел поинтересоваться. Ваш последний вариант — это фактически взаимная рекурсия. Получается, что взаимная рекурсия не оптимизируется?

в этом варианте рекурсивный вызов не находится в хвосте.

он в хвосте. man хвост

А, точнож. Надо подумать

Получается, что взаимная рекурсия не оптимизируется

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

Просто я думаю, что любая нехвостовая рекурсия, является, по сути, частным случаем взаимной рекурсии. А нас учат, как бы, что оптимизируется только хвостовая.

Tail call легко заменяется на цикл, это даже IDE умеют сами делать.

Если не хвостовая то тут вопрос не понятно что ты хочешь получить на выходе. Например можно сделать стек руками на базе списка и свести алгоритм к хвостовому.

А нас учат, как бы, что оптимизируется только хвостовая.

а объяснение этому есть? «ты втираешь какую-то дичь! я не куплю твои удобрения!»

эх если бы я знал, что хочу получить на выходе... Я знаю, чего не хочу. Не хочу видеть StackOverflowError в Java, чего бы я ни написал, и чтобы это происходило автоматически.

Насколько я понимаю, у хвостовой рекурсивный вызов должен быть в хвосте, как и следует из названия.

не правильно понимаешь. «хвост» - это не место в редакторе кода.

А нас учат, как бы, что оптимизируется только хвостовая.

Вся оптимизация в том что используется только один стековый кадр при вычислении значения функции. Подобная оптимизация для произвольной рекусивной функции (не хвостовой) невозможна, но это не отменяет того что ее можно переписать в итеративном стиле, просто для компилятора такая техника оптимизации, видимо, крайне сложно реализуема (если вообще возможна).

ну так не пиши рекурсивные функции =)

анонiмус покусал?

это под какими такими веществами ты от тезиса чёрча «функции натуральных чисел эффективно вычислимы лишь в случае, если они являются лямбда-определимыми» пришёл к выводу «любая рекурсия может быть привращена в итеративную запись»?

Черч - Тюринг - Дойч - «любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.»

а объяснение этому есть?

Возможно, это то, что тебе надо: https://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)

вопросы :)

1. куда пропали тьюринг с дойчем из оп-поста?

2. каким веществом тезис всех троих вместе связан с твоим выводом вообще и переполнением стека в твоей жабе в частности?

функцию аккермана разверни

Это, кстати, возможно. С привлечением своего стека, естественно.

автоматом врятли, но то, что выражается рекурсивно элементарно переписывается нерекурсивно.

Вот это что-то вроде автоматики (часто используется в бедных ЯП не умеющих в рекурсию)

fix :: (a -> a) -> a
fix f = let w = f w in w

можешь перевести на свой язык :) Использовать, например, как

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

если хочется явного управления, то

data Fix a = Result a
           | Next (Fix s a)

Дальше твоя функция переписывается так, чтобы возвращала Fix a. Соотвественно получается что-то вроде continuation-passing-style и пишется враппер удовлетворяющий твоим требованиям, например запускающий функцию до выполнения в constant stack space:

fixit :: (Fix s a) -> s -> a
fixit (Result s) = s
fixit (Next f)   = fixit f -- (*)

(*) — не надо пугаться что выглядит как рекурсия, тут она хвостовая и в этих ваших явах переписывается явно без рекурсии. Ну и вообще fixit через dowhile

Выше это Fix для бедных, по хорошему надо:

data Fix a = Fix (Fix a)

и тогда, например, можно:

type List a = Fix (L a)

data L a b = Nil | Cons a b

instance Functor (L a) where
   fmap f x = case x of
        Nil      -> Nil
        Cons a b -> Cons a (f b)
 
length :: List a -> Int
length = cata $ \x -> case x of
   Nil      -> 0
   Cons _ n -> n + 1

sum :: Num a => List a -> a
sum = cata $ \x -> case x of
    Nil      -> 0
    Cons a s -> a + s

т.о. алгориртм из рекурсивного переписывается в нерекурсивный руками, но это straightforward операция и его форма сохраняется.

P.S. и нафигя я это тут пишу? :/

изучение хаскеля назначено на лето, летом вернусь и перечитаю, спасибо :3

любая рекурсия может быть привращена в итеративную запись, правильно?

нет. Если данные рекурсивные, то они и будут рекурсивными. А сам код можно. Т.е. у тебя будет эмуляция рекурсии стеком возвратов.

К примеру обход дерева(центрированный)

1. обойти левое поддерево

2. пройти корень

3. пройти правое

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

Java/C/C++ ? Может кто-то уже налабал готовый тул? причина вопроса в том, что некоторые вещи интуитивно записывать именно в рекурсивной форме, а в указанных языках рекурсией пользоваться небезопасно (= нельзя)

бред. Просто нужно _доказывать_, что глубина рекурсии не будет более log(N). Уж на 64 адреса стека у тебя всегда хватит (если ты не любитель делать массивы в 1000К на стеке), ну а 2⁶⁴ элемента у тебя в память тупо не влезут.

Компьютер работает нерекурсивно. Так что любой компилятор с этой задачей справляется.

Они и запилили. Называется TCO.

TC это и не рекурсия вовсе, а только её видимость.

Насколько я понимаю, у хвостовой рекурсивный вызов должен быть в хвосте, как и следует из названия.

неправильно. Хвостовая рекурсия, это просто тупо сахар над goto → в начало функции. Где она находится — не имеет значения. В C/C++ goto есть, т.ч. сомневающиеся могут прямо так и писать:

void qwe()
{
qwe:
if(…) goto qwe;
// …

Правильно, в таком случае, может всплыть ситуация, когда у тебя не все ветки условного выражения могут быть выполнены.

Черч - Тюринг - Дойч - «любой конечный физический процесс

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

Рекурсия не обязана быть конечной безотносительно каких-либо условий вообще. Ее «конечность» — ограничение глубины стека — это чисто техническая сторона, математике срать на глубину твоего стека, и при TCO любая бесконечная рекурсия просто превратится в бесконечный цикл, вот и все. Данные тут не при чем.

Правильно, в таком случае, может всплыть ситуация, когда у тебя не все ветки условного выражения могут быть выполнены.

и что?

while(false) — какую ты тут зависимость от данных увидел?

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

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

конечность рекурсии зависит от данных.

И да, вот тебе код

struct Node
{
  void do();
  Node* left;
  Node* right;
}

void round(Node* root)
{
  if(!root) return;
  round(root->left);
  root->do();
  round(root->right);
}

Компьютер работает нерекурсивно.

Это не имеет никакого отношения к делу.

Так что любой компилятор с этой задачей справляется.

Не все компиляторы поддерживают TCO.

while(false) — какую ты тут зависимость от данных увидел?

тут и кода нет никакого. Бессмысленный набор букв, который компилятор выкинет нафиг.

Ты че этим хочешь сказать? То что данные кончатся, и рекурсия закончится? или что? Нет, не закончится. Либо вылетит ошибка, либо кончится стек. Но это отношения к делу не имеет. Еще раз

f=function(){f()}
то же самое что
mark
goto mark

который компилятор выкинет нафиг.

ты за все компиляторы не кукарекай. И почему это он должен его выкинуть? там может быть сайд эффект внутри. Че сишный компилятор такое реально обязан выкинуть? Странно.

предположим что мы заранее знаем «правильный ответ», что написанное - конечно. Если оно не конечно, компилятору или рантайму в этом месте допустимо повиснуть. Практически, если конпеляция скопа идет дольше 30 секунд, светим в IDE диалоговое окно: вот в этом скопе у вас несобирающийся говнокод, перепишите его по другому и останавливаем сборку.

ты за все компиляторы не кукарекай. И почему это он должен его выкинуть?

кукарекалка, иди почитай про dead code elimination.

он в хвосте. man хвост

fun qwe(arg) {
if (...) return 1 + qwe(arg-1)[вот тут goto к началу откуда мы знаем, что в следующей ветке?] else(...) foo else arg
}

вот тут goto к началу откуда мы знаем, что в следующей ветке?

ой, опять ты со своей хернёй, не делай вид что не понимаешь о чём я

Если у тебя goto в хвосте выражения, значит все необходимое гарантированно выполнилось, поэтому она и хвостовая.

детка, если у тебя один выход из функции, и он только в конце функции, то такая «рекурсия» не имеет смысла. Смысл _всегда_ в такой (возможно)хвостовой рекурсии, которая иногда выполняется, а иногда — нет.

не делай вид что не понимаешь о чём я

Нет, я действительно не понимаю.

Не все компиляторы поддерживают TCO.

я уже говорил: если ты сомневаешься в C/C++, используй goto вместо TCO. Т.ч. TCO в C/C++ тупо не нужна.

Если б такой тул существовал, создатели этих языков давно бы уже бы его туда запилили, они ж не школьники как ТС

Они и запилили. Называется TCO.

TCO - это только специальный вид рекурсии.

детка, если у тебя один выход из функции, и он только в конце функции

Ребетеночек, он один, вопрос где именно.