CODEWITHSUNDEEP
common-lisp
Xavier Maldonado
Xavier Maldonado

Reputation: 310

lisp Elementary recursion function. Help me trace it

Lisp sigma function recursion - help me trace it. I get it logically, I just need to understand this example so I can do my assignments. I'm not sure what is happening on the 4th and 5th line, what is x being set to. If my inputs are (sigma f 1 2) my output is 20, another example would be (sigma f 1 5). If you can help me trace it. I would post the sigma definition below. Thank you for your help.

(defun sigma (f m n)
  (if (> m n)
      0
      (let ((x (sigma f (+ m 1) n)))
        (+ (funcall f m)
           x))))

Upvotes: 2

Views: 134

Answers (2)

coredump
coredump

Reputation: 38967

You could also trace your function. Since you need an auxiliary function, let's define myfun, which multiplies its argument by 2.

CL-USER> (defun myfun (x) (* x 2))
MYFUN

TRACE both functions:

CL-USER> (trace sigma myfun)

And then, you should have something like this:

CL-USER> (sigma 'myfun 0 5)
  0: (SIGMA MYFUN 0 5)
    1: (SIGMA MYFUN 1 5)
      2: (SIGMA MYFUN 2 5)
        3: (SIGMA MYFUN 3 5)
          4: (SIGMA MYFUN 4 5)
            5: (SIGMA MYFUN 5 5)
              6: (SIGMA MYFUN 6 5)
              6: SIGMA returned 0
              6: (MYFUN 5)
              6: MYFUN returned 10
            5: SIGMA returned 10
            5: (MYFUN 4)
            5: MYFUN returned 8
          4: SIGMA returned 18
          4: (MYFUN 3)
          4: MYFUN returned 6
        3: SIGMA returned 24
        3: (MYFUN 2)
        3: MYFUN returned 4
      2: SIGMA returned 28
      2: (MYFUN 1)
      2: MYFUN returned 2
    1: SIGMA returned 30
    1: (MYFUN 0)
    1: MYFUN returned 0
  0: SIGMA returned 30
30

Upvotes: 5

David Maze
David Maze

Reputation: 160073

A first thing that might help in understanding this is using more descriptive names:

(defun sigma (some-function current-index end-index) ...)

This function is a pretty typical recursion pattern. First, there is a base case:

(if (> m n) 0 ...)

Once we've reached the end of the loop, we're done. For any f, (sigma f 2 1) is "past the end of the loop" and will always produce 0.

Otherwise, we're not past the end of the loop, so there's a fragment of "call this function again, with the next index":

(sigma f (+ m 1) n)

a fragment of "produce some result for this index":

(funcall f m)

and then a combination of the two:

(let ((x (recursive-sigma-call)))
 (+ (value-at-this-index) x))

You might try walking through

(sigma (lambda (x) (* x 2)) 1 2)

expanding each of the forms by hand to see how this works.

Upvotes: 3

Related Questions