Кажется, я нашел общий способ преобразования любой рекурсивной процедуры в хвостовую рекурсию:

1. Определите вспомогательную подпроцедуру с дополнительным параметром «result».
2. Примените то, что будет применено к возвращаемому значению процедуры к этому параметру.
3. Вызовите эту вспомогательную процедуру, чтобы начать. Начальным значением для параметра «result» является значение для точки выхода рекурсивного процесса, поэтому итоговый итерационный процесс начинается с того места, где рекурсивный процесс начинает сокращаться.

Например, вот оригинальная рекурсивная процедура для преобразования ( упражнение SICP 1.17 ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Вот преобразованная хвосто-рекурсивная процедура ( упражнение SICP 1.18 ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Может кто-то доказать или опровергнуть это?

Ваше описание вашего алгоритма действительно слишком расплывчато, чтобы оценить его на данный момент. Но вот некоторые вещи для рассмотрения.

КПС

Фактически, есть способ преобразовать любой код в форму, которая использует только хвостовые вызовы. Это преобразование CPS. CPS ( Continuation-Passing Style ) - это форма выражения кода, передавая каждой функции продолжение. Продолжением является абстрактное понятие, представляющее «остальную часть вычисления». В коде , выраженной в виде CPS, естественный способ материализовать продолжение является как функция , которая принимает значение. В CPS вместо функции, возвращающей значение, она применяет функцию, представляющую текущее продолжение, к функции, «возвращаемой» функцией.

Например, рассмотрим следующую функцию:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Это может быть выражено в CPS следующим образом:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

Это уродливо и часто медленно, но у него есть определенные преимущества:

• Преобразование может быть полностью автоматизировано. Поэтому нет необходимости писать (или видеть) код в форме CPS.
• В сочетании с thunking и trampolining он может использоваться для обеспечения оптимизации хвостового вызова на языках, которые не обеспечивают оптимизацию хвостового вызова. (Оптимизация хвостового вызова непосредственно хвостовой рекурсивной функции может быть выполнена с помощью других средств, таких как преобразование рекурсивного вызова в цикл. Но косвенная рекурсия не так тривиальна для преобразования таким способом.)
• С CPS продолжения становятся первоклассными объектами. Поскольку продолжения являются сущностью управления, это позволяет реализовать практически любой оператор управления в виде библиотеки, не требуя специальной поддержки языка. Например, goto, исключения и совместная обработка потоков могут быть смоделированы с использованием продолжений.

TCO

Мне кажется, что единственная причина, связанная с хвостовой рекурсией (или хвостовыми вызовами в целом), заключается в целях оптимизации хвостовых вызовов (TCO). Поэтому я думаю, что лучше задать вопрос: «Может ли мой код преобразования преобразовать с помощью хвостового вызова?».

Если мы еще раз рассмотрим CPS, одной из его характеристик является то, что код, выраженный в CPS, состоит исключительно из хвостовых вызовов. Поскольку все является хвостовым вызовом, нам не нужно сохранять точку возврата в стек. Таким образом, весь код в форме CPS должен быть оптимизирован с помощью хвостового вызова, верно?

Ну, не совсем. Видите ли, хотя может показаться, что мы удалили стек, все, что мы сделали, это просто изменили способ его представления. Стек теперь является частью замыкания, представляющего продолжение. Таким образом, CPS волшебным образом не делает весь наш код оптимизированным.

Так что, если CPS не может сделать все TCO, существует ли преобразование специально для прямой рекурсии, которое может? Нет не вообще. Некоторые рекурсии линейны, а некоторые нет. Нелинейные (например, древовидные) рекурсии просто должны где-то поддерживать переменное количество состояний.