I am done with chapter 15 of Simply Scheme. I have been working through SS for a while. Sometimes I come home from work, and I do not feel like doing anything. Or I get stuck and take a break.
I took a break when I got to chapter 9. Then I started back up, and flew through lambdas and recursion. I started making my answers tail-recursive, so mine were a bit bigger than other repos I found with answers. They do not cover tail recursion in the text, but I thought it was a good idea to work on it. I got stuck on question 5 in Chapter 15. I ported my answers to Clojure, then to Racket (with the emacs Racket mode). Eventually I wound up back at the question I had problems with.
I spent a lot of time on it, and I think the problem was that I was trying both do it with tail recursion and to follow the text’s recommendation, which is NOT tail-recursive. I was having no luck with the “Leap of Faith”, so I decided to try solving the problem with higher-order functions, and then port the answers to recursion. In Chapter 14, they have a section called “How To Use Recursive Patterns” in which they show how to use recursion to do every/map, keep/filter and accumulate/reduce. Doing it that way, I solved the problem pretty quickly.
I think I read somewhere that if you have the choice to use recursion or higher-order functions, you should use higher order functions.
I ran some tests comparing my solutions (one with recursion and one with every) with someone who followed the text’s recommended solution. Usually theirs was a bit faster. But if you give the functions a number with 8 digits, mine are noticeably faster.
At first I thought that “tail recursion” meant that the “tail call” had to be at the bottom of a function. I kind of thought that is what people meant when they said the recursive call had to be the last thing called. But you can have tail recursion even in every branch of a cond or an if statement.
Here are a couple of implementations of factorial from a CS course at the University of Washington:
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
This is not tail-recursive. For Lisp languages, you can tell what order things are called in by starting at the innermost parens and working outward. First, the minus function is called. Then the recursive “factorial” function is called. Then the multiply function is called. Then the system leaves the function.
Here is a tail-recursive version:
(define (factorial n)
(acc-factorial n 1))
;; auxiliary function that takes an additional parameter (the accumulator,
;; i.e. the result computed so far)
(define (acc-factorial n sofar)
(if (zero? n)
sofar
(acc-factorial (- n 1) (* sofar n))))
First off, you need another argument for your function. Think of having one as an “input” (which in this case gets decremented to 0 with each call) and an “output” (or accumulator), which holds the increasing total. If we look at the line in “acc-factorial” where it calls itself, it calls the minus and multiply functions, and THEN makes a recursive call. And that call would cause the system to exit the function (or that instance of the function). In the first function, it makes the recursive call, then it makes the call to multiply, and THEN it exits the function.
I hope I understood that. I am not going to name-and-shame, but while writing this I found a gist on github that the author claimed was a tail-recursive factorial in Scheme, but it looks more like the first example I posted from UWash and not the second. So either our mystery gist-er misunderstands tail-recursion, or I do.
You’re welcome.
Image from León Bible of 960, a 10th century Bible manuscript housed in the Basilica of San Isidoro, León; image from Wikimedia, assumed allowed under Fair Use.