Brief Introduction to Recursion

What is recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.

Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Fibonacci Series, nCr, Factorial etc.

Types of Recursions:

1. Tail Recursion: If a recursive function calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion. After that call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time.
2. Head Recursion: If a recursive function calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion. There’s no statement, no operation before the call. The function doesn’t have to process or perform any operation at the time of calling and all operations are done at returning time.
3. Tree Recursion: To understand Tree Recursion let’s first understand Linear Recursion. If a recursive function calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive function calling itself for more than one time then it’s known as Tree Recursion.
4. Indirect Recursion: In this recursion, there may be more than one functions and they are calling one another in a circular manner.
5. Nested Recursion: In this recursion, a recursive function will pass the parameter as a recursive call.That means “recursion inside recursion”. Let see the example to understand this recursion.

Will add details discussion in next parts.

Let's take a simple recursive function now and analyze its space and time complexity.

def func(n):
    if n > 1:
        return func(n-1)

Let's do the time complexity analysis first. Assume that the total time taken for the above function func() is T(n). Now the T(n) is a sum of the time taken to compare if n is greater than 1 and the time taken to execute func(n-1). So, T(n) can be expressed as -

T(n) = 1 + T(n?1)

1 is the time taken for the comparison (you can put any constant there). Now, what will be the time (in terms of T(n)) for executing func(n-1)?

T(n?1) = 1 + T(n?2)

Similarly,

T(n?2) = 1 + T(n?3)

and so on.

If you pay close attention to the equations, they all are connected. Aren't they? If you substitute them after one another, you get -

T(n) = 1 + (1 + T(n?2)) = 2 + T(n?2) = 3 + T(n?3) = .... = k + T(n?k) (after running the function for k terms)

Now, you need to determine at what point the function is going to stop. According to the anchor condition given, you can write -

Assume that, after running for k terms, the function stops running. If so, then it must be -

n ? k = 1 => k = n?1

Now substituting the value of k (= n -1) in T(n)=k+T(n?k) :

T(n) = (n?1) + T(n?(n?1))

=> T(n) = (n?1)+T(1)

=> T(n) = n?1+1 = n # For T(1) only comparison is required

By the rule of time complexity analysis, T(n)=n can be rewritten as T(n)=O(n). This means the time complexity (worst) of the function is O(n).

The space complexity analysis of the function is simple. The function is an in-memory function and does not make use of any extra variables. So, you can conclude that the space complexity of the function O(n).

Python Recursive Function

We know that in Python, a function can call other functions. It is even possible for the function to call itself. These type of construct are termed as recursive functions.

Following is an example of recursive function to find the factorial of an integer.

Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.

How recursion works?

def factorial(n):
    if n == 1:
        return 1
    else:
        return (n * factorial(n-1))

num = 5

print("The factorial of", num, "is", factorial(num))

In the above example, factorial() is a recursive functions as it calls itself.

When we call this function with a positive integer, it will recursively call itself by decreasing the number.

Each function call multiples the number with the factorial of number 1 until the number is equal to one. This recursive call can be explained in the following steps.

factorial(5)                  # 1st call with 5
5 * factorial(4)              # 2nd call with 4
5 * 4 * factorial(3)          # 3rd call with 3
5 * 4 * 3 * factorial(2)      # 4th call with 2
5 * 4 * 3 * 2 * factorial(1)  # 5th call with 1

5 * 4 * 3 * 2 * 1             # return from 5th call as number=1
5 * 4 * 3 * 2                 # return from 4th call
5 * 4 * 6                     # return from 3rd call
5 * 24                        # return from 2nd call
120                           # return from 1st call

Our recursion ends when the number reduces to 1. This is called the base condition.

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.

What is a base case in recursion

When working with recursion, we should define a base case for which we already know the answer. In the above example we are finding factorial of an integer number and we already know that the factorial of 1 is 1 so this is our base case.

Let's go through another easy example,

def print_number(n):
    if n > 0:
    print(n)
    print_number(n-1)

num = 3
print_number(num)

Steps:

1. It call print_number function with n = 3 as print_number(3). If check if n is greater than 0. Yes 3 is greater than 0 so it print 3 and call print_number function again with n = n - 1.
2. It call print_number function with n = 2 as print_number(2). If check if n is greater than 0. Yes 2 is greater than 0 so it print 2 and call print_number function again with n = n - 1.
3. It call print_number function with n = 1 as print_number(1). If check if n is greater than 0. Yes 1 is greater than 0 so it print 1 and call print_number function again with n = n - 1.
4. It call print_number function with n = 0 as print_number(1). If check if n is greater than 0. No 0 is not greater than 0 so it ends the execution of print_number function.

Please follow the below tracing tree for better understanding:

How Recursion uses Stack?

For above example let's discuss how this function use stack memory.

When print_number(3) executes it's create a record in stack memory. Similarly it creates record for print_number(2), print_number(1) and print_number(0). After reaching base condition point it starts returning values and deleting records those actions are finished.

See below mentioned chart for better understanding.

Space-time analysis of a recursive function:

For a given input, a function is supposed to produce some kind of output. In order to do that how much time does the function takes? The time-complexity measure approximates this time, and it is also called the runtime of the function. Similarly, the space-complexity measure approximates the space (memory) requirements of a function, i.e., for a given input. But why these are even required?

• Instead of running a function on the range of inputs with varying sizes, you can easily approximate how a function might behave on different inputs with varying sizes.
• If you have two functions that are fulfilling the same objective which one will you take? What measures will you consider to make the decision? Yes, you guessed it right. You will compare them by analyzing their space and time complexities and see which one is performing better.

Advantages of Recursion

1. Easier to write.
2. Code is easier to read and understand.
3. Recursive functions make the code look clean and elegant.
4. A complex task can be broken down into simpler sub-problems using recursion.
5. Sequence generation is easier with recursion than using some nested iteration.
6. It takes less lines of code to solve a problem using recursion.

Disadvantages of Recursion

1. Not all problems can be solved using recursion.
2. If you don’t define the base case then the code would run indefinitely.
3. Sometimes the logic behind recursion is hard to follow through.
4. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
5. Recursive functions are hard to debug.

GitHub Link: Recursion Introduction