DR
А если в ф языках юзают рекурсию вместо лупов, то что если массив будет настолько длинный, что полюбому будет приводить к переполнению стека?
Size: a a a
2018 October 09
к
А если в ф языках юзают рекурсию вместо лупов, то что если массив будет настолько длинный, что полюбому будет приводить к переполнению стека?
- Хвостовая рекурсия
- Ленивая рекурсия в конструкторы
- Ленивая рекурсия в конструкторы
к
А если в ф языках юзают рекурсию вместо лупов, то что если массив будет настолько длинный, что полюбому будет приводить к переполнению стека?
Если про хвостовую рекурсию все понятно, то про рекурсию в данные пишут мало
Самый простой пример: map
Вот тут нужно в стеке что-то хранить в случае лени (да и без лени)?
Не нужно, потому что не нужно возвращаться к : и выполнять что-то
Самый простой пример: map
map f [] = []
map f (x:xs) = (f x):(map f xs)Вот тут нужно в стеке что-то хранить в случае лени (да и без лени)?
Не нужно, потому что не нужно возвращаться к : и выполнять что-то
к
Ну а про хвостовую рекурсию: луп и хвостовая рекурсия это одно и то же
к
fib n = iter (1, 1, n) where
iter (a, b, 1) = a
iter (a, b, n) = iter (b, a + b, n - 1)
fib(n) {
(a, b, n) = (1, 1, n)
loop {
if n == 1 then return a
(a, b, n) = (b, a + b, n - 1)
}
}
(defn fib [n]
(loop [a 1, b 1, n n]
(if (= n 1)
a
(recur b (+ a b) (dec n)))))DR
- Хвостовая рекурсия
- Ленивая рекурсия в конструкторы
- Ленивая рекурсия в конструкторы
Ок, правда не знаю ни первое, ни второе, из примеров кода не понятно, не знаю что за язык
к
Ок, правда не знаю ни первое, ни второе, из примеров кода не понятно, не знаю что за язык
первый пример - хаскель
второй - тоже
третий - неизвестный псевдоязык, синтаксис вроде должен быть понятен
четвертый - кложа
второй - тоже
третий - неизвестный псевдоязык, синтаксис вроде должен быть понятен
четвертый - кложа
к
function fib(n) {
let [a, b, i] = [1, 1, n];
while (true) {
if (i === 1) return a;
[a, b, i] = [b, a + b, i - 1];
}
}ну переписал псевдопример с циклом на жс
к
function fib(n) {
return fib_iter(1, 1, n);
}
function fib_iter(a, b, n) {
if (n == 1) return a;
return fib_iter(b, a + b, n - 1);
}к
ну и хвостовой рекурсии (оптимизации которой нет в жс)
DR
function fib(n) {
return fib_iter(1, 1, n);
}
function fib_iter(a, b, n) {
if (n == 1) return a;
return fib_iter(b, a + b, n - 1);
}Не очень понял, в сем прикол, вроде обычная рекурсия
к
почему появляется переполнения стека?
DR
Слишком много раз вызвана функция самой собой
NK
потому что стек кто-то переполнил
к
потому что в стек приходится класть:
- локальные переменные
- ссылку, чтобы вернуться назад по вызовам и продолжить выполнять код
то есть при
f(x) = 1 + f(x - 1)
мы прыгаем в f(x - 1), выполняем его, возвращаемся назад и продолжаем вычисление 1 + someResultFromFDecX
- локальные переменные
- ссылку, чтобы вернуться назад по вызовам и продолжить выполнять код
то есть при
f(x) = 1 + f(x - 1)
мы прыгаем в f(x - 1), выполняем его, возвращаемся назад и продолжаем вычисление 1 + someResultFromFDecX
к
function fib(n) {
return fib_iter(1, 1, n);
}
function fib_iter(a, b, n) {
if (n == 1) return a;
return fib_iter(b, a + b, n - 1);
}а тут нам не нужно прыгать по стеку назад, так как мы не делаем никаких вычислений после вычисления шага рекурсии, можно в стек вообще ничего не класть на шагах рекурсии
к
мы вместо кола делаем джамп на начало функции с новыми аргументами
к
нихуя себе