[scheme] рекурсия против итерации

А где ты итерацию увидел? Во втором случае создаётся такая же лямбда, только у нёё 2 параметра вместо одного, вот и работает чуть дольше. Суть tail-call заключается в том, что рекурсия не ест бессмысленно стек.

Вообще, как я понимаю, в первом случае расход памяти O(n), во втором O(1), скорость тут по идее не при чём. Если где то неправ - поправьте, тоже интересно.

с чего вы взяли, что во втором случае o(1)? там то же самое - чем больше n, тем дольше будет работать. o(n)

> с чего вы взяли, что во втором случае o(1)? там то же самое - чем больше n, тем дольше будет работать. o(n)

прошу прощения, торможу. пропустил ключевые слова - "расход памяти".

> А где ты итерацию увидел?
Ну во втором случае tail call optimisation будет, так? Т.е. это будет
итеративный процесс. Состояние вычисление будет передаваться как параметр, а не складываться на стек.

> с чего вы взяли, что во втором случае o(1)?

господа, не путаем О большое и о малое

> господа, не путаем О большое и о малое

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

> Ну во втором случае tail call optimisation будет, так? Т.е. это будет итеративный процесс. Состояние вычисление будет передаваться как параметр, а не складываться на стек.

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

В первом случае рекурсия не хвостовая.

Из-за чего?

(* n (factorial-1 (- n 1))))))

вычисляется так:
1. n -> n
2. (- n 1) ; вызов функции
3. (factorial-1 <результат 2>) ; вызов функции (рекурсивный, не хвостовой)
4. (* <результат 1> <результат 2>) ; вот здесь идёт tail-call, но это особого выигрыша не даёт.

Сори, я не лиспер, но как работает такой вариант: (define factorial-back (lambda (f, n) (if (zero? n) f (factorial-back (* f n) (- n 1)))))

(define factorial (lambda (n) (factorial-back 1 n )))

?

> Сори, я не лиспер, но как работает такой вариант
Тут хвостовая рекурсия будет, т.к. рекурсивный вызов находится в
_хвосте_ вычисления, и от этого вызова в текущем вызове
factorial-back ничего не зависит. Т.е. текущий call frame на
стеке может быть просто заменен на новый. Стек зазря не жрется.

А почему bytes allocated так отличаются?

Я вообще не очень понимаю, как у тебя получается считать 16384!, это же дочерта :) Мой csi дает стабильно +inf за тысячную долю секунды.

В твоем случае разница, скорее всего, из-за специфической реализации твоего интерпретатора.