LINUX.ORG.RU

Рекурсия


0

0

Какие языки поддерживают полноценную рекурсию? А то во всех языках она есть, но на деле воспользоваться не получается, т.к. переполняется стек. Поэтому всегда приходится использовать циклы. А хвостовая рекурсия - фиговый листочек, т.к. это просто другая запись того же цикла, т.е. f(x) { ... f(x-1) } это же while(1) { ... x = x-1 }

Хотелось бы иметь возможность пометить рекурсивную функцию специальным ключевым словом, чтобы она все локальные переменные и информацию о вызовах хранила не на стеке, а в куче.

★★

>Какие языки поддерживают полноценную рекурсию?

ты часом не путаешь языки с их реализациями?

jtootf ★★★★★
()

> чтобы она все локальные переменные и информацию о вызовах хранила не на стеке, а в куче.

Просто увеличь стек.

tailgunner ★★★★★
()
Ответ на: комментарий от xTERM

> А если заранее не известно, на сколько увеличивать?

Если неизвестно, то как тебе поможет куча?

> Или это можно сделать в рантайме?

Ну если совсем втупую, то при создании нити можно указать ее размер стека - для особо глубокой рекурсии создавай новую нить :)

Наверняка можно поиграть с mmap и mremap и для главной нити.

tailgunner ★★★★★
()

Вряд ли это где то есть, но вообще идея реализации стека вызовов не аппаратным стеком а связанным списком мне нравится. Тормозить только будет в разы больше :)

Точнее это точно есть в некоторых реализациях Scheme. Но по эффективности проигрывает классическому. Зато continuations делаются за O(1) кажется.

Legioner ★★★★★
()

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

// use this method for deep recursion into fptr
void deep_invoke(void(*fptr)()) {
if (в стеке ещё много места) {
(*fptr)();
} else {
void *new_sp = malloc(...);
void* old_sp = set_sp(new_sp); // меняет указатель стека, возвращает старое значение
(*fptr)();
set_sp(old_sp);
free(new_sp);
}

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

alexsaa
()
Ответ на: комментарий от xTERM

>Или это можно сделать в рантайме?

Можно. В JBForth при переполнении стека в stdout идёт warning, а резерв памяти на стеке удваивается :)

KRoN73 ★★★★★
()

sbrk/brk не оно?

anonymous
()

Делаешь свой стек с блекджеком и шлюхами и не паришся.

wfrr ★★☆
()
Ответ на: комментарий от tailgunner

> Просто увеличь стек.

До меня доходили слухи, что ms windows умеет на ходу увеличивать стэк, если программа исчерпала свой

www_linux_org_ru ★★★★★
()
Ответ на: комментарий от xTERM

> А если заранее не известно, на сколько увеличивать? Или это можно сделать в рантайме?

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

www_linux_org_ru ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.