## Some of this, sum of that

| categories: miscellaneous | View Comments

recursive_sum

## Some of this, sum of that

John Kitchin 5/29/2012

Matlab provides a sum function to compute the sum of a vector. However, the sum function does not work on a cell array of numbers, and it certainly does not work on nested cell arrays. We will solve this problem with recursion.

```function main
```

## Basic sum of a vector

```v = [1 2 3 4 5 6 7 8 9]
sum(v)
```
```v =

1     2     3     4     5     6     7     8     9

ans =

45

```

## sum does not work for a cell

```v = {1 2 3 4 5 6 7 8 9}  % note {} is a cell array
try
sum(v)
catch
'An error was caught!'
end
```
```v =

[1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]

ans =

An error was caught!

```

## Compute sum of a cell array with a loop

In this case, it is not hard to write a loop that computes the sum. Note how the indexing is done. v{i} is the contents of the ith element in the cell array. v(i) is a new cell array containing the contents of the ith element.

```s = 0;
for i=1:length(v)
s = s + v{i};
end
sprintf('The sum of the cell array v = %d', s)
```
```ans =

The sum of the cell array v = 45

```

## Nested cell arrays

Suppose now we have nested cell arrays. This kind of structured data might come up if you had grouped several things together. For example, suppose we have 5 departments, with 1, 5, 15, 7 and 17 people in them, and in each department they are divided into groups.

```Department 1: 1 person
Department 2: group of 2 and group of 3
Department 3: group of 4 and 11, with a subgroups of 5 and 6 making
up the group of 11.
Department 4: 7 people
Department 5: one group of 8 and one group of 9.```

We can represent that data as nested cell arrays like this.

```v = {1,
{2,3}
{4,{5,6}},
7,
{8,9}}
```
```v =

[       1]
{1x2 cell}
{1x2 cell}
[       7]
{1x2 cell}

```

## Sum of nested cell arrays

Now, say we want to know the sum of the people in all departments. We can not write a loop to do this because of the nesting. Lets see what a loop would do.

```for i=1:length(v)
v{i}, class(v{i})
end
```
```ans =

1

ans =

double

ans =

[2]    [3]

ans =

cell

ans =

[4]    {1x2 cell}

ans =

cell

ans =

7

ans =

double

ans =

[8]    [9]

ans =

cell

```

You can see the output of v{i} is variable. Sometimes it is a number, sometimes it is a new cell array, and sometimes a new nested cell array. There is no set of loops we can construct to add all the numbers. Instead, we have to construct a recursive function that goes into each nested cell array to the end, gets the numbers and adds them up.

## a recursive sum function

For a recursive function we need to identify the situation that is terminal, work towards the terminal condition, and then call the function again. Here, as we traverse the cell array, when we get a number we end the recursive call, and when we get another cell array we recurse. So, we will iterate over the cell array, and everytime we find a number we add it to the sum, and otherwise call the function again

```    function s = recursive_sum(v)
% v is a (possibly nested) cell array
s=0; % initial value of sum
for i=1:length(v)
if isnumeric(v{i})
% this is the terminal step
v{i}  % show the order of traversal
s = s + v{i};
else
% we got another cell, so we recurse
s = s + recursive_sum(v{i});
end
end
end
```

## Test the recursive function

We should get the same answer as before. and we do. You can also see that the numbers are added up in the order you go through the cell array.

```recursive_sum(v)
```
```ans =

1

ans =

2

ans =

3

ans =

4

ans =

5

ans =

6

ans =

7

ans =

8

ans =

9

ans =

45

```

## check on a non-nested cell array

```recursive_sum({1,2,3,4,5,6,7,8,9})
```
```ans =

1

ans =

2

ans =

3

ans =

4

ans =

5

ans =

6

ans =

7

ans =

8

ans =

9

ans =

45

```

## check on a non-cell array argument

```try
recursive_sum([1,2,3,4,5,6,7,8,9])
catch
disp('our function does not work if the argument is not a cell array!')
end
```
```our function does not work if the argument is not a cell array!
```

## Conclusions

In Post 1970 we examined recursive functions that could be replaced by loops. Here we examine a function that can only work with recursion because the nature of the nested data structure is arbitrary. There are arbitary branches and depth in the data structure. Recursion is nice because you don't have to define that structure in advance.

```end

% categories: Miscellaneous
% tags: recursive
```

## Lather, rinse and repeat

| categories: math | View Comments

recursive_functions

## Lather, rinse and repeat

John Kitchin 5/28/2012

Recursive functions are functions that call themselves repeatedly until some exit condition is met. Today we look at a classic example of recursive function for computing a factorial. The factorial of a non-negative integer n is denoted n!, and is defined as the product of all positive integers less than or equal to n.

```function main
```

## recursive function definition

The key ideas in defining a recursive function is that there needs to be some logic to identify when to terminate the function. Then, you need logic that calls the function again, but with a smaller part of the problem. Here we recursively call the function with n-1 until it gets called with n=0. 0! is defined to be 1.

```    function f = recursive_factorial(n)
% compute the factorial recursively. Note if you put a negative
% number in, this function will never end. We also do not check if
% n is an integer.
if n == 0
% this is the terminating case
f = 1
else
% otherwise we call the function again, this time with n-1
f = n * recursive_factorial(n-1)
end
end
```
```f =

1

f =

1

f =

2

f =

6

f =

24

f =

120

ans =

120

```

## Matlab factorial function

```factorial(5)
```
```ans =

120

```

## Now our function

```recursive_factorial(5)
```

## Compare to a loop solution

This example can also be solved by a loop. This loop is easier to read and understand than the recursive function. Note the recursive nature of defining the variable as itself times a number.

```n = 5;
factorial_loop = 1;
for i=1:n
factorial_loop = factorial_loop*i
end
```
```factorial_loop =

1

factorial_loop =

2

factorial_loop =

6

factorial_loop =

24

factorial_loop =

120

```

## Conclusions

Recursive functions have a special niche in mathematical programming. There is often another way to accomplish the same goal. That isn't always true though, and in a future post we will examine cases where recursion is the only way to solve a problem.

```end

% categories: math
% tags: recursive
```