✳flâneur — a map of the web's best reading

CSC 151 - Tail Recursion

eikmeier.sites.grinnell.edu · 2,267 words · saved by 1 readers

So far, we have not dwelled too much on program efficiency. By program efficiency, we mean two qualities: We will cover efficiency in depth in later courses. However, today we’ll cover a particular problem of efficiency as it pertains to recursion and functional programming. Our solution to this problem, tail recursion, is a fundamental part of every functional programming language. Consider the function (make-list n v) which makes a list of n copies of v, implemented recursively: And let’s trace its execution on an example: Observe the “essence” of this computation: for every element of the input list, we “pop out” a (cons "z" ...) call. These cons calls do not immediately evaluate! Instead, we continue making recursive calls until we hit the base case. It isn’t until after this point that we evaluate the five cons calls that we accumulate along the way. Looking at the trace, we see that if we pass in n to make-list, after k calls of make-list, we will have n-k pending calls to cons b

CSC 151 - Tail Recursion Tail Recursion Due Monday, 27 October 2025 --> So far, we have not dwelled too much on program efficiency . By program efficiency, we mean two qualities: Time efficiency : how long a program takes to run? Space efficiency : how much memory does a program consume during execution? We will cover efficiency in depth in later courses. However, today we’ll cover a particular problem of efficiency as it pertains to recursion and functional programming. Our solution to this problem, tail recursion , is a fundamental part of every functional programming language. Blowing the S

Explore this link on the map →

saved by

related reading