Lecture Outline
Recursion
Base Case
Recursion and Stack
Factorial using Recursion
Fibonacci Series using Recursion
Recursion
• Recursion is a technique that leads to elegant solutions to problems
that are difficult to program using simple loops.
• To use recursion is to program using recursive functions—functions
that invoke themselves.
• Recursion is a useful programming technique. In some cases, it
enables you to develop a natural, straightforward, simple solution to
an otherwise difficult problem.
Example: Factorials
• A recursive function is one that invokes itself.
• Base Case
• The recursive algorithm for computing factorial(n) can be simply
described as follows:
Recursive Call
• A recursive call can result in many more recursive calls, because the
function is dividing a subproblem into new subproblems.
• For a recursive function to terminate, the problem must eventually
be reduced to a stopping case.
• At this point the function returns a result to its caller.
Infinite Recursion
• Infinite recursion can occur if recursion does not reduce the problem
in a manner that allows it to eventually converge into the base case or
a base case is not specified.
• For example, suppose you mistakenly write the factorial function as
follows:
• The function runs infinitely and causes the stack overflow.
Show the output of the following programs
and identify base cases and recursive calls.
Case Study: Fibonacci Numbers
The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the
preceding two numbers in the series. The series can be defined recursively as follows:
Recursive Algorithm for Fibonacci Series
• The recursive algorithm for computing fib(index) can be simply
described as follows:
Show the output of the following two
programs:
What is wrong in the following function?
