> 1 <
Автор | Сообщение |
boef
1 сообщений |
#6627 2012-09-26 23:00 GMT+3 часа(ов) |
Добрый день.
Подскажите, есть такое простое задание: Цитата Что я сделал:
Но преподаватель сказал, что я говно, что я ничего не понимаю и что нужно делать с хвостовой рекурсией. Блин, объясните пожалуйста, ну что такое это хвостовая рекурсия и чем она отличается от обычной рекурсии? «специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией» — ну правда, мне это не понятно. Вот что, если я перепишу функцию summ вот так: (define (sum L) То это будет уже хвостовая рекурсия? Если да, то что это за бред? Чем это отличается от того что было раньше? Если нет, то как надо? Подскажите, пожалуйста! Хочу разобраться. |
|
Oleg
2 сообщений |
#6628 2012-09-27 10:46 GMT+3 часа(ов) |
У хвостовой рекурсии нет остаточных вычислений.
(define (summ xs) (let f ([xs (reverse xs)][ys null][s 0]) (if (null? xs) ys (f (cdr xs) (cons (+ s (car xs)) ys) (+ s (car xs)))))) |
|
Aoloa
37 сообщений |
#6630 2012-10-02 17:51 GMT+3 часа(ов) |
Функция summ у Вас хвостовая, build — нет.
Удобно продемонстрировать работу Ваших функций: (summ '(1 2 3 4 5) 0) То есть на каждом шагу этой функции нужно хранить в памяти два аргумента. (build '(1 2 3 4 5)) То есть на каждом шагу этой функции число аргументов, которые нужно хранить в памяти, возрастает: на первом шагу один (список), на втором два (15 и список), на третьем три (15, 14, список)… (Кроме того, названия вызываемых функций тоже хранятся в памяти. То есть даже если бы функция была из одного аргумента, память бы всё равно расходовалась.) Чтобы рекурсия в функции build стала хвостовой, надо определить её так: (define (build L) Ну, или так: (define (build L) В таком варианте функция будет работать так: (build '(1 2 3 4 5)) Без переворачивания результатов, наверное, можно, но я не умею. При хвостовой рекурсии рекурсивный вызов должен быть хвостовым. Хвостовые вызовы — это те, которые выполняются последними. То есть в примере (- (ширина-объекта окно) (ширина-объекта кнопка)) вызовы функции ширина-объекта не являются хвостовыми, а вызов минуса (-) является, см. как они выполняются: (- (ширина-объекта окно) (ширина-объекта кнопка)) Но специальные формы, такие как (if ...), (let ...) не влияют на хвостовость вызова. В примере (if во-весь-экран (ширина-объекта экран) (ширина-объекта окно)) вызовы функции ширина-объекта являются хвостовыми, так как они выполняются так: (if во-весь-экран (ширина-объекта экран) (ширина-объекта окно)) Надеюсь, что понятно. |
|
With iTeX* your entire life can be encapsulated into a dynamic hyperdocument, downloadable by anybody you designate (Donald E. Knuth, An Earthshaking Announcement)
|
> 1 <