# Recursive functions

Original blog illustration by Benedicte 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?

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

### 7 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

• Jerome says:

Oups, Typo. Thanks.
Outputting x is useful to use in place computation which can be useful with recursive function but I edited.

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)

• Jerome says:

Hi,
Your request was very pertinent so I added it to the post.

4. Angel says:

Nice post, i will try to use recursion more times in my programs.

Just one comment, i think that the if condition of the code is with && not with ||. You need that it is not ‘.’ AND it is not ‘..’

• zgavin says:

Very true – otherwise, the user will get the exact recursion error that was referenced in the article.

The shortcut ‘OR’ operator, ‘||’, will be tripped every time – because there is a ‘.’ and ‘..’ (contents and back shortcut respectively) in every folder.

Great article though! It is very hard for me to conceptualize and create these functions so this helped a bunch.

Just in case anyone wants to use this function the correct condition nested ‘if’ statement is:

`~strcmp(ListSubFold(i).name,'.') && ~strcmp(ListSubFold(i).name,'..')`