What is the advantage of using recursive functions?

I recently discovered the famous (or not so famous) recursive functions and found the concept very interesting. However, during my reading some doubts arose regarding the use of such.

1st What is the advantage of using a recursive function ? For I cannot understand the advantage of this:

<?php
function recursiveFunction($num)
{
    if ($num != 0) {
        echo "O valor é $num. <br>";
        recursiveFunction(--$num);
    }
}
recursiveFunction(10);

About this:

<?php
function recursiveFunction($num)
{
    for ($i = $num; $i != 0; $i--) {
        echo "O valor é $i <br>";
    }
}
recursiveFunction(10);

2ª how is the memory consumption? For from what I understood a recursive function is executed within another function (then making a loop of repetition). Depending on the size of the calculation, could using a recursive function impair the performance of my application?

3rd should I use a recursive function instead of a common repeating loop (e.g. for/while)? What would be the ideal situations for using recursive functions ?

Author: Maniero, 2016-01-11

5 answers

Actually recursion is overvalued.

I realize that recursive function teaching is not usually done the right way (in my opinion, of course) when the example always used is to do something that is sequential and not recursive. Of course it can be recursive, but recursion goes well when you go blasting subsequent executions using the same criterion. I even understand that simulating a sequence recursively is the simplest way to teach, but it creates the addiction that this it's what's best about recursion.

Consumption

If the language does not provide an optimization the memory and processing consumption can be much higher than the loop version. It can cause runtime issues, such as Stack Overflow . Current PHP (at the date of this answer) does not do optimization.

Function calls are expensive in the two analyzed vectors. Without considering the algorithm itself each call has a cost mainly to prepare the environment of the function and return to the original state. And to ensure that you can return to the original state application stack resources are being consumed.

Note that languages that optimize turn recursion into iteration. Porting the iteration is better for the computer. Recursion may be better for the human to understand, in some cases .

This optimization is only to eliminate the calls and cost cited above, not to change the way the algorithm is executed.

Is important note that this does not affect the complexity of the algorithm. Both are linear, logarithmic, exponential or otherwise, according to the specific need of the algorithm, it has nothing to do with the fact that they are recursive or iterative.

You can do manual optimization, such as memoization for example. In iterative it is a help, in recursion it can be mandatory and even then not solve everything. It is a way to prevent recursion from occurring or decrease its depth that may be the difference between it working or not.

Where is interesting

Recursive functions are interesting when going to run an inherently recursive algorithm. Working on data trees , for example, is usually best expressed recursively.

The question example is clearly worse done recursively. It is a simple sequence that does not need the complication of recursion (some disagree).

If it is not obvious that it should be recursive is likely not to be even. The purpose of recursion is to be able to do something as you think the problem. When you force the bar is abusing the language to look smarter. If the mechanism is difficult to understand and does not bring a clear advantage is better not to use. Use when you feel natural. If you study well and are aware of the utility you will realize when to use it.

Unless the language does not have the loop feature, recursion should only be used when clearly it will make the code more readable for everyone, not just academics who usually prefer recursion. Especially in languages that do not have optimization.

More information

I will not go into detail because almost everything has already been answered in question that I have already done on the subject. Although utluiz's answer there answers more directly to the question I find mgibsonbr's answer more interesting for the context here.

 53
Author: Maniero, 2020-10-13 11:49:23

TL; DR

All recursive code can be translated into an iterative form, but some algorithms are naturally recursive and more easily represented in this form.

Think, for example, of traversing all nodes in a tree or graph, processing all files in a directory and subdirectories, and so on.

In iterative mode you are responsible for manually managing the state of each step of the algorithm using some structure of data, often a stack, while in recursive mode you delegate this function to your programming language, by making use of variables and parameters that are automatically allocated in the execution stack at the beginning of each execution of the method method.

Example

To answer the questions, consider something a little more complex. I extracted the pseudo-code to traverse trees from the Wikipedia .

Recursive method

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

Method iterative

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

Answers

1ª what is the advantage of using a recursive function?

In your example there is little advantage, but in what I put above, we clearly see that the recursive method:

  • better expresses the functionality . Programming function makes everything heavy of this ability.
  • is more compact . Less code means easier maintenance, less chance of errors and so on forth.
  • automatic State Management . In the iterative example a stack (stack) was used. Think now of languages where memory management is not automatic. In C, for example, you would have to add code to allocate and release stack elements on each iteration.

2ª how is the memory consumption?

Depends on the function. Usually you should do a memory complexity and time analysis to analyze the differences, but it is somewhat obvious that in the vast majority of cases, recursive routines consume more memory and require more execution cycles.

Recursive routines usually use more memory by relocating variables on each recursive call, but iterative routines can use the same amount of memory if values are saved in lists or stacks, for example.

In iterative mode you have control, for better or for worse. There is a possibility to create a more optimized routine than the recursive version. But one should not take this as a rule, after all there are excellent recursive implementations that are more efficient than the average iterative implementations.

Also, efficiency depends greatly on the number of executions and the level of recursion. Just like ordering routines, some implementations work best when there are few iterations and others when there are more iterations. Some implementations recursives are better for small processing. See, for example, on this site that the performance for Fibonacci where n <= 5 was better for the recursive version.

In a very simple example, the Fibonacci recursive function has exponential complexity while the version can be implemented with two or three simple variables and therefore has constant memory usage .

On the other hand, almost always recursive routines end up needing be rewritten in its iterative version when the number of elements or Numbers processed is large, after all Recursion has a sensitive limit of both memory and data stacking.

And in addition to all this, there are techniques that can improve the performance and capacity of recursive routines, examples of which are:

3rd should I use a recursive function instead of a common repeating Loop (e.g. for/while)? What would be the ideal situations for using recursive functions?

Should only if the algorithm is better expressed recursively and if the general use of that algorithm will not exceed the recursion limits.

I believe that the ideal situations have been exemplified above, that is:

  • inherently algorithms recursive, best expressed in this format
  • computational use is moderate, so as not to exceed the recursion limits
 26
Author: utluiz, 2016-01-11 04:28:06
  1. recursive functions are an advantage for cases where the problem is naturally defined as a function of itself, and where the recursive solution is the simplest. At first this may seem strange since recursion seems complicated and confusing, but over time and with understanding (a lot of practice too) you learn to identify problems where it is the best solution.
  2. usually recursion represents an additional expenditure of memory, this occurs because each call of a function allocates a frame in the Call Stack, so each new invocation that the recursive function makes itself allocates a new frame in the stack and each new frame accumulates more memory, all this memory is only released when all recursive calls reach the breakpoint (when $num is == 0 in your example). If the recursive function makes too many calls to itself (accumulate too many frames in the stack) a "Stack Overflow" will occur. I recommend that you read this question and the answers provided in case you want a greater understanding about what the call stack is and how a stack overflow can occur.
  3. how hard life is the answer is, it depends. As I have commented before the recursion advantage is for recursive problems by nature and for which a recursive solution is the simplest and most straightforward, a classic example is the manipulation of binary trees, an inherently recursive data structure. My suggestion final is: learn recursion, understand how it works, practice, eventually you will know the best time to use.
 12
Author: BrunoRB, 2017-04-13 12:59:39

Those who do not experiment in practice end up not understanding the theory. So it's always good to show a practical example of use in the "real world".

A basic tip to know when to deploy is, when you need to perform multiple variable number repeat loops.

When you are sure that you can solve something with X number of repeat loops, then it is logical that the most sensible thing is to apply multiple loops, as long as they are not many. For example, 10 loops is a lot then it would be the case to think about the use of recursion.

Picture

while(){
    while(){
        while(){
            while(){
                while(){
                    while(){
                        while(){
                            while(){
                                while(){
                                    while(){

How would that look in a recursion?

function foo()
    while(){
       foo();

Below, a practical example of use.

In this situation I needed to create a function to normalize a path (filesystem). In PHP there is the function realpath() but this function normalizes only an existing path. The function below does the same as realpath() with the difference that it ignores whether the path exists or not. The purpose is only to normalize.

That it is a practical example of using recursion. Here in this case it would not fit to use multiple loops manually.

$path_canonicalize = function($str, $started = false) use(&$path_canonicalize)
{
    $str = str_replace('/', DIRECTORY_SEPARATOR, $str).DIRECTORY_SEPARATOR;

    if (!$started)
        $str = preg_replace("/".preg_quote(DIRECTORY_SEPARATOR, "'".DIRECTORY_SEPARATOR."'")."{2,}/", DIRECTORY_SEPARATOR, $str);

    $pos = strpos($str, '..'.DIRECTORY_SEPARATOR);
    if ($pos !== false)
    {
        $part = trim(substr($str, 0, $pos), DIRECTORY_SEPARATOR);
        $str = $path_canonicalize(trim(substr($part, 0, strrpos($part, DIRECTORY_SEPARATOR)), DIRECTORY_SEPARATOR).DIRECTORY_SEPARATOR.trim(substr($str, $pos+3), DIRECTORY_SEPARATOR), true);
    }
    return rtrim($str, DIRECTORY_SEPARATOR);
};

/*
Try those cases to check the consistency:
$str = __DIR__.'/template//////../header//..';
$str = __DIR__.'/template///..///../header//..';
$str = __DIR__.'/template/../header/..';
$str = __DIR__.'/template/../header/../';
$str = __DIR__.'/template/../header/..//';
$str = __DIR__.'/template/../header/..///';
$str = __DIR__.'/template/../header/..///..';
$str = __DIR__.'/template/../header/..///../';
$str = __DIR__.'/template\\..\\header\\..';
*/
$str = __DIR__.'/template/../header/..///..//';
echo 'original: '.$str.PHP_EOL;
echo 'normalized: '.$path_canonicalize($str).PHP_EOL;
 5
Author: Daniel Omine, 2016-12-22 02:54:08

In addition to what has been said in the other answers, recursive functions are especially advantageous in cases where it is possible to divide the problem in half. This is evident when working with binary trees, but is not limited to this.

Consider the two functions below to calculate multiplication from successive sums. While the iterative solution has O(N) complexity, the recursive solution has O(log(n)) complexity. This should compensate for the overhead for calling methods.

Sorry for the Python code, it was the language I was working on, but I think you can express the concept. If I have time later, I can try to translate to PHP.

def multIterativa(a, b):
    total = 0
    for i in range(b):
        total += a
    return total

def multRecursiva(a, b):    
    if b == 0:
        return 0
    if b == 1:
        return a
    total = multRecursiva(a, int(b / 2))
    total += total
    if b % 2 != 0:
        total += a
    return total
 0
Author: Renato Lenz Costalima, 2017-11-29 14:42:55