Late afternoon, yesterday, when the sky was bluer than blue, my intelligent cat, Bin, asked me:

Dad. Why is linear recursion called linear? I petted Bin and smiled. A very smart cat, that, probably because he had been with us since he was merely weeks old.

I replied:

Dear Binbin, have a look at this function:

Bin yawned:

I know this.

I:

What happens if I pass 3 to it?

Well, something like 1 * 2 * 3 = 6.

Does it all happen at once?

Lemesee. As I do (factorial 3), Since it’s n is 3 and not 0, we go to recursive call. Here, some outcome should be multiplied to our n. Oh I see! This multiplication to n does not happen immediately. It has to wait for some other process to complete.

Your intelligence amazes me, Bin. Here’s a snack. Eat it later! Now look at this, in particular, look at line 4:

What am I looking at?

The darker green shade implies that, that is what is computed first. It’s computation priority inside the list processing languages like Scheme and Lisp.

Ah! I can say it, I can say it. Before 3 is multiplied to anything it can be multiplied to—

A number.

Yes, a number, don’t interrupt dad. It has to wait for the recursive call to go all the way to the base case.

More precisely son, each * waits for the inner factorial to finish before it can execute. The call stack builds up as you go deeper (3 → 2 → 1 → 0), then collapses as results bubble back up.

Whoa, whoa, easy dad. Let me show you how to write more intuitively (though less rigorously):

At line 5, in the previous image, all this unstacks and

So now I understand those arrows you showed in the first screenshot. Everything happens linearly, one after another. Right?

Absolutely. Now let’s look at another function, which we have written like so:

Dad, whoa, whoa, what’s happening and when?

Let’s run an x-ray on it:

The darker areas are computed first. In this case, line 5, as the whole line is green, whereas the if-clause’s if is slightly lighter.

Ok, so far it makes sense. Then what?

Then, we created a helper function inside (factorial n). It takes n but also an accumulator. Since n is continually decreased, eventually the base case is saying: return the accumulator once n is 0.

Oh, oh, and since in (factorial 3) n is not 0, it goes to (iter….) line. There, the n parameter for (iter n acc) is (- n 1) and the acc parameter is (* n acc). Am I right?

You are. Thus, there’s no waiting—each call immediately computes the new accumulator and passes it to the next call. The stack never grows because the recursive call is the final operation.

Dad, let me rephrase you so that even cats can understand it:

So, correct me if I am wrong: this is iterative?

The recursive call is the last operation (aka tail position). R5RS mandates that Scheme implementations optimize this into a loop—so the call stack remains constant regardless of depth. This is functionally iterative despite syntactic recursion.

Dad, please don’t show off your dense writing. I know you can write a fluffier version, please do, since the above went well over my head. I chuckled. My cat is a stickler for clarity.

As you wish Bin. Let’s go back a bit. In(define (iter n acc) (if (= n 0) acc(iter (- n 1) (* n acc))))

The last operation is (iter (- n 1) (* n acc)). After that line executes, there’s nothing else to do—no waiting, no multiplication to perform on the result.

Now compare to linear recursion:(define (factorial n)(if (= n 0) 1(* n (factorial (- n 1)))))

The recursive call is (factorial (- n 1)), but it’s not the last operation. After it returns, you still need to do (* n …) with that result. The * operation is waiting.

Ah I see. And?

And that, when Scheme sees a recursive call in tail position, it doesn’t create a new stack frame—it reuses the current one. So syntactically it’s still recursion (we wrote a recursive function), but operationally it behaves like a loop.

Grrrr. Wattt? Bin always makes me laugh. Especially when I say something that may sound confusing. So I pulled a respectable textbook by authors who are passionate about both programming and teaching, and showed him this:

Bin’s eyes distended:

So, Scheme considers recursive procedures as iteration?

Why not? Performance-wise at least, they are the same. Scheme takes something like:

And optimizes it to roughly something like this:

Same stack frame gets reused, same memory usage. Bin said:

Let me improve the above sentence, since you write like a mathematician:

Scheme says: “If you write it recursively in tail position, we’ll execute it as a loop.”

Proud of you, Bin! Well done. I confess I get impatient and want to say as much as possible in as few words as I can.

Yeah, dad, but don’t over do it. When you’re teaching, or writing tutorials, you could relax a bit and write with patience.

Noted, Bin. Thanks little fella for the reminder. It’s always so easy to forget one (too) was a beginner once.