Бесконечная рекурсивная функция

Если хвостовая, то можно... Кажется, call-with-current-continuation или как-то так.

http://en.wikipedia.org/wiki/Tail_recursion

1: goto 1;

Но ведь все эти вызовы будут заноситься в стек, и рано или поздно возникнет Stack overflow.

в полном виде:

long pm = ;

1:
...
pm = ..;
goto 1;

>1: goto 1;

нужна функция, а не просто бесконечный цикл.

если надо хранить все параметры - без ограничения в памяти не обойтись, если нет - обычный цикл то что тебе надо

Слышал чтонить про кольцо?

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

может тогда поможет man 'конечный автомат'?

если я правильно понял, что надо.

Абелева группа по первой операции, полугруппа по второй плюс дистрибутивность, или ты про что?

> надо хранить все параметры

в астрале?

Если компилятор поддерживает оптимизацию хвостовой рекурсии то нет. Он превратит такую рекурсию в итерацию на уровне ассемблера. GCC, например, оптимизирует.

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

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

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

> Он превратит такую рекурсию в итерацию на уровне ассемблера

Хорошо, а если не поддерживает? Т.е. не будем использовать никаких компиляторных оптимизаций.

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

Тут собственно весь интерес в том - можно ли создать такую функцию, скажем, на С++, не прибегая при этом к возне с ассемблером.

Задачка интересная. Я подумаю над ней, как будет время.

Но думаю что в виде функции нельзя. Хотя...

Объет вызывается на на стеке, а со спискаом

function a(): value->value;

function caller(function* f):
value val = 0;
while(1) val = f(val);

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

function a(): value->value;

хм, что-то вроде того, но тут точно ничего не будет в стек заноситься?

а какова конечная цель бесконечной рекурсии?

исключительно интереса ради.

> хм, что-то вроде того, но тут точно ничего не будет в стек заноситься?

Что такое стек. Это способ сохранения данных. Вызовы можно организвать и другим путем. Я его привел.

Задача у тебя именно в сохранении коненчо числа шагов. То есть в терминах совремных архитектур, необходимо чтоб в стеке выполнения было конечное заранее ограничено число функций

Все одно не понятно. Организовать бесконечность запросто, но память и пр. ресурсы конечны. Это реальность. Срек кончится и фсё, или ОЗУ или ХДД.

(define (f x) (g (- x 1)))
(define (g x) (f (+ x 1)))

Если компилятор не оптимизирует, стек очень быстро "фсё"

>>1: goto 1;

>нужна функция, а не просто бесконечный цикл.

Хвостовая рекурсия сводится к циклу.

>необходимо чтоб в стеке выполнения было конечное заранее ограничено число функций

Я бы даже сказал, что стек вообще не нужен, так как если что-то класть в него, то в пределе он всё равно переполнится.

>Организовать бесконечность запросто, но память и пр. ресурсы конечны. Это реальность.

Значит не будем использовать стек?

>Значит не будем использовать стек?

Тогда остается GOTO
:)

любая рекурсия сводится к коду без функций

>Но ведь все эти вызовы будут заноситься в стек, и рано или поздно возникнет Stack overflow.

Кольцевой буфер вместо стека

я полагаю требуется корректное поведение

>любая рекурсия сводится к коду без функций

Не любая. Функции бывает нужно помнить свои локальные переменные/параметры.

Бесконечная рекурсия в общем виде требует бесконечного стека по определению, так что корректной быть не может. Или её разворачивать нужно, или стек ненужный не использовать... Собственно, бесконечная рекурсия полного отката назад по определению же не требует, так что стек можно и похерить :) И, вообще:

      call loop
      return
loop:
      pop eax
      ; do something
      call loop

Вот вам бесконечная рекурсия без переполнения стека :D

Попробуй на бумаге посчитать (f 5), например.
Вот еще (для ценителей прекрасного):
((λ (x) (x x)) (λ (x) (x x))) - стек не используется.

>Вот вам бесконечная рекурсия без переполнения стека :D

Ну этак каждый может. Чел на сях приплюснутых хотел... и без оптимизации от компилятора! :)

>Кольцевой буфер вместо стека

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

>Собственно, бесконечная рекурсия полного отката назад по определению же не требует, так что стек можно и похерить

Вот всё в этой стране так и происходит. Самая фишка состоит в том, что необходимо организовать полный откат назад, иначе неинтересно. :)

let rec fib f1 f2 = [<'f1; fib f2 (f1 + f2)>];;

И никакого переполнения сетка.

Ну а в общем случае бесконечная рекурсия разумеется невозможна.

И че, даже fib(10000) посчитает?

выше уже говорилось - частные случаи не рассматриваем

Нет конечно. Хотя бы потому, что аргументами являются 2 числа, с которых надо начинать, а не номер числа, которое мы хотим получить.

> Не любая. Функции бывает нужно помнить свои локальные переменные/параметры.

Компьютер эквевалентен машине Тьюринга. Машину Тьюринга нерекурсивна. Дальше продолжать?

С таким колдунством не только числа Фибоначчи можно считать.

> Вот всё в этой стране так и происходит. Самая фишка состоит в том, что необходимо организовать полный откат назад, иначе неинтересно. :)

Тогда пожалусто назовите замое большое из натуральных чисел :)

void f(int n) return f(n); оно либо я чета не понял?

нет - но во многих практических задачах такое "колдунство" невозможно

>Тогда пожалусто назовите замое большое из натуральных чисел :)

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

>void f(int n) return f(n); оно либо я чета не понял?

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

не понял

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

ОК, тогда кодируй стек в своем бесконечном счетчике. Получится очень даже забавно. Ушел от потребления бесконечного количества памяти, а пришел к бесконечному росту значения счетчика. В чем профит?

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

let f = f

потом запускаешь f.

> Компьютер эквевалентен машине Тьюринга. Машину Тьюринга нерекурсивна. Дальше продолжать?

Продолжайте учить математическую логику. Конкретно - нумерацию Клини, тезис Чёрча, короче программу за первый курс университета.