Recursive functions

Original blog illustration by Cali Rossi

Original blog illustration by Cali Rossi

In this post, I introduced you to the beauty of recursive functions. I believe that these are part of the “basic programming package” that anyone into coding should have been introduced to.

I quickly discuss the theory and their usage along with a few examples. 

I clearly remember that class when I was first introduced to recursive functions (Yes, I am a complete geek, I admit). At first I deemed the idea kind of messy but, very soon, I realized this was pure computational beauty. The underlying principle is very simple : a function that can call itself. In other word, something like this :

function y=fact(x)
if x>1
   y=fact(x-1)*x;
else
   y=1;
end

I am sure you noticed the call to fact(x) within the function calling itself. This particular example is the “hello world” example of recursive functions : the factorial. Indeed to calculate N! or N*(N-1)*(N-2)*…*1 you just need to realize that N!=N*(N-1)!. In other words you can break down the calculation in smaller blocks.

In more standard programming, you would use the following code :

function y=fact(x)

y=x;
while x>1
   x=x-1;
   y=y*x;
end

On this particular example, the standard way to code does look simpler so you could wonder : Why is this recursion useful?

Well, because there are actually many places where you can replace a complex computation with simpler blocks. Let’s look at another example of this : navigating trees. One very common tree problem is navigating hard drive hierarchical file system.
Let’s suppose you have a lot of data located in a folder with subfolders. In each of these folders and subfolder, you have tons of Mat files that stores, say, the time traces of individual neurons (yeah, yeah, I am a geek AND a neuroscientist). Now you want to gather ALL the neuronal traces files (names NeuronTraceXXX.mat) that you ever recorded that are stored in many folders and subfolders (organized by data of experiments and maybe experimental conditions).

Coding this can be a huge mess……. if you don’t use recursive functions.

Here is an example code :

function NeuronFileList=findAllNeuronFiles(Directory)

NeuronFileList=dir(fullfile(Directory,'NeuronTrace*.mat'));

ListSubFold=dir(Directory);
ListSubFold=ListSubFold([ListSubFold(:).isdir]);

for i=1:numel(ListSubFold)
   if ~strcmp(ListSubFold(i).name,'.') || ~strcmp(ListSubFold(i).name,'..')
      NeuronFileList=[NeuronFileList;findAllNeuronFiles(fullfile(Directory,ListSubFold(i).name))];
   end
end

end

The nice thing about this function is you can customize this code quite nicely to add some criteria on the particular content of mat file.

In the old days (before even my birth), hierarchical database models were main stream and you would used this sort of function to navigate the data. Now relational database have taken over the planets, so it doesn’t really apply here. Since hard drive file system are still hierarchical, this is incredibly useful.

Now, there are a few things you must know when using recursive functions.

First, it is important you always have a termination condition in your function : Design your algorithm so that it always find a final solution and stops calling itself or you will go infinite loop. Lucky for you, Matlab is ready for that scenario and you will get an error before your computer goes crazy, like so :

Maximum recursion limit of 500 reached. Use set(0,’RecursionLimit’,N) to
change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Second, make sure you understand how memory is used by all these recursive calls. Chance are that your variables are not going to be duplicated in memory, thanks to Matlab copy on write mechanism, but if you are not careful about this, memory usage can grow quite quickly. 

And you, how do you use recursive functions?

Related Posts

This entry was posted in Beginners, Intermediate. Bookmark the permalink.

5 Responses to Recursive functions

  1. Kevin says:

    Your simple recursion function is flawed. You need to call fact(x-1). Also I would call the output something else for clarity. I would suggest;

    function y=fact(x)
    if x>1
    y=x*fact(x-1);
    else
    y=1;
    end

  2. Greg Hale says:

    Hi again! Nice post, I hope some matlabbers can have a fun time playing with recursion. Here are two little examples of recursion as it appears in Haskell:

    — Define the factorial function by parts
    fact 0 = 1
    fact x = x * fact (x-1)

    — Self-referencing fibonacci
    fibs = [1,1] ++ zipWith (+) fibs (tail fibs)

    If you can arrange so that the recursive call is at the top level, the compiler will rewrite to a form that doesn’t grow the stack at all:

    — Slightly uglier, constant stack space version
    fact 0 accum = accum
    fact n accum = fact (n*accum) (n-1)

  3. Muheeb AbuZant says:

    How can I write a M-file function that computes n! using an iterative algorithm? (i.e. an explicit for loop or a matla vector command)

Leave a Reply