> 1 <

Автор Сообщение

boef

Members


Статус

1 сообщений

Где: Russia Deep Town
Род занятий: Студент
Возраст: 24

#6627   2012-09-26 23:00 GMT+3 часа(ов)      
Добрый день.
Подскажите, есть такое простое задание:
Цитата
Функция из исходного списка формирует список-результат: первый элемент — сумма всех элементов, второй — сумма элементов хвоста и т.д.

Что я сделал:
 
(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))
 

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

Oleg

Members


Статус

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

Members


Статус

37 сообщений

Где: Ukraine
Род занятий:
Возраст:

#6630   2012-10-02 17:51 GMT+3 часа(ов)      
Функция 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



Надеюсь, что понятно.
With iTeX* your entire life can be encapsulated into a dynamic hyperdocument, downloadable by anybody you designate (Donald E. Knuth, An Earthshaking Announcement)
> 1 <


Онлайн :

0 пользователь(ей), 6 гость(ей) :




Реклама на сайте: