Today we will talk about recursion, a very useful tool for writing code. This tool allows you to make your code more succinct and easier to read.
The concept of recursion is not computer-specialized and is natural.
Recursion is a situation when an object contains itself in its description, that is, it is its part. In short, recursion allows you to get away from the simplest imperatively written iterations to a more declarative style of programming.
Recursion examples
A living example of recursion is tree growth — from the tree trunk grow smaller trees — branches, then smaller branches grow from the bigger ones, and so on until only leaves remain. Recursion in nature can be endless — if the tree does not die, new branches continue growing from the branches, and so on without stopping.
Recursion is also often used as an artistic technique. I'm sure many of you have seen how an artist paints a picture, which depicts an artist painting an artist, and so on.
A great visual example of recursion can also be the picture, where the desktop depicts the desktop depicting the desktop:
Recursion is widely used in computer science when solving problems that require multiple repetitions of one action with the accumulation of the result. For example, to calculate the factorial, we can create a function that will call itself internally with new arguments. The key feature of using recursion in programming is the reachability rule — any recursive function must contain a reachable condition for exiting recursion. If there is no such a condition, the function will execute indefinitely and in the case of using a recursive process (lazy evaluation), we will get a stack overflow—this means that the application will crash, and there will be nothing we can do.
There are two main processes in which we can use recursion — recursive and iterative processes.
What is a recursive process?
In the first case, we do not calculate the final result until we reach the terminal condition. In the second case, the intermediate result is calculated at each execution step. The steps are interrupted when the terminal condition is reached. At first sight, it may seem not so clear.
Let us look at what is meant by a recursive process and its lazy evaluation with a realistic example.
Example
Assume we want to calculate the factorial of a number 5. The factorial is calculated for all non-negative numbers. Thus, we will sequentially expand one factor at a time until we reach the condition to exit the recursive loop. The condition for exiting the recursive loop, in this case, will be that the last factor (which is a factorial) reaches zero, that is, the operation of calculating the factorial for zero will be the last one for recursion. It will look like this:
5! = 5 × 4! => 5 × 4 × 3! => 5 × 4 × 3 × 2! => 5 × 4 × 3 × 2 × 1! => 5 × 4 × 3 × 2 × 1 × 0! => 5 × 4 × 3 × 2 × 1 × 1
As you can see from the example, we cannot calculate the final result in parts — we are forced to accumulate factors until we open the entire chain and can perform a complete calculation, which means that the call stack will accumulate until the terminal condition is reached. If the resources of the machine are limited and the call stack is very long, we may also run out of resources, and we may get a stack overflow, yet we have a terminal condition. Then the execution of a recursive process is impossible due to limited memory resources.
Let us reproduce the above example in code to understand the implementation of the recursive function:
What is an iterative process?
Now let us look at the iterative process. As we said earlier, its feature is that we do not wait for the complete “expanding” of the chain of calls to perform actions on the function arguments but perform any calculations in each iteration, saving them using the accumulator.
Let us see how this happens in the already known example with a factorial:
5! = 5 × 4! => // At this step, we have an accumulator equal to 5 20 × 3! => // We calculate the intermediate result equal to 20 60 × 2! => // We continue to recalculate the intermediate result... 120 × 1! => // We continue to recalculate the intermediate result... 120 × 0! => // We continue to recalculate the intermediate result... 120 // The terminal condition is reached; we stop the calculation.
The advantage of this approach is that we do not create a long chain of calculations, doing the maximum useful work at each step, thus removing the limit on the stack depth. However, in this case, be sure to remember the terminal condition. Otherwise, we will never finish executing our iteration cycle.
Example
This approach is more time consuming to implement in code, let us look at an example:
Summing up
A recursion is a useful tool for writing code that allows you to make it more capacious and easier to read, getting away from the simplest imperatively written iterations to a more declarative style of programming. However, it is worth remembering that its use should precede the analysis of a specific problem for the optimal choice of processes, which implements a recursive approach to avoid subsequent errors in the program running.
