Recursion

Recursion is one of the most widely used tools in the field of computer science. Recursion literally stands for repetition of an application. Sometimes it is much easier to define a function recursively instead of a closed-form, even though it may take a little bit of practice to get the recursion.

Recursive functions are defined by base cases and recursive cases. Base cases simply tell the function when to stop and recursive cases indicate how to do the repetition. One of the recursive functions that we are all used to is the factorial. I will define the factorial function below:

Factorial(x):
    if x = 0:
        then 1
    if x = 1:
        then 1
    else:
        then factorial(x-1) * x

Another use of recursion can be seen in fibonacci numbers. The definition of fibonacci numbers includes two base cases and one recursive step just like the factorial. Fibonacci numbers are defined as the following: the first fibonacci number is equal to 1, the second fibonacci number is also equal to 1 and any other fibonacci number is equal to the sum of the two previous fibonacci numbers.

In the following blogs I will be talking about different strategies/paradigms in which the recursion is the main agent. I will start with the algorithmic paradigm called divide and conquer method.