Transcript Recursion

Recursion
Chapter 11
Chapter Contents





Recursive Definitions
Base and General Cases of Recursion
What is a Recursive Algorithm
Recursive Functions
Using Recursive Functions
Recursive Definitions


Definition:
The process of solving a problem by reducing it
to smaller versions of itself is called recursion.
Example:
Consider the concept of factorials
0! = 1
1! = 1
2! = 1 * 2
3! = 1 * 2 * 3
...
n! = 1 * 2 * 3 * 4 * … * (n – 1) * n
Recursive Algorithm

The factorial of a number could be defined
recursively
 1 if n  1
n!  
n *(n  1)! if n > 1
Base Case
General Case
Base and General Cases of Recursion
1. Every recursive definition must have one
(or more) base cases.
2. The general case must eventually reduce
to a base case.
3. The base case stops the recursion
Base Case
 1 if n  1
n!  
n *(n  1)! if n > 1
General Case
Recursive Functions

This would be the recursive function for the
recursive factorial algorithm
int fact (int num)
{
}
if (num == 0)
return 1;
else
return num * fact (num – 1);
Recursive Functions

Execution of
a call to the
recursive
factorial function
cout << fact(4);
Recursive Functions


Think of a recursive function as having infinitely
many copies of itself.
Every call to a recursive function has




its own code and
its own set of parameters and
its own local variables.
After completing a particular recursive call,


Control goes back to the calling environment
That is, the previous call.
Recursive Functions



The current (recursive) call must execute
completely before the control goes back to the
previous call.
The execution in the previous call begins from
the point immediately following the recursive
call.
A recursive function in which the last statement
executed is the recursive call is called a tail
recursive function.

The function fact is an example of a tail recursive
function.
Using Recursive Functions

Consider the task of finding the largest element
of an array

To find the largest element in
list[a]...list[b]


First find the largest element in
list[a+1]...list[b]

Then compare this largest element with list[a].
Note the source code
Using Recursive Functions

Execution of
the recursive
function
largest()
Using Recursive Functions

Example of Fibonacci number
•
•
•
a denotes the first Fibonacci number
b is the second Fibonacci number
n is the nth Fibonacci number:
if n = 1
a

fib(a, b, n)  b
if n = 2
 fib(a, b, n  1)  fib(a, b, n  2) if n > 2

Using Recursive Functions


Note
Fibonacci
source
code
Note diagram of
recursive
Fibonacci
function call
•
Very inefficient
Recursion or Iteration?

Iterative control structures use a looping
structure to repeat a set of statements.




There are usually two ways to solve a
particular problem

iteration and
recursion.
Which method
is better?
The obvious question …


while,
for,
or do...while,
Recursion or Iteration?


Another key factor in determining the best
solution method is efficiency.
Recall that whenever a function is called,



Memory space for its formal parameters and local
variables is allocated.
When the function terminates, that memory space is
then deallocated.
We also know that every (recursive) call has its
own set of parameters and (automatic) local
variables.
Recursion or Iteration?

Overhead involved with recursion
•
•

Today’s computers
•
•

Memory space
Time of execution
fast
inexpensive memory
Therefore, the execution of a recursion function
is not noticeable.
Recursion or Iteration?

Rule of thumb:
If an iterative solution is
•
•

Fibonacci numbers
more obvious
easier to understand than a recursive solution
Use the iterative solution, which would be more
efficient.
When the recursive solution is more obvious or
easier to construct … use recursion
Tower of Hanoi