What is Recursion ? and with example of Recursive Functions..

+IT Programming World

What is Recursion ? and with example of Recursive Functions..

1. 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 recursion immediate recursion.

2. 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 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 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
   }

   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: n!

   Compute n! Recursively.

   We are given the mathematical function for computing the factorial:

   n! = n * (n - 1)!

   Why this is a recursive function?  To compute n! we are required to compute (n - 1)!.

   We are also given the simple case.  We define mathematically 0!

   0! = 1

   To undersatnd factorial in a recursive sense, consider a few simple cases:
    

   1! = 1 * 0! = 1 * 1 = 1

   2! = 2 * 1! = 2 * 1 = 2

   3! = 3 * 2! = 3 * 2 = 6

   4! = 4 * (3 * 2 * 1) = 4 * 3! = 24

   Consider a more complicated instance:

   12! = 12 * 11! = 12 * (11 * 10 * ... * 1) = = ?

   Now let us write the C++ function which will calculate the factorial of a given integer. Apply the simple case and the general factorial function to the general recursive function established previously.

   int Factorial(int n) {
     if (n == 0) return 1;           // Simple case: 0! = 1
     return (n * Factorial(n - 1));  // General function: n! = n * (n - 1)!
   }

   Here, 0! = 1 is the base case and our general recursive function forms the simplification of the original problem.
    

   Stepping Through Recursive Functions (Be stupid like a computer)

   Example 1: Fibonacci Sequence

   Consider the following program which contains a recursive function.  What is the complete output?

   #include <iostream.h>

   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;

     cin >> num;
     cout << Fibonacci(num) << endl;

     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.

                                 Fibonacci(5)
                                 /         \
                                /           \
                               /             \
                              /               \
                             /                 \
                          F(4)        +        F(3)
                          /  \                 /  \
                         /    \               /    \
                        /      \             /      \
                       /        \           /        \
                      /          \         /          \
                    F(3)   +    F(2)    F(2)   +     F(1)
                    /\           /\       |  \         \
                   /  \         /  \      |   \         \
                  /    \       /    \     |    \         \
                 /      \     /      \    |     \         \
                F(2) + F(1)  F(1) + F(0) F(1) + F(0)       1
                 /\      |    |      |    |      |
                /  \     |    |      |    |      |
               /    \    |    |      |    |      |
              /      \   |    |      |    |      |
             F(1) + F(0) 1    1      0    1      0
             |       |
             |       |
             |       |
             |       |
             1       0

   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
    

   Example 2: F()

   #include <iostream.h>

   //F(0) = 1; F(1) = 2
   //F(n) = F(n-1) * F(n-2)

   int Recursive(int n) {
     cout << n << endl;
     if (n == 0) return 1;
     if (n == 1) return 2;
     return (Recursive(n - 1) * Recursive(n - 2));
   }

   int main()
   {
     int Result, num;

     cin >> num;

     cout << "Result: " << Recursive(num) << endl;

     return 0;
   }

   Inputting: num = 3.

   Output:

   3
   2
   1
   0
   1
   Result: 4

   If we evaluate these recursive calls we have

   ((2 * 1) * 2) = 4

   Thus, Recursive(3) = 4.

               Recursive(3)
                  /  \
                 /    \
                /      \
               /        \
              /          \
             R(2)    *   R(1)
             /  \          \
            /    \          \
           /      \          \
          /        \          \
         R(1)  *  R(0)         2
          |        |
          |        |
          |        |
          |        |
          2        1
    
    

   Running the program with num = 5;

   5
   4
   3
   2
   1
   0
   1
   2
   1
   0
   3
   2
   1
   0
   1
   Result: 32

   We can generate the recursive calls.

                                 Recursive(5)
                                 /         \
                                /           \
                               /             \
                              /               \
                             /                 \
                          R(4)        *        R(3)
                          /  \                 /  \
                         /    \               /    \
                        /      \             /      \
                       /        \           /        \
                      /          \         /          \
                    R(3)   *    R(2)    R(2)    *    R(1)
                    /\           /\       |  \         \
                   /  \         /  \      |   \         \
                  /    \       /    \     |    \         \
                 /      \     /      \    |     \         \
                R(2) * R(1)  R(1) * R(0) R(1) * R(0)       2
                 /\      |    |      |    |      |
                /  \     |    |      |    |      |
               /    \    |    |      |    |      |
              /      \   |    |      |    |      |
             F(1) * F(0) 2    2      1    2      1
             |       |
             |       |
             |       |
             |       |
             2       1

   If we evaluate these recursive calls we have

   (((2 * 1) * 2) * (2 * 1)) * ((2 * 1) * 2) = 32

   Thus, Recursive(5) = 32.

   One thing you may have noticed from Recursive(5) is that one of the subtrees is Recursive(3).
    

   Don't be concerned if you have trouble with some of these functions, many more examples will be provided in class.