Mumbai University > Information Technology > Sem 3 > Object Oriented Programming Methodology

Marks: 10M

Year: Dec 2015

Recursive Functions:

A recursive function is a function which either calls itself or is in a potential cycle of function calls. As the definition specifies, there are two types of recursive functions. Consider a function which calls itself: we call this type of recursion immediate recursion.

One can view this mathematically in a directed call graph

 A ---| 
   ^    | 
   |    | 
   |----|

void A() { 
  A(); 
  return; 
}

A() is a recursive function since it directly calls itself.

The second part of the defintion refers to a cycle (or potential cycle if we use conditional statements) which involves other functions.

Consider the following directed call

 A ---------> B 
   ^            | 
   |            | 
   |            | 
   |---- C <----|

This can be viewed in the following three functions:

void C() { 
  A(); 
  return; 
}
void B() { 
  C(); 
  return; 
}

void A() { 
  B(); 
  return; 
}

Recursive functions are an inefficient means of solving problems in terms of run times but are interesting to study nonetheless. For our purposes we will only consider immediate recursion since this will cause enough difficulty.

Writing Recursive Functions:

A recursive function has the following general form (it is simply a specification of the general function we have seen many times):

ReturnType Function( Pass appropriate arguments ) { if a simple case, return the simple value // base case / stopping condition else call function with simpler version of problem }

For a recursive function to stop calling itself we require some type of stopping condition. If it is not the base case, then we simplify our computation using the general formula.

Example : Fibonacci Sequence:

Consider the following program which contains a recursive function.

import java.io.*;
int Fibonacci(int x) { 
  if (x == 0) return 0;  // Stopping conditions 
  if (x == 1) return 1; 
  return Fibonacci(x - 1) + Fibonacci(x - 2); 
}
int main() { 
  int num;
System.out.println("Enter the Number:");
  int number =sc.nextInt();
  System.ut.println(Fibonacci(num));
  return 0; 
}

Let's input the value 5 for this program.

The following recursive calls are made. Notice the (upside-down) tree structure created by the recursive calls.

If we evaluate these recursive calls we have

(((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1) = 5

Thus, Fibonacci(5) = 5.

Input: 5

Output: 5

You may have noticed the name of the function and recognized it as a well-known mathematical function: the fibonacci sequance.

Working backward, we could have formulated the function given the mathematical equations:

General form:

Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)

Stopping conditions:

Fibonacci(0) = 1

Fibonacci(1) = 1