Wygląda na to, że znalazłem ogólny sposób na konwersję dowolnej procedury rekurencyjnej na rekurencyjną:

1. Zdefiniuj podprocedurę pomocnika z dodatkowym parametrem „wynik”.
2. Zastosuj to, co zostanie zastosowane do wartości zwracanej przez procedurę do tego parametru.
3. Zadzwoń do tej procedury pomocnika, aby rozpocząć. Wartość początkowa parametru „wynik” jest wartością punktu wyjścia procesu rekurencyjnego, tak że wynikowy proces iteracyjny rozpoczyna się od miejsca, w którym proces rekurencyjny zaczyna się kurczyć.

Na przykład tutaj jest oryginalna procedura rekurencyjna do konwersji ( ćwiczenie 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))))

Oto konwertowana procedura rekurencyjna ( ćwiczenie 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))

Czy ktoś może to udowodnić lub obalić?

Twój opis algorytmu jest naprawdę zbyt niejasny, aby go ocenić w tym momencie. Ale oto kilka rzeczy do rozważenia.

CPS

W rzeczywistości istnieje sposób na przekształcenie dowolnego kodu w formę, która używa tylko wywołań tail. To jest transformacja CPS. CPS ( Continuation-Passing Style ) to forma wyrażania kodu poprzez przekazywanie każdej funkcji kontynuacji. Kontynuacja jest abstrakcyjnym pojęciem reprezentującym „resztę obliczeń”. W kodzie wyrażonym w postaci CPS naturalnym sposobem potwierdzenia kontynuacji jest funkcja, która przyjmuje wartość. W CPS zamiast funkcji zwracającej wartość, stosuje funkcję reprezentującą bieżącą kontynuację do bycia „zwróconym” przez funkcję.

Rozważmy na przykład następującą funkcję:

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

Można to wyrazić w CPS w następujący sposób:

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

Jest brzydka i często powolna, ale ma pewne zalety:

• Transformacja może być całkowicie zautomatyzowana. Nie ma więc potrzeby pisania (lub wyświetlania) kodu w postaci CPS.
• W połączeniu z „ thunking” i „trampolinowaniem” można go wykorzystać do optymalizacji optymalizacji przywołania ogona w językach, które nie zapewniają optymalizacji przywołania ogona. (Optymalizację funkcji wywołania ogona bezpośrednio rekursywnych funkcji ogona można osiągnąć innymi sposobami, takimi jak przekształcenie wywołania rekurencyjnego w pętlę. Jednak rekurencja pośrednia nie jest tak łatwa do konwersji w ten sposób.)
• Dzięki CPS kontynuacje stają się pierwszorzędnymi obiektami. Ponieważ kontynuacje są istotą kontroli, umożliwia to praktycznie każdemu operatorowi kontroli wdrożenie jako bibliotekę bez konieczności specjalnego wsparcia ze strony języka. Na przykład goto, wyjątki i gwintowanie kooperacyjne można modelować za pomocą kontynuacji.

TCO

Wydaje mi się, że jedynym powodem, dla którego należy zajmować się rekurencją ogona (lub ogólnie ogłaszaniem ogonów), jest dla celów optymalizacji ogonów ogonowych (TCO). Wydaje mi się, że lepszym pytaniem jest „czy mój kod wydajności transformacji, który można zoptymalizować na żądanie?”.

Jeśli jeszcze raz rozważymy CPS, jedną z jego cech jest to, że kod wyrażony w CPS składa się wyłącznie z wywołań tail. Ponieważ wszystko jest na żądanie, nie musimy zapisywać punktu zwrotu na stosie. Więc cały kod w postaci CPS musi być zoptymalizowany pod kątem wywołania ogona, prawda?

Cóż, niezupełnie. Widzisz, chociaż może się wydawać, że wyeliminowaliśmy stos, wszystko, co zrobiliśmy, to po prostu zmiana sposobu, w jaki go reprezentujemy. Stos jest teraz częścią zamknięcia reprezentującego kontynuację. Więc CPS nie magicznie optymalizuje całego naszego kodu do wywołania ogona.

Więc jeśli CPS nie jest w stanie zrobić wszystkiego TCO, to czy istnieje transformacja specjalnie do bezpośredniej rekurencji, która może? Nie, ogólnie nie. Niektóre rekurencje są liniowe, ale niektóre nie. Rekurencje nieliniowe (np. Drzewa) muszą po prostu utrzymywać gdzieś zmienną liczbę stanów.