Page 46 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 3: Recursion

For recursion to be successful, the problem needs to have a recursive substructure. This is Notes
a fancy term that says that to solve a big problem (say of size N), you should be able to
solve a smaller problem (of smaller size) in exactly the same way, except the problem size
is smaller.

As an analogy, you might have to, say, sweep the floor. Sweeping half the floor is the same
as sweeping the entire floor, except you do it on a smaller area. A problem that is solved
recursively generally needs to have this property.
Many folks think recursive functions are implemented in some weird and unusual way in
assembly language. They can’t believe it’s implemented just like any other function.

The biggest misconception is that a function calls a smaller and smaller version, reaches
the base case, then quits. For example, you might call fact(3), which calls fact(2), which
calls fact(1), which finally calls fact(0), the base case.
Some programmers think the function stops there, right at the base case, and then jumps
back to the initial recursive call. But you know that’s not true.

Or do you? Suppose we have function f(), which calls function g(), and g() calls h().
What happens when we’re done with h()? We return back to g(). And what happens when
we’re done with g()? We return back to f().

Recursive functions behave that way too! Thus, fact(3) calls fact(2) which calls fact(1)
which calls fact(0), the base case. We call this phase the winding of the stack.
Once fact(0) is done, it goes back to fact(1), just like it would for non-recursive functions.
When fact(1) is done, it goes back to fact(2). When fact(2) is done, it goes back to fact(3).
When fact(3) is done, it goes back to whoever called fact(3). We call this the “unwinding”
of the stack.
During the winding of the stack, you are making progress towards the base case. Basically,
you’re trying to get to the base case, solve the base case, and slowly grow your solution
back as you go though the unwinding part of the recursion. Thus, winding heads to the
solution of the base case, while unwinding typically grows the solution from base case
back to the original call.
An Example

Let’s solve the following recursive function, written in C. This sums all elements of an
array.
int sum( int arr[], int size ) {
if ( size == 0 )
return 0 ;
else
return sum( arr, size - 1 ) + arr[ size - 1 ] ;
}

A MIPS Translation
We assume arr is in $a0 and size is in $a1.
We have to decide what to save to the stack. We have two choices. Either save size – 1, from
which we can compute arr[ size – 1 ], or save arr[ size – 1 ]. Let’s opt to save size – 1 on the
stack.

Contd...

LOVELY PROFESSIONAL UNIVERSITY 39