Recursion
Recursion
‣ method of defining functions in which the function being
defined is applied within its own definition
‣ an important and powerful tool in problem solving and
programming
‣ can be used as an alternative to iteration / looping to
provide an elegant solution to a problem
2
Recursive Thinking
Recursive Definition
‣ when one uses the word or concept being defined in
the definition itself
‣ when defining an English word, a recursive definition is
not often helpful but it can be an appropriate way to
express a concept in other situations
‣ before applying recursion to programming it is best to
practice thinking recursively
3
Recursive Thinking
Consider the following list of numbers:
24, 88, 40, 37
Such a list can be defined as follows:
a LIST is a: number
or a: number comma LIST
That is, a LIST is defined to be a single number, or a number
followed by a comma followed by a LIST
In the definition above, the concept of a LIST is used to define
itself
4
Recursive Thinking
The recursive part of the definition of LIST is used several times,
terminating with the non-recursive part:
number comma LIST
24 , 88, 40, 37
number comma LIST
88 , 40, 37
number comma LIST
40 , 37
number
37
5
Recursive Thinking
Infinite Recursion
‣ all recursive definitions must have a non-recursive part
otherwise there would be no way to terminate the
recursive path
‣ similar to an infinite loop but the non-terminating “loop”
is part of the definition itself
6
Recursive Function
‣ a function is called “recursive” if a statement within its definition is a call to
itself
‣ a function that invokes / calls itself
Problems that lend themselves to a recursive solution have the following
characteristics:
‣ One or more simple cases of the problem have a straightforward solution,
non-recursive solution
‣ The other cases can be redefined in terms of problems that are closer to
the simple cases
‣ By applying the redefinition process every time the recursive function is
called, eventually the problem is reduced entirely to simple cases which
are easy to solve
7
Recursive Function
General form
returnType FunctionName( Parameters) {
if simple case //base case or terminating condition
solve it
else
call function with simpler version of problem
8
Recursive Function
Example 1 - Recursive Factorial
Given the mathematical function for computing the factorial:
0! = 1
n! = n * (n-1)!, for n > 0
Why is this a recursive function?
‣ to compute for n! we are required to compute for (n-1)!
‣ a factorial is defined in terms of another factorial
9
Recursive Function
Example 1 - Recursive Factorial
10
Recursive Function
Example 1 - Recursive Factorial
int factorial(int n) {
int ans;
if (n == 0) //base case or terminating condition
ans = 1;
else
ans = n * factorial(n - 1);
return ans;
}
11
Recursive Function
Example 1 - Recursive Factorial
12
Recursive Function
Iterative Factorial
int factorial(int n) {
int i, product = 1;
for (i = n; i > 1; i--) {
product = product * i;
return product;
Note that the iterative version contains a loop as its major control structure while the
recursive version contains an if statement. In the iterative version, the variable
product is the target of the repeated assignments, each of which brings its closer
value to the result value.
13
Recursive Function
Example 2 - Recursive Multiplication
int multiply(int x, int y) {
int ans;
if(y == 1) //base case or terminating condition
ans = x;
else
ans = x + multiply(x, y-1);
return ans;
}
14
Recursive Function
Example 2 - Recursive Multiplication
15
Questions?
16
Activity
Define a recursive function for
1. Addition
2. Division
17