Home > Tutorials > Using recursion in MATLAB

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.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: