# How to understand this recursion code?

I found this code in the manual `An Introduction to Programming in Emacs Lisp` demonstrating recursion with the help of `cond` function to find out the number of pebbles based on the entered number of rows, i.e. if rows = 2, then pebbles should be 3, if 4 rows then it should be 10 pebbles there.

``````(defun triangle-using-cond (number)
(cond ((<= number 0) 0)
((= number 1) 1)
((> number 1)
(+ number (triangle-using-cond (1- number))))))
``````

evaluate to 10 after passing argument 4:

``````(triangle-using-cond 4)
``````

The manual did not explain clearly what happens at each step in this example code in particular and I couldn't figure out how recursion works here. Can you pls help me understand the mechanics step-by-step what happens at each instance?

• I'll let someone else help you with the word "recursion" (because I think of it as being something different than in this context) or better explain what I'm about to write: (a) if number is less than or equal to 0, then 0; (b) if number equals 1, then 1; (c) if number is greater than 1, then add number to the value returned by the function `triangle-using-cond` with the argument being 1 less than whatever the number is. The conditions go in order of a, b, and then c -- whatever matches first, is where the buck stops. Nov 6, 2014 at 20:17
• as usual elisp interpreter evaluates from innermost to outermost. Thus, `1-4 = 3`. Now the recursive call will be `(triangle-using-cond 3)`, but that will end up with the same recursive call again and again until it hits the 1 conditional, right? what will happen next? Nov 6, 2014 at 20:24
• Oh, I see -- the function reuses itself at step 3 -- okay, good point. Nov 6, 2014 at 20:27
• I wonder what would be the result of `(triangle-using-cond 3)`? Nov 6, 2014 at 20:31
• n.b. The function `1-` has a particularly misleading name, especially if you read a call as if it were infix notation. It returns its argument minus one; NOT one minus the argument. Nov 6, 2014 at 20:34

## Using "printf debugging"

You could let Emacs help you understand by modifying the function definition:

``````(defun triangle-using-cond (number)
(message (format "called with %d" number))
(cond ((<= number 0) 0)
((= number 1) 1)
((> number 1)
(+ number (triangle-using-cond (1- number))))))
``````

Just add `(message ...)` somewhere to have a trail printed to the `*Messages*` buffer.

## Using Edebug

Place point anywhere inside the function definition and hit `C-u C-M-x` to "instrument" it. Then evaluate the function, e.g. by placing point after `(triangle-using-cond 3)` and hitting `C-x C-e`.

You are now in Edebug mode. Hit the space bar to step through the function. The intermediate values of each expression are shown in the echo area. To exit Edebug mode just hit `q`. To remove the instrumentation, put point anywhere inside the definition and hit `C-M-x` to re-evaluate the definition.

## Using the standard Emacs debugger

`M-x debug-on-entry triangle-using-cond`, then, when `triangle-using-cond` is invoked, you are placed in the Emacs debugger (buffer `*Backtrace*`).

Step through the evaluation using `d` (or `c` to skip through any uninteresting evaluations).

To see intermediate state (variable values, etc.) you can use `e` anytime. You are prompted to enter a sexp to evaluate, and the evaluation result is printed.

While you use the debugger, keep a copy of the source code visible in another frame, so you can follow what's going on.

You can also insert explicit calls to enter the debugger (more or less breakpoints) at arbitrary places in the source code. You insert `(debug)` or `(debug nil SOME-SEXP-TO-EVALUATE)`. In the latter case, when the debugger is entered `SOME-SEXP-TO-EVALUATE` is evaluated and the result is printed. (Remember that you can insert such code into the source code and use `C-M-x` to evaluate it, then undo - you need not save the edited file.)

See the Elisp manual, node `Using Debugger` for more information.

## Recursion as a loop

Anyway, think of recursion as a loop. There are two termination cases defined: `(<= number 0)` and `(= number 1)`. In these cases the function returns a simple number.

In the recursive case the function returns the sum of that number and the result of the function with `number - 1`. Eventually, the function will be called with either `1` or a number smaller than or equal to zero.

The recursive case result is hence:

``````(+ number (+ (1- number) (+ (1- (1- number)) ... 1)
``````

Take for example `(triangle-using-cond 4)`. Let's accumulate the final expression:

• in the first iteration `number` is `4`, so the `(> number 1)` branch is followed. We start building an expression `(+ 4 ...` and call the function with `(1- 4)`, i.e. `(triangle-using-cond 3)`.

• now `number` is `3`, and the result is `(+ 3 (triangle-using-cond 2))`. The total result expression is `(+ 4 (+ 3 (triangle-using-cond 2)))`.

• `number` is `2` now, so the expression is `(+ 4 (+ 3 (+ 2 (triangle-using-cond 1))))`

• `number` is `1` now, and we take the `(= number 1)` branch, resulting in a boring `1`. The whole expression is `(+ 4 (+ 3 (+ 2 1)))`. Evaluate that from the inside out and you get: `(+ 4 (+ 3 3))`, `(+ 4 6)`, or just `10`.

• Edebug will be even better. =) Nov 6, 2014 at 20:33
• how to get the trail printed using the `message (...)`, hitting `C-x C-e` just shows the final result (10) nothing else? Am I missing something? Nov 6, 2014 at 21:06
• @Malabarba, how to put `Edebug` in action? Nov 6, 2014 at 21:08
• @doctorate hit `C-u C-M-x` with point inside the function to edebug it. Then just run the function as normal. Nov 6, 2014 at 21:43
• @doctorate the `(message ...)` stuff prints to the `*Message*` buffer.
– user2005
Nov 6, 2014 at 21:52

The Substitution Model for Procedure Application from SICP can explain the algorithm to understanding code like this.

I wrote some code to facilitate this as well. `lispy-flatten` from lispy package does this. Here's the result of applying `lispy-flatten` to `(triangle-using-cond 4)`:

``````(cond ((<= 4 0)
0)
((= 4 1)
1)
((> 4 1)
(+ 4 (triangle-using-cond (1- 4)))))
``````

You can simplify the above expression to just:

``````(+ 4 (triangle-using-cond 3))
``````

Then flatten once more:

``````(+ 4 (cond ((<= 3 0)
0)
((= 3 1)
1)
((> 3 1)
(+ 3 (triangle-using-cond (1- 3))))))
``````

The final result:

``````(+ 4 (+ 3 (+ 2 1)))
``````

This is not specific to Emacs / Elisp, but if you have a mathematics background, then recursion is like mathematical induction. (Or if you don't: then when you learn induction, it's like recursion!)

``````(defun triangle-using-cond (number)
(cond ((<= number 0) 0)
((= number 1) 1)
((> number 1)
(+ number (triangle-using-cond (1- number))))))
``````

When `number` is `4`, neither of the first two conditions hold, so it's evaluated according to the third condition:
`(triangle-using-cond 4)` is evaluated as
`(+ number (triangle-using-cond (1- number)))`, namely as
`(+ 4 (triangle-using-cond 3))`.

Similarly,
`(triangle-using-cond 3)` is evaluated as
`(+ 3 (triangle-using-cond 2))`.

Similarly, `(triangle-using-cond 2)` is evaluated as
`(+ 2 (triangle-using-cond 1))`.

But for `(triangle-using-cond 1)`, the second condition holds, and it is evaluated as `1`.

A piece of advice for anyone learning recursion: try to avoid

the common beginner mistake of trying to think about what happens during the recursive call instead of trusting that the recursive call works (sometimes called the recursive leap of faith).

If you're trying to convince yourself whether `(triangle-using-cond 4)` will return the correct answer, just assume that `(triangle-using-cond 3)` will return the right answer, and verify whether it will be correct in that case. Of course you have to verify the base case too.

The calculation steps for your example would be like the following:

``````(4 +               ;; step 1
(3 +            ;; step 2
(2 +         ;; step 3
(1))))    ;; step 4
=> 10
``````

The 0 condition is actually never met because 1 as an input already ends the recursion.

• `(1)` is not a valid expression.
– user2005
Nov 6, 2014 at 20:40
• It evaluates just fine with `M-x calc`. :-) Seriously though, I meant to show the calculation, not the Lisp evaluation. Nov 6, 2014 at 20:46
• Oh, I didn't even notice that it's `(4 +` instead of `(+ 4` in your answer ... :)
– user2005
Nov 6, 2014 at 20:54

I think it's pretty easy, you don't need emacs lisp to under this, it's just elementary school math.

f(0) = 0

f(1) = 1

f(n) = f(n-1) + n when n > 1

so f(5) = 5 + f(4) = 5 + 4 + f(3) = 5 + 4 + 3 + 2 + 1 + 0

Now it's obvious.

• In the case of this function, though, f(0) is never called.
– user2005
Nov 8, 2014 at 11:12