Question

Explain recursive function & what is the data structures used to perform recursion?

Answer 1

Recursive Functions

A recursive function (DEF) 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 recursionimmediate 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 graph
   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