(Untitled)

[kincajou]

Реализовал "оптимизацию хвостовой рекурсии" в самом простом виде. Работает так: если функция "видит", что она вызывает самоё себя, то новый вложенный контекст не создаётся и пересчитанные значения аргументов перезаписываются на текущий уровень. Сэкономило заметное количество malloc/free. Чтобы механизм сработал как надо, "сам себе вызов" не должен

Comments

[artworklv]

На гитхаб не желаешь выложить?
Было бы интересно видеть эволюцию проекта, покоммитово.

[kincajou]

мне пока стыдно

[artworklv]

Стыдно писать на Похапэ всю жизнь :)
Вливайся! Рецензентов подгоню, нерусских.

[oppositus]

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

[kincajou]

я прочитал, но пока не всё понял.

[oppositus]

В общем, хвостовая рекурсия возможна, если на стеке не осталось операций. Вот так не получится хвостовой:

function foo (arg) { return 1 + foo (arg / 2); }

Если у нас стековая машина, то мы должны положить в стек 1, результат вызова foo (arg / 2) и потом вернуть результат оператора + от последнего и предпоследнего элементов стека. То есть, мы должны выполнить операцию после того, как вызовем другую функцию.

А вот так хвостовая рекурсия получится:

function foo (arg1) { return bar (arg1 / 2); }
function bar (arg1) { return foo (arg2 * 2); }

Потому что мы возвращаем результат работы функции, с которым больше ничего не надо делать.

[oppositus]

Можно по-другому сформулировать (для стековой машины, для регистровой примерно так же получится