Recursion in computer science:

Introduction

In programming, a recursive function is known as a function that calls itself over and over until a base case is hit. The base case (or the base cases) is the condition that checks if we have gotten the information that we need out of our function. Every recursive function should have at least one base case, but there could be multiple. If there is no base case there will be a "stack overflow", this is when a function calls itself so many times (infinite loop) that the space needed to store the variables and information associated with each call is more than can fit on the stack making the stack overflow (this is the explanation of the name of the famous web StackOverflow).?

The base case as I have explained above is one of the two parts of a recursive function, the other part is the recursive call. As you can imagine the recursive call is when the function calls itself.?

Recursion vs loops (while, do while, for)

The main difference between a loop and recursion is that recursion as was stated before is a mechanism to call a function within the same function while a loop is a control structure that allows executing a set of instructions again and again until the given condition is true.

Every iteration (loop) does not require extra space while every recursive call needs extra space in the stack memory.

Recursion is very useful for solving situations that can be broken down into smaller and repetitive problems. It is widely used on different data structures that have a variety of possible branches like tries, graphs, etc, in this type of case is easier to use recursion than a loop with several conditions.?

We will discuss a bit more about the advantages and disadvantages of recursion in another paragraph.

Explaining recursion with factorial example

Calculating the factorial (mathematical calculation) of a number with recursion is a great first approach to understanding recursion, so let's see how !4 (factorial of four) would be calculated:

!4 = 4 * 3 * 2 * 1

This is the same to:

The following is an implementation of the code in C using recursion to solve this problem:

As you can see when 'n' is equal to 0, it will return one, so this is the base case that allows our program to "know" when to stop and start returning the function calls, first is going to return the last call of the stack that is the factorial of 0 in this example, and then it will be able to return the others functions calls of the stack. The final result will be that factorial of 4 is 24.

I would recommend you to watch the following video that explains in great detail how to calculate factorial numbers with recursion and it gives you a visual idea of what is happening behind the scenes:

So now that we understand the concept of recursion and an example of its implementation was explained, we are able to jump to the next part of this blog and see how the stack works.

Explaining how the stack works using pow recursion

First of all, we will define what is a stack. A stack contains local variables from functions and related book-keeping data. The memory in the stack is managed automatically unlike the heap (another segment of the memory layout). A stack frame is created in the stack when a function is called, each function has its stack frame. It has a LIFO (Last In First Out) structure. Once the calling function completes its execution its stack frame is popped off the stack frame and the thread of execution of called function will continue from the position where it was left.

We are going to use the following code written in C to calculate the value of x raised to the power of y:

Next I will show you how the stack would look if you want to calculate 6 to the power of 4 using the function _pow_recursion:

As you can see the stack builds upwards, and when the base case is encountered (y == 0) it return 1 and get popped off the stack, and then the following functions are called repeting the same proccess until the last function of the stack is called with the value of: 6 * 216 that is 1296, this is the same that: 6 ^ 4.

Advantages and Disadvantages of recursion

Advantages:

• The code may be shorter to write than if you use a loop.
• Extremely useful when applying the same solution over and over to different sub-tasks.
• Reduce the length of code.
• It is very useful in solving problems that use data structures like: trees, graphs, structures that have lots of branches.?

Disadvantages:

• It uses more memory than a non-recursive function like loops (to hold intermediate results on the system stacks).
• For the reason discussed in the above point recursive functions tend to be slower than non-recursive functions.
• The code is harder to analyze than if you use loops.
• In terms of Big O notation, it increases the space complexity of the algorithm, because every time a new call is added to the stack, the amount of memory that is being used is going to increase.

As always, thanks for reading and I hope this was useful! Until next time.