12

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?

Malabarba
  • 22,878
  • 6
  • 78
  • 163
doctorate
  • 1,789
  • 16
  • 39
  • 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. – lawlist Nov 06 '14 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? – doctorate Nov 06 '14 at 20:24
  • Oh, I see -- the function reuses itself at step 3 -- okay, good point. – lawlist Nov 06 '14 at 20:27
  • I wonder what would be the result of `(triangle-using-cond 3)`? – doctorate Nov 06 '14 at 20:31
  • 2
    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. – phils Nov 06 '14 at 20:34
  • @phils, is it not that `(1- number)` equal to `(- number 1)`? – doctorate Nov 06 '14 at 20:36
  • doctorate: absolutely correct. I just thought the phrasing of the earlier comment "`1-4 = 3`" had the potential to confuse someone. – phils Nov 06 '14 at 20:39
  • In order to understand recursion, you *must* understand recursion. – MDMoore313 Nov 07 '14 at 13:12

5 Answers5

15

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.

Drew
  • 75,699
  • 9
  • 109
  • 225
  • 3
    Edebug will be even better. =) – Malabarba Nov 06 '14 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? – doctorate Nov 06 '14 at 21:06
  • @Malabarba, how to put `Edebug` in action? – doctorate Nov 06 '14 at 21:08
  • 1
    @doctorate hit `C-u C-M-x` with point inside the function to edebug it. Then just run the function as normal. – Malabarba Nov 06 '14 at 21:43
  • @doctorate the `(message ...)` stuff prints to the `*Message*` buffer. –  Nov 06 '14 at 21:52
  • Edebug is indeed better. You "instrument" the function with `C-u C-M-x` as @Malabarba said and then hit space to step through the function, observing the messages at the bottom. Hit `q` to exit debugging. To remove instrumentation, simple evaluate the definition (`C-M-x` inside the function). –  Nov 06 '14 at 21:55
  • @Drew feel free to edit my answer to add this method. –  Apr 24 '15 at 08:09
  • I turned this answer into a community wiki answer. –  Apr 24 '15 at 08:09
7

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)))
abo-abo
  • 13,943
  • 1
  • 29
  • 43
3

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!)

Let's start with the definition:

(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.

ShreevatsaR
  • 880
  • 6
  • 19
2

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.

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

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.

chen bin
  • 4,781
  • 18
  • 36