Поверните рекурсивную/итеративную процедуру в полностью рекурсивную процедуру

Question

В настоящее время я пишу простую программу на Схеме, которая объединяет числа вместе рекурсивно и без использования оператора +. Сейчас у меня есть эта программа, которая делает то, что я хочу сделать:

(define (add1 x) (+ x 1)) 

(define (sub1 x) (- x 1)) 

(define (plus x y) 
    (if (zero? y) 
     x 
     (plus (add1 x) (sub1 y)) 
    ) 
) 

Однако мой учитель попросил меня опустить хвост рекурсии/итерацию и написать процедуру плюс полностью рекурсивно. Не рассказывая мне слишком много (это, в конце концов, упражнение Юни), можете ли вы указать мне в правильном направлении, чтобы выяснить, как это сделать?

Заранее благодарен!

Answer 1

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

(define (plus x y) 
    (if (zero? y) ; the first part remains unchanged 
     x 
     <???>)) ; now, what do we put here? 

Вы должны add1 на каждом шаге рекурсии, идея заключается в том, что вы продолжаете добавлять 1 точно y раз, и в конце концов вы добавить это x. Позвольте мне показать это на примере, чтобы добавить 4 плюс 3 мы это делаем:

(plus 4 3) 

который расширяет это:

(add1 (plus 4 2)) 
(add1 (add1 (plus 4 1))) 
(add1 (add1 (add1 (plus 4 0)))) 
(add1 (add1 (add1 4))) 

В выше, 4 был связан с x и 3 к y в начало, а после выполнения программы мы видим, что add1 был вызван три раза, первый раз добавляем 1 в 4, затем 1 - 5 и, наконец, 1 до 6, до получения 7. Другими словами: рекурсивный шаг должен вызвать add1 к результату рекурсивно ссылающегося plus, где x остается неизменным и y уменьшается на одну единицу, пока не достигнет нуля, и в этот момент мы достигаем базовый случай и рекурсия раскручивается возвращения правильный результат.