Introduction to Recursion

Recursion

Recursion is a technique by which a function repeatedly calls itself (Or a different function) to have a effect similar to a loop.

A Recursive function in it's most basic form consists of two parts.

• Base case
• Recursive call

This flow chart shows how a basic recursive function works

Base case

The base case or the terminal case consists of the final step of the function which marks the end of the recursive function.

Recursive call

This step usually performs the calculations required and calls a smaller version of the main problem. This goes on until it reaches the base case.

Choosing base case and recursive call

The choice of the base case and recursive call for your function is really important as these decide how your function works

The recursive call of your function must be such that at each successive recursive call the function reaches closer to your base case, ie after multiple calls to your function, you should eventually reach your base case

The base case of your function decides when your function ends, so your base case should be selected such that your recursive case can never overshoot your base case.

Examples

So lets try out a couple of examples on how recursion works

Example 1 : Fibonacci series

The fibonacci series in mathamatics is represented by F(0) = 1 F(1) = 1 F(x) = F(x-1) + F(x-2) This problem gives us the perfect example of where to use recursion

This code in c++ would be

int fibonacci(int x)
{
	if(x == 0 || x == 1)
	    return 1;
        return fibonacci(x - 1) + fibonacci(x - 2);
}

The same code in Python would be

def fibonacci(x):
	if x == 0 or x == 1:
		return 1
	return fibonacci(x - 1) + fibonacci(x - 2)

Here if(x == 0 || x == 1) is the base case and it returns when x = 0 or x = 1 and return fibonacci(x - 1) + fibonacci(x - 2) is the recursive call. We can verify that the recursive call can never go below 1 or 0 as long as the initial input is valid because it is taken care of by the base case thus we never go past the base case. Also we see that with every call to the function x is getting smaller and thus closer to the base case of 0 or 1.

Example 2 : Factorials

The factorial of a number n is equal to n*(n-1)*(n-2)...1 ie,

F(n) = n*(n-1)*(n-2)...1

Thus the code in c++ for this would be

int factorial(int x)
{
    if(x <= 1)
	return 1;
    return x*factorial(x - 1);
}

Similarly in python this code becomes

def factorial(x):
    if x <= 1:
	return 1
    return x*factorial(x - 1)

Again here if(x == 1) is the base case and returns when x is 1 and return x*factorial(x - 1) is the recursive call. Here too we see that x can never go below 1 as long as the initial input is above 1 and we also notice that with every successive recursive call x gets closer to 1.