Можно ли это превратить в хвостовую рекурсивную функцию?

Question

Пройдя через HtDP и столкнувшись с проблемой, которая была: Разработайте функцию умножить. Он потребляет натуральное число n и умножает его на некоторое произвольное число x без использования *.

Это то, что я придумал:

(define (multiply n x) 
    (cond 
    [(= x 1) n] 
    [else (+ n (multiply n (- x 1)))])) 

Это работает, но я думаю, что это не самое лучшее решение. Поскольку это можно было бы решить как цикл for, основанный на моем понимании, это должно быть хвостовым рекурсивным.

Answer 1

Ключевым моментом хвостовой рекурсией решение: сохранить инвариантное N * х + г = сопзЬ. В этом случае, когда x равно нулю, r содержит n * x.

(define (iter-mul n x r) 
    (cond ((= x 0) r) 
     (else (iter-mul n (- x 1) (+ r n))))) 

Вы можете использовать его как:

(define (mul n x) (iter-mul n x 0)) 

Answer 2

Возможно не самый изящный, но это, по крайней мере, хвостовой рекурсией:

(define (acc a n x) 
    (if(= x 0) 
    a 
    (acc (+ a n) n (- x 1)))) 

(define (multiply n x) 
    (acc 0 n x)) 

Answer 3

Процедура может быть легко преобразована в хвостовой рекурсии, используя параметр аккумулятора для хранения результата. Ниже для n >= 0 и x >= 0, и я использую названный let (loop - это процедура хвостового рекурсирования, не), чтобы избежать необходимости явно определять вспомогательную процедуру или добавлять другой параметр в процедуру , Вот как это сделать:

(define (multiply n x) 
    (let loop ((acc 0) 
      (x x)) 
    (cond 
     [(= x 0) acc] 
     [else (loop (+ n acc) (- x 1))]))) 

заметить также, что у вас есть ошибка в вашем коде, попробуйте запустить (multiply 1 0) - бесконечный цикл.

Answer 4

Теперь, когда другие показали вам, как сделать функцию tail-recursive, вот альтернативная версия функции, чтобы умножить два положительных целых числа, которые намного быстрее, чем тот, который вы дали. Вы видите, как работает эта функция?

(define (times x y) 
    (let loop ((x x) (y y) (z 0)) 
    (if (zero? x) z 
     (loop (quotient x 2) (+ y y) 
      (if (odd? x) (+ y z) z)))))