Cadence.com will be under maintenance from Friday, Oct. 3rd at 6pm (PST) thru Sunday, Oct 5th at 11pm (PST).
Home > Community > Blogs > Custom IC Design > unfinished skill for the skilled many ways to sum a list part 3

 Login with a Cadence account. Not a member yet? Create a permanent login account to make interactions with Cadence more convenient. Register | Membership benefits
 Get email delivery of the Custom IC Design blog (individual posts).

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# SKILL for the Skilled: Part 3, Many Ways to Sum a List

Comments(0)In Part 1 and Part 2 of this series of posts, I showed a couple of ways to sum up a given list of numbers. In this post, I want to show a couple of ways to use recursive functions to do this.

Recall the sumlist_1a function

In a previous posting the function `sumlist_1a` was defined.

```(defun sumlist_1a (numbers)
(let ((sum 0))
(foreach number numbers
sum = sum + number)
sum))
```

Describing this algorithm in words, we see that it does not express the mathematical relationship very well, but it does describe how a Von Neumann machine would perform the calculation.

• Initialize an accumulator to 0
• Keep incrementing the accumulator by the successive element of the list
• When the list is exhausted, return the accumulator
Implementation with simple recursion

The following implementation of `sumlist_3a` is an example of simple recursion.

```(defun sumlist_3a (numbers)
(if numbers
(plus (car numbers)
(sumlist_3a (cdr numbers)))
0))
```

Expressing this algorithm in words, you can see that it is more elegant than `sumlist_1a` as the code actually expresses a mathematical relationship.

• The sum of the empty list is `0`
• The sum of a N element list is the first element plus the sum of the remaining elements

An advantage of recursive functions such as `sumlist_3a` is that they are elegant. They often require less code because there is no need to maintain state; e.g., there is no accumulator variable, and no variables are modified during the evaluation of the function.

Implementation with tail recursion

The `sumlist_3b` function is a tail recursive version of `sumlist_3a`.

```(defun sumlist_3b (numbers)
(labels ((sum (sum_so_far rest)
(if rest
(sum (plus (car rest) sum_so_far)
(cdr rest))
sum_so_far)))
(sum 0 numbers)))
```

An obvious drawback of this type of recursive function is that it is more difficult for the human to read than simple recursion.

Tail recursion is a technique which can be used to enable recursive function to require no more stack space than iterative functions. There is a pretty clear explanation on Wikipedia.

The main difference, computation-wise, between `sumlist_3a` and `sumlist_3b` is the following. In `sumlist_3a` the final computation the function does is to call the `plus` function. For example the top level call to sumlist_3a with `(1 2 3 4 5 6 7)` must completely finish processing `(2 3 4 5 6 7)` before it can add the `1`--the call to `(plus 1 ...)` cannot occur before the recursive call to `sumlist_3a` returns.

In `sumlist_3b`, on the other hand, the computation order is reversed. In the local function, `sum`, the `(plus 1 ...)` happens first. That partial sum is passed as the `sum_so_far` parameter. The final thing the local function does is call itself recursively. There is no pending operating waiting for the recursive call to return.

We'll talk more about why this is important in an upcoming posting of SKILL for the Skilled -- Many Ways to Sum a List.

Testing the functions

If we call `sumlist_1a`, `sumlist_3a`, and `sumlist_3b` on some examples we see that they return the same thing.

```(sumlist_1a nil)
=> 0

(sumlist_3a nil)
=> 0

(sumlist_3b nil)
=> 0

(sumlist_1a '(3.4))
=> 3.4

(sumlist_3a '(3.4))
=> 3.4

(sumlist_3b '(3.4))
=> 3.4

(sumlist_1a '(1 2 3 4 5 6 7))
=> 28

(sumlist_3a '(1 2 3 4 5 6 7))
=> 28

(sumlist_3b '(1 2 3 4 5 6 7))
=> 28
```

Computation order

That the computation order of `sumlist_3a` and `sumlist_3b` are opposite can be seen by tracing the `plus` function.

```(trace plus)
==>(plus)
(sumlist_3a '(1 2 3 4 5))
||||||(5 + 0)
||||||plus --> 5
|||||(4 + 5)
|||||plus --> 9
||||(3 + 9)
||||plus --> 12
|||(2 + 12)
|||plus --> 14
||(1 + 14)
||plus --> 15
==>15
(sumlist_3b '(1 2 3 4 5))
||||(1 + 0)
||||plus --> 1
|||||(2 + 1)
|||||plus --> 3
||||||(3 + 3)
||||||plus --> 6
|||||||(4 + 6)
|||||||plus --> 10
||||||||(5 + 10)
||||||||plus --> 15
==>15
```

Looking at the trace output, we see that `sumlist_3a` calls plus with first argument being first 5, then 4, 3, 2, and finally 1. However, `sumlist_3b`, `plus` is called first with first argument being 1, then with 2, 3, 4, and finally with 5. Since integer addition is commutative, associative, and side effect free, both algorithms give the same result.

This difference in the two computation models might be important in some situations if some function other than `plus` is used. For example, if a function with side effects is used, you might find that the side-effects happen in a different order.

For example, replacing the `0` with `nil`, replacing the `plus` function with `cons`, and renaming the local function from `sum` to `rev` we have two different and useful functions: a list-copy function and a list-reverse function.

```(defun copy_3e (numbers)
(if numbers
(cons (car numbers)
(copy_3e (cdr numbers)))
nil))

(defun reverse_3f (numbers)
(labels ((rev (list_so_far rest)
(if rest
(rev (cons (car rest) list_so_far)
(cdr rest))
list_so_far)))
(rev nil numbers)))
```

Testing these functions we see the following results:

```(copy_3e '(1 2 3 4 5))
==>(1 2 3 4 5)
(reverse_3f '(1 2 3 4 5))
==>(5 4 3 2 1)
```

Review

In the paragraphs above we looked at two different types of recursive functions. The two techniques usually give compatible results. However, depending on the application one technique may be preferable because of computation order or order of side effects.

More to come

I've alluded several times to the issue that these recursive functions fail for very long lists. In the next post we'll look at some ways of dealing with this issue.