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