Добрый день.
Подскажите, есть такое простое задание:

Цитата

---

Функция из исходного списка формирует список-результат: первый элемент — сумма всех элементов, второй — сумма элементов хвоста и т.д.

---

Что я сделал:

 

  (define (summ L result)

    (if (null? L)

        result

        (summ (cdr L)

              (+ result (car L))))))

(define (build L)

  (if (null? L)

      '()

      (cons (summ L 0)

            (build (cdr L)))))

 

Но преподаватель сказал, что я говно, что я ничего не понимаю и что нужно делать с хвостовой рекурсией.
Блин, объясните пожалуйста, ну что такое это хвостовая рекурсия и чем она отличается от обычной рекурсии?
«специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией» — ну правда, мне это не понятно.
Вот что, если я перепишу функцию summ вот так:

(define (sum L)

  (define (summ L result)

    (if (null? L)

        result

        (summ (cdr L)

              (+ result (car L)))))   

(summ L 0)) 

 

То это будет уже хвостовая рекурсия? Если да, то что это за бред? Чем это отличается от того что было раньше? Если нет, то как надо? Подскажите, пожалуйста! Хочу разобраться.

Функция summ у Вас хвостовая, build — нет.

Удобно продемонстрировать работу Ваших функций:

(summ '(1 2 3 4 5) 0)

(summ '(2 3 4 5) 1)

(summ '(3 4 5) 3)

(summ '(4 5) 6)

(summ '(5) 10)

(summ '() 15)

15

То есть на каждом шагу этой функции нужно хранить в памяти два аргумента.

(build '(1 2 3 4 5))

(cons 15 (build '(2 3 4 5)))

(cons 15 (cons 14 (build '(3 4 5))))

(cons 15 (cons 14 (cons 11 (build '(4 5)))))

(cons 15 (cons 14 (cons 11 (cons 9 (build '(5))))))

(cons 15 (cons 14 (cons 11 (cons 9 (cons 5 (build '()))))))

(cons 15 (cons 14 (cons 11 (cons 9 (cons 5 (build '()))))))

(cons 15 (cons 14 (cons 11 (cons 9 (cons 5 '())))))

(cons 15 (cons 14 (cons 11 (cons 9 '(5)))))

(cons 15 (cons 14 (cons 11 '(9 5))))

(cons 15 (cons 14 '(11 9 5)))

(cons 15 '(14 11 9 5))

'(15 14 11 9 5)

То есть на каждом шагу этой функции число аргументов, которые нужно хранить в памяти, возрастает: на первом шагу один (список), на втором два (15 и список), на третьем три (15, 14, список)… (Кроме того, названия вызываемых функций тоже хранятся в памяти. То есть даже если бы функция была из одного аргумента, память бы всё равно расходовалась.)

Чтобы рекурсия в функции build стала хвостовой, надо определить её так:

(define (build L)

  (define (build-iter L result)

    (if (null? L)

        (reverse result)

        (build-iter (cdr L) (cons (summ L 0) result)))

    (build-iter L '())))

Ну, или так:

(define (build L)

  (let ((build-iter (lambda (L result)

                      (if (null? L)

                          (reverse result)

                          (build-iter (cdr L) (cons (summ L 0) result))))))

         (build-iter L '())))

В таком варианте функция будет работать так:

(build '(1 2 3 4 5))

(build-iter '(1 2 3 4 5) '())

(build-iter '(2 3 4 5) '(5))

(build-iter '(3 4 5) '(4 5))

(build-iter '(4 5) '(11 14 15))

(build-iter '(5) '(9 11 14 15))

(build-iter '() '(5 9 11 14 15))

(reverse '(5 9 11 14 15))

'(15 14 11 9 5)

Без переворачивания результатов, наверное, можно, но я не умею.



При хвостовой рекурсии рекурсивный вызов должен быть хвостовым.

Хвостовые вызовы — это те, которые выполняются последними.

То есть в примере (- (ширина-объекта окно) (ширина-объекта кнопка)) вызовы функции ширина-объекта не являются хвостовыми, а вызов минуса (-) является, см. как они выполняются:

(- (ширина-объекта окно) (ширина-объекта кнопка))

(- 200 30)

170

Но специальные формы, такие как (if ...), (let ...) не влияют на хвостовость вызова.

В примере (if во-весь-экран (ширина-объекта экран) (ширина-объекта окно)) вызовы функции ширина-объекта являются хвостовыми, так как они выполняются так:

(if во-весь-экран (ширина-объекта экран) (ширина-объекта окно))

(if #f (ширина-объекта экран) (ширина-объекта окно))

(ширина-объекта окно)

200

Надеюсь, что понятно.