## Using recursion in MATLAB

This week I wind up with coding sum-product algorithm in MATLAB. All went well, and there were some interestingly simple but powerful techniques I would like to share. We all know that programming function with recursion can save a lot of time, and is a classic technique in C++. I just realized that we can do so in MATLAB too, and the way to do it is very similar to that in C++.

### Example1: “Calculate the summation at each node in a binary tree”

I have a 3-level binary tree whose nodes are connected as follows: node1 is the parent of node 2 and 3, node 2 is the parent of node 4 and 5, node 3 is the parent of node 6 and 7. Let’s assume that nodes 4 – 7 are instantiated with number 4, 5, 6 and 7 respectively. We want to calculate for a node n the summation of its corresponding children in the leaf level. Let’s name the function fn_recurs_sum_tree(tree, n) where the variable “tree” is the binary tree structure with node 4-7 instantiated as above, and n denotes the node of interest. More specifically, tree is a cell array of the size 7 x 1, where tree{n} returns the value stored in the node n of the tree. Here is the example of the code

```
````function sum = fn_recurs_sum_tree(tree,n) if ~isempty(tree{n,1}) sum = tree{n,1}; else sum = fn_recurs_sum_tree(tree,2*n) + fn_recurs_sum_tree(tree,2*n+1); end `

### Example2: “Calculate the summation at every node in a binary tree”

What if we want to find the summation at every node in the network? Of course, we would not call the function fn_sum_bin_tree(tree, n) for n=1, 2 and 3 as that would not be efficient when the number of node is large. One technique is to call the function at the root node (i.e., n = 1) so that all the summation is accumulated from bottom to the top. The price to pay is to deal with how to pass the cell array tree into such a function. Here is the example.

```
````function [sum, tree] = fn_recurs_sum_tree2(tree,n) if ~isempty(tree{n,1}) sum = tree{n,1}; else [sum1, tree] = fn_recurs_sum_tree2(tree,2*n); [sum2, tree] = fn_recurs_sum_tree2(tree,2*n+1); sum = sum1 + sum2; tree{n,1} = sum; end `

Here are some test codes:

% #### example code ###### % initial the tree tree = cell(7,1); for n = 4:7 tree{n,1} = n; end % Calculate the sum for a single node 2 sum = fn_recurs_sum_tree(tree,2) % Calculate the sum for the whole network [sum, tree] = fn_recurs_sum_tree2(tree,1)

This technique is very useful when you have to deal with tree. So, hope this helps! Sample codes are made available here:

fn_recurs_sum_tree.m

fn_recurs_sum_tree2.m

example1.m

Just copy all the codes, put them in the same folder, then run example1.