Recursion
or selfcalling routine
1. Basics
2.
Example with Factorials
3.
Video: Solve a Puzzle with Recursivity
1. Basics
Recursion
is a kind
of tricky and smart construction which
allows a function to call itself. The Matlab programming language
supports it,
so a function can call
itself during its own execution. Recursive
algorithms can be directly implemented in Matlab.
Here is a simple
example of
recursion, let's elaborate...
Example of recursive code:
function y =
ten_exp(n)
%
This is a recursive program for computing y = 10^n.
%
The program works only if n is a nonnegative integer.
%
If n is negative, the algorithm won't stop.
if n == 0
y
= 1
else
n
%<< this line is not
needed but for inspection
y = 10
* ten_exp(n1)
end
Semicolons were avoided
in those statements (on purpose) to see
the value updates in different levels of the recursion. You can explore
the
code by running the
stepbystep feature while at the editor.
This
code has a construction using a branch. The comparison
n == 0 is the base of the recursion, because it defines the final step
or
lowest level. This is the only way to get the program to stop calling
itself.
The
‘else’ part
in the branch is the key to recursivity. The trick is
that it is calling a lower value (n  1), and it will continue to do so
until
it gets down to n = 0.
There are several considerations while using this selfcalling
technique:
 The
first is that it is possible for the function
to call itself forever and never return an answer. That happens in the
code
above if we enter a negative argument.
 The
second is that recursion can lead to
redundant calculations which can be time consuming. The code above uses
instructions again and again that could be performed using a single
line of
code (10^n).
 The
third consideration is that it needs more memory
allocation. In calculations on large systems, memory space should not
be wasted
on program overhead.
On the other hand, recursive
programs can be easier to write
and read than nonrecursive programs.
2.
Recursivity to solve Factorials
Now, we’re going to write
a function to compute a factorial
(n!) using this technique, again. We know that it’s not the most
efficient way to
compute a
factorial number, but it is conceptually a recursive calculation easy
to test
and implement...
function y =
fact(n)
%
We have the highest number
y = n
%
We go down to 0
if n == 0
y
= 1
else
% We multiply by all the
integers before ours,
% one at a time...
y = y * fact(n1)
end
Again, these
are the considerations for this example:
 It
is possible for the function to call itself
forever and never return an answer. That happens in the code above if
we enter
a negative argument.
 There
are redundant calculations which can be
time consuming. The code above uses instructions again and again that
could be
performed using a single builtin function (factorial(n)).
3.
Video: Puzzle solved with Recursivity
From
'Recursion' to home
From 'Recursion' to Matlab
Examples
