Recursion, a quick example


Most people look at Recursion as something scary and unknown. Recursion is simply when a function calls itself again and again until the problem gets smaller and smaller to solve until its done, or when a problem meets a given condition. In every recursive function, there always exists a base case where the function will stop calling itself and return something. Visually, recursion is a stack of calls where a method will call itself and push that call onto a stack, then pops when it meets a base case or there’s nothing else to push. See illustration and animation…

stack2

To explain a bit more, a clear example of recursion is finding a factorial of a number.

b_n = nb_{n-1}
b_0 = 1

Remember that a factorial is a number multiplied by its previous number like so: n(n-1)(n-2)…*1
[or in plain terms: 5! is 5*4*3*2*1]

Recursive factorial animation

We can use recursion to create a factorial program that computes the factorial of an integer entered.
And as always, you can use this code in Java since syntax is similar.

class factorial//we have an object called factorial that will contain all the functions/properties
    {
        public int result(int val)//our primary function
        {
            int answer;

            if (val == 1)//if the value is just 1, 1!=1 so return 1
            {
                return 1;
            }
            else
            {
                answer = result(val - 1) * val;   /* method result is call to it self*/

                /*here is how answer works: factorial is basically n*(n-1)*(n-2)...*1, so each time its 

               called the value decreases by 1 as its multiplied by the previous value */

                return answer; //we return answer
            }
        }
    }
    class Program
    {
        static void Main()
        {
            Console.WriteLine("Factorial with Recursion");
            factorial factorial = new factorial();
            Console.Write("Enter a value to find its factorial: ");
            int f = int.Parse(Console.ReadLine());
            Console.WriteLine("Result: {0}",factorial.result(f));
            Console.ReadLine();

        }
    }

In C++

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>

using namespace std;

int factorial(int n)
{
    int answer;
    if(n == 1)
    {
        return 1;
    }
    else
    {
        answer = factorial(n-1) * n;
        return answer;
    }
}

int main()
{
    cout<<"5! factorial is: "<<factorial(5);
    cin.get();
    return 0;
}

To get a closer look into whats happening when we call the function, here is an illustration:
Example: int val = 4; So we want to find 4!

1st call: answer = result(4-1)*4 so we have 4*(3)<– (3) is the result we get from the function’
2nd call:answer = result(3-1)*(4-1)*4 so we have 4*(3(2))
3rd call: answer = result(2-1)*(3-1)*(4-1)*4 so we have 4*(3(2(1)))
and we would get an answer of 24.

So to conclude, Recursion helps us solve problems where its better to use it. In data structures such as Trees, its used a lot to print out a tree or sort or find something within the Tree structure. In the grand scheme of things, nobody really has to fully understand Recursion but really just playing around with it helps a lot, its a complex concept.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s