Recursive programming : A Picture is Worth 1,500 Words

Recursion

What is recursive programming

“I know that I know nothing…”

Socrates

In programming terms, recursion is when a function calls itself to solve a problem. In other words, in recursion algorithms, we find a solution to a problem using the solution to the same problem.

Confused ??! It’s OK, you are right, it seems strange and paradoxical. For a better understanding of the concept, let’s take an everyday problem that we can solve recursively. Let’s take writing this article as example assuming that I want to make it 100 lines long, if I plan to write 10 lines every time I open it up, then, the first time I write 10 lines, I leave myself 90 lines to write. Next time I write 10 lines and have only 80 lines to write and so on until I have zero lines left to write. So you see ?? Each time, I partially solve the problem and the remaining problem is being reduced, then solved by the same way and so on until the problem is entirely solved.

How a recursive program works

Based on what has already been said, you can notice that a recursive program must have the following items:

1. Condition of stop (base case)
2. Step toward base case
3. Recursive call of the step (the function recall itself)

To apply the concept, let’s see what happens when we use this code:

This code calculates a float to the power of another float this way:

Recursion

So, for x = 4 and y = 3, the program will perform this way:

As presented in the pictures above, as long as the base case is not reached, the function calls itself.

How recursion behaves in stack

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out), i.e., the element inserted at the last is the first element to come out. The insertion of an element into stack is called push operation, and deletion of an element from the stack is called pop operation.

General presentation of stack (LIFO order)

Our function behaves in stack as the following (knowing that x=3 and y=2)

_pow_recursion in stack

I hope that this article is helpful and useful for you !