Tail Recursion

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Identifying Tail-Recursive Procedures
  • Exercise 2: Does Tail Recursion Really Make a Difference
  • Exercise 3: Make add-to-all Tail Recursive
  • Exercise 4: Finding the Longest String on a List
  • Exercise 5: Finding the Index
  • Exercise 6: Iota, Once Again
• Notes

Exercises

Exercise 0: Preparation

Please go over the short reading on tail recursion.

Exercise 1: Identifying Tail-Recursive Procedures

Identify two (or more) tail-recursive procedures you've written already.

Exercise 2: Does Tail Recursion Really Make a Difference

Try the two versions of factorial on some numbers that are big enough that you can observe a running time by counting ("one thousand one one thousand two ..."). Do you observe any significant difference in running times?

Exercise 3: Make add-to-all Tail Recursive

a. Make add-to-all tail recursive by using the list of things already added to as the accumulator (the second parameter to the kernel) and using append to extend the accumulator.

b. Make add-to-all tail recursive by using the reverse of the list of things already added to as the accumulator and cons to extend the accumulator.

c. Try some examples to see if you can determine whether or not there is a substantial difference in the running times of the three versions.

Exercise 4: Finding the Longest String on a List

Write a tail-recursive longest-string-on-list procedure.

Exercise 5: Finding the Index

Define a procedure index that has two arguments, an item a and a list of items ls, and returns the index of a in ls, that is, the zero-based location of a in ls. If the item is not in the list, the procedure returns -1. Test your procedure on:

  (index 3 '(1 2 3 4 5 6)) ===> 2
  (index 'so '(do re mi fa so la ti do)) ===> 4
  (index 'a '(b c d e)) ===> -1
  (index 'cat '()) ===> -1

Exercise 6: Iota, Once Again

Define and test a tail-recursive version of Iota.

Notes