Fundamentals of Computer Science 1 (CS151 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Back to Discussion of Exam 2. On to Tail Recursion (2).
Held: Monday, 14 April 2003
Summary: Today we revisit recursion and consider a more efficient way to write recursive procedures. This technique is called tail recursion.
Related Pages:
Notes:
Overview:
add-to-all
, factorial
,
traditional right-associative sum
.
member?
, the left-associative sum
.
sum
(in class).
(define sumr (lambda (values) (if (null? values) 0 (+ (car values) (sumr (cdr values))))))
+ Version 2, left associative, tail recursive. (define suml (lambda (values) (letrec ((suml-helper (lambda (remaining-values partial-sum) (if (null? remaining-values) partial-sum (suml-helper (cdr remaining-values) (+ partial-sum (car remaining-values))))))) (suml-helper values 0))))
(1 2 3 4)
and see if one seems
to be easier to deal with.
(sumr (1 2 3 4)) --> (+ 1 (sumr (2 3 4))) --> (+ 1 (+ 2 (sumr (3 4)))) --> (+ 1 (+ 2 (+ 3 (sumr (4))))) --> (+ 1 (+ 2 (+ 3 (+ 4 (sumr ()))))) --> (+ 1 (+ 2 (+ 3 (+ 4 0)))) --> (+ 1 (+ 2 (+ 3 4))) --> (+ 1 (+ 2 7)) --> (+ 1 9) --> 10
(suml (1 2 3 4)) --> (suml-helper (1 2 3 4) 0) --> (suml-helper (2 3 4) 1) --> (suml-helper (3 4) 3) --> (suml-helper (4) 6) --> (suml-helper () 10) --> 10
things to do once the recursion reaches the base case.
suml
:
accumulatespartial solutions. Hence, we often call it an accumulator.
oldbase case (the one in the non-tail-recursive procedure).
Thursday, 16 January 2003 [Samuel A. Rebelsky]
Sunday, 13 April 2003 [Samuel A. Rebelsky]
suml
local).
Back to Discussion of Exam 2. On to Tail Recursion (2).
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Project]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Scheme Reference]
[Scheme Report]
[CS151 2003S Gum]
[CS151 2002F]
[CS151 History]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 6 09:30:13 2003.
The source to the document was last modified on Sun Apr 13 21:39:59 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Outlines/outline.41.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby