A Gentle
Introduction to Functions and Recursions
for MATLAB®
Programmers
Part 2: Recursions
So, after the function tutorial we understand the difference between local and global variables. That is an important building block to understanding recursion, because without local variables recursion would not be possible.
The other building block to understanding recursion is to be really clear about what a function does after it called another function.
Consider these three nested functions and their output and try to answer that question.
function
outerLevel
disp('Hi, I am Toni the Electron.')
disp('I will keep you advised on what''s going on while we run
these nested functions.')
innerLevel
disp('Hugh, back finally, this trip was exhausting.')
function
innerLevel
disp('Good, we''re in the inner level. Let the action
begin!!!')
MerryGoRound
disp('Hi, I''m back, ready to puke!')
function
MerryGoRound
for
k=1:100
disp('I am in the for loop. Help! I am
getting dizzy. ....zzz')
end
>> outerLevel
Hi, I am Toni the Electron.
I will keep you advised on what's going on while we
run these nested functions.
Good, we're in the inner level. Let the action
begin!!!
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
I am in the for loop. Help! I am
getting dizzy. ....zzz
Hi, I'm back, ready to puke!
Hugh, back finally, this trip was exhausting.
>>
So what does a function do after it called another function?
It first sits in a holding pattern, similar to airplanes which have to circle around until some action on the ground has been completed so that the airplane can get cleared to land. When a function sits in a holding pattern, it waits for the function it just called to complete what it’s doing and then return the control back over to the calling function. The holding pattern for functions is called the stack, basically a set of memory locations.
Once the calling function is back in control, IT CONTINUES WHERE IT LEFT OFF.
Recursion works exactly the same way, except that the function calls itself instead of some other function.
Consider a simple example of linear recursion, an implementation of the factorial function.
function
answer = factorialRecursion (n)
fprintf ('... going down ... n = %1.0f \n', n)
if n
< 0
disp('The factorial function is only defined for nonnegative
numbers.')
elseif n
== 0
disp('This is it, we''ve hit bottom! n = 0
Now we will get answers.')
answer = 1
else
disp('Sorry we don''t have an answer yet.')
answer = n *
factorialRecursion (n-1)
fprintf ('... going up, up , up ... n = %1.0f \n', n)
end
>> factorialRecursion(7)
... going down ... n = 7
Sorry we don't have an answer yet.
... going down ... n = 6
Sorry we don't have an answer yet.
... going down ... n = 5
Sorry we don't have an answer yet.
... going down ... n = 4
Sorry we don't have an answer yet.
... going down ... n = 3
Sorry we don't have an answer yet.
... going down ... n = 2
Sorry we don't have an answer yet.
... going down ... n = 1
Sorry we don't have an answer yet.
... going down ... n = 0
This is it, we've hit bottom! n = 0 Now we will get answers.
answer =
1
answer =
1
... going up, up , up ... n = 1
answer =
2
... going up, up , up ... n = 2
answer =
6
... going up, up , up ... n = 3
answer =
24
... going up, up , up ... n = 4
answer =
120
... going up, up , up ... n = 5
answer =
720
... going up, up , up ... n = 6
answer =
5040
... going up, up , up ... n = 7
ans =
5040
>>
Here is a schematic illustrating what just happened.
>>
factorialRecursion(7) ans
=
5040
|
function answer = factorialRecursion (7)
answer
uninitialized |
|
function answer = factorialRecursion (7)
answer = 5040 |
|
|
|
|
|
function answer = factorialRecursion (6)
answer uninitialized |
|
function answer = factorialRecursion (6)
answer = 720 |
|
|
|
|
|
function answer = factorialRecursion (5)
answer uninitialized |
|
function answer = factorialRecursion (5) n=5
|
|
|
|
|
|
function answer = factorialRecursion (4)
answer uninitialized |
|
function answer = factorialRecursion (4)
answer = 24 |
|
|
|
|
|
function answer = factorialRecursion (3)
answer uninitialized |
|
function answer = factorialRecursion (3)
answer = 6 |
|
|
|
|
|
function answer = factorialRecursion (2)
answer uninitialized |
|
function answer = factorialRecursion (2)
answer = 2 |
|
|
|
|
|
function answer = factorialRecursion (1)
answer uninitialized |
|
function answer = factorialRecursion (1) n=1
|
|
|
|
|
|
function answer =
factorialRecursion (0) n=0 answer = 1 |
||
Notice that at some point there are eight (8) copies of that function on the stack and each copy has its own set of local variables, from n=7 all the way down to n=0. Clearly, without local variables, recursion could not work.
Notice the following:
- On the “way down” answer= is not displayed because this variable was not initialized yet and had no value at those points.
- The fprintf statement at the beginning of the function does not execute again on the “way up”. The function is done with this section. On the second call to the stack location it goes back to the if statement, because that is where it had left off. But notice that it doesn’t execute the first statement in the else branch either on the way up. It had already done that on the way down. This statement is checked off or crossed off by the function, however you want to think of it. The function now first displays the value of answer, since this assignment statement is not followed by a semicolon. Then it continues and executes the second fprintf statement, the one which follows the answer= assignment statement.
Instead of just executing an fprintf statement when it comes back to that particular copy of itself, the function could do anything else we might want to program, including calling itself again, this time passing different variables as parameters to itself. Also, each copy of the function on the stack has a different set of values for all its local variables. So the same function call does different things depending on where we are on the stack.
This concept is the basis for traversing trees.
go back to the Part 1 of the tutorial