Недавно я начал читать SICP. , и я очень заинтересован в преобразовании рекурсивной процедуры в форму хвостовой рекурсии.
Для «одномерных» ситуаций (линейных), таких как ряд Фибоначчи или вычисление факториала, выполнить преобразование несложно.
Например, как говорится в книге, мы можем переписать вычисление Фибоначчи следующим образом.
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
И эта форма, очевидно, хвостовая рекурсия
Однако для «двумерной» ситуации, такой как вычисление треугольника Паскаля (пример 1.12 в SICP), мы все еще можем легко написать рекурсивное решение следующим образом.
(define (pascal x y)
(cond ((or (<= x 0) (<= y 0) (< x y )) 0)
((or (= 1 y) (= x y) ) 1)
(else (+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))
Вопрос в том, как преобразовать это в хвостовую рекурсивную форму?