Recursion

What is Recursion?

The Process of Defining a function or calculating a number by the repeated application of an algorithm.

Recursion Consist of:

  1. Base Case : When we stop repeating our algorithm
  2. Recursion Case: Repeating the algorithm

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

“The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.” – Wirth, Niklaus

Code Example

        public static int Summation(int n)
        {
            //Base Case : we are at the end
            if (n<= 0)
            {
                return 0;
            } else

            //Recursion Case : keep going 
            {
                return n + Summation(n-1);
            }
        }

        public static int Factorial(int n)
        {
            //Base Case : we are at the end
            if (n <= 0)
            {
                return 0;
            }
            else
            //Recursion Case : keep going 
            {
                return n * Factorial(n-1);
            }
        }

        public static int Exponentiation(int n, int p)
        {
            //Base Case : we are at the end
            if (p <= 0)
            {
                return 1;
            }
            else
            //Recursion Case : keep going 
            {
                return n * Exponentiation(n, p-1);
            }
        }

        public static void RecursionExample()
        {
            Summation(3);
            Factorial(5);
            Exponentiation(5,3);
        }
Advertisements

Leave a Reply