Хвост-рекурсивный?

Question

Я пишу функцию, которая берет список и возвращает сумму квадратов всех элементов в списке. При вызове (1 2 3) он должен вернуть 14: (1 ² + 2 ² + 3 ² ).

У меня есть эта функция sqsum:

(define (sqsum lis)
    (if (null? lis)
        0
        (+ (* (car lis) (car lis)) (sqsum (cdr lis)))
    )
)

Является ли этот хвост рекурсивным? Я думаю, что это рекурсивно, но не рекурсивно. Это часть моей домашней работы, и я не ищу решения: я просто хочу знать, рекурсивный ли это хвост или нет. Если нет, то мне нужно больше узнать и найти новые решения.

Answer 1

Чтобы быть хвостовой рекурсией, рекурсия должна происходить в самой последней функции, то есть вы ничего не можете сделать с результатами рекурсивного вызова.Здесь вы передаете его +, что делает его нерекурсивным.Хотя компилятор может оптимизировать это, и это тоже довольно легко сделать самостоятельно.

Answer 2

Нет, это не хвостовая рекурсия.

Общий подход к созданию хвостовой рекурсивной функции хвостовой рекурсии состоит в том, чтобы включить аккумулятор, который является дополнительным аргументом, который передает текущую оценку процедуры через ваши рекурсивные вызовы.

Между прочим, именно здесь очень полезны "вспомогательные" функции. Общая практика состоит в том, чтобы определить вашу функцию так, чтобы она не брала аккумулятор, определяла в нем вспомогательную функцию, которая действительно собирает аккумулятор, и затем основная функция выполняет мало, кроме вызовите вспомогательную функцию. Через секунду вы поймете, что я имею в виду.

В вашем случае (если я правильно помню свою Схему: p):

(define (sqsum lis)
    (define (sqsum-h lis acc)
        (if (null? lis)
            acc
            (sqsum-h (cdr lis) (+ acc (* (car lis) (car lis))))
        )
    )
    (sqsum-h lis 0)
)

Это хвостовая рекурсия, потому что последнее, что делает любой рекурсивный вызов, - это немедленно возвращает результат другой функции без ее изменения.