Reputation: 310
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
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
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