Transcript Topic7

Topic 7 – Recursion
(A Very Quick Look)
What is Recursion?


A recursive function is a function that
calls itself.
Recursive functions can be used to
replace loops, under certain
circumstances.
CISC 105 – Topic 7
Recursive Problems

Problems that can be solved using recursion
typically:



Have one or more simple cases (or base case)
that have simple, non-recursive solutions
The other cases can be redefined in terms of
problems that are closer to the base cases.
By applying this redefinition, the entire problem
can be reduced entirely to simple cases, which are
relatively easy to solve. This relationship between
cases is known as the recurrence relation.
CISC 105 – Topic 7
THE Classic Recursive Problem



The most-common recursive problem is
that of the Fibonacci numbers.
Each Fibonacci number can be defined
as the sum of the two previous
Fibonacci numbers.
The first two Fibonacci numbers are
exempt from this definition, as they are
both equal to one (1).
CISC 105 – Topic 7
Fibonacci Numbers




Therefore, the first two Fibonacci numbers
(the ones) are the base cases.
All other Fibonacci numbers are the sum of
the previous two Fibonacci numbers. This is
the recurrence relation of the Fibonacci
numbers.
Therefore, Fib(3) = Fib(2) + Fib(1).
As Fib(1) = 1 and Fib(2) = 1,
Fib(3) = 1 + 1 = 2
CISC 105 – Topic 7
Fibonacci Numbers





Similarily, Fib(4) = Fib(3) + Fib(2).
Fib(3) = Fib(2) + Fib(1)
Fib(2) = 1
Fib(1) = 1
Therefore, Fib(4) = 1 + 1 + 1 = 3
CISC 105 – Topic 7
Fibonacci Numbers







Similarily, Fib(5) = Fib(4) + Fib(3).
Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(4) = Fib(2) + Fib(1) + Fib(2)
Fib(2) = 1
Fib(1) = 1
Therefore, Fib(5) = 1 + 1 + 1 + 1 + 1 = 5
CISC 105 – Topic 7
Fibonacci Numbers Function
Recurrence Relation
Base Cases
The
program redefined all cases
Here, fib(1)function
and fib(2) are the
 So…a recursive Fibonacci
other than the base case as
base cases. They both have
would
look
like:
a problem closer to the base case(s).
simple, non-recursive solution;
This will continue to occur until
they are both equal to one.
int
fib(int
n)
all problems are simply a function
{
of theint
base
case(s).
ans;
if (n == 1 || n == 2)
ans = 1;
else
ans = fib(n - 2) + fib(n - 1);
return ans;
}
CISC 105 – Topic 7
A Common Error in
Recursive Function Design



A common error in the writing of recursive
function is to not have a problem which
breaks down (using the recurrence relation)
into base cases.
If a function does not break down to base
cases, the function may continue forever.
For example, if the Fibonacci function did not
include the Fib(1) and Fib(2) base cases, it
would continue forever and never return an
answer.
CISC 105 – Topic 7
A Common Error in
Recursive Function Design

For example, this Fibonacci function
would never return a correct answer:
int fib(int n)
{
int ans;
ans = fib(n - 2) + fib(n - 1);
return ans;
}
CISC 105 – Topic 7
A Common Error in
Recursive Function Design

Likewise, this function will also never
return an answer:
int fib(int n)
{
int ans;
if (n == 1 || n == 2)
ans = 1;
else
ans = fib(n) + fib(n - 1);
return ans;
}
CISC 105 – Topic 7
A Test of Recursion

Write a recursive function which can be
used to compute the factorial of a
certain number.
CISC 105 – Topic 7