What is the advantage of using recursive functions?

Question

Recently discovered the famous (or not so famous) Recursive Functions and I found the concept very interesting. However, during my reading I had some doubts regarding the use of such.

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);

2nd What about memory consumption? Because from what I understood a recursive function is executed within another function (then making a Loop). Depending on the size of the calculation, the use of a recursive function could impair the performance of my application?

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

Answer 1

Actually recursion is overrated.

I realize that the teaching of recursive function 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’re exploding subsequent runs using the same criteria. I even understand that simulating a sequence recursively is the simplest way to teach, but it creates the addiction that this is the best thing about recursion.

Consumption

If the language does not provide an optimization the memory consumption and processing can be much higher than the loop version. Can cause problems at runtime, such as pile burst. Current PHP (on the date of this answer) does not perform optimization.

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

Note that languages that optimize transform recursion into iteration. Porting 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 the cost quoted above, not to change the way the algorithm runs.

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

Manual optimization is possible, such as memoisation for example. In iterative is a help, recursion can be mandatory and still not solve everything. It is a way to prevent recursion from occurring or diminishing its depth which may be the difference between it working or not.

Where it’s interesting

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

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

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

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

More information

I won’t go into detail because almost everything has been answered in question I’ve already done on the subject. Although the answer of utluiz there answers more directly to the question I consider more interesting the answer of mgibsonbr to the context here.

Answer 2

TL;DR

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

Think, for example, of going through all the nodes of a tree or graph, processing all the files of 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 data structure, 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 to the execution stack at the beginning of each method execution.

Example

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

Recursive method

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

Iterative method

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

1st What is the advantage of using a Recursive Function?

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

• Better expresses functionality. Programming work makes everything heavy that capacity.
• Is more compact. Less code means easier maintenance, less possibility of errors and so on.
• Automatic state management. In the iterative example a stack was used (stack). 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 in each iteration.

2nd How does memory consumption look?

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 reallocating variables to 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 the possibility of creating 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.

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

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

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

And beyond all that, there are techniques that can improve the performance and capacity of recursive routines, examples being:

• Memoization, or memorization of results
• Tail call, or tail recursion

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

It should only be if the algorithm is best expressed recursively and if the general use of that algorithm will not exceed recursive limits.

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

• Inherently recursive algorithms, best expressed in this format
• Computational use is moderate so as not to exceed recursion limits

Answer 3

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 (much practice too) you learn to identify problems where recursion is the best solution.
2. Usually recursion represents an additional expense 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 on the stack and each new frame accumulates more memory, all that memory is only released when all recursive calls reach the halting point (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" (stack overflow) will occur. I recommend you read this question and the answers provided if you want a greater understanding of what the call stack is and how a stack overflow can occur.
3. How hard life is, the answer is, depends. As I’ve 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 final suggestion is: learn recursion, understand how it works, practice, eventually you will know the best time to use.

Answer 4

Who does not experiment in practice ends up not understanding the theory. So it is 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 run multiple variable number repeat loops.

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

Imagine

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

How that would 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 a function realpath() however, this function normalizes only an existing path. The function below does the same as realpath() except that it ignores whether the path exists or not. The purpose is only to normalize.

This is a practical example of recursive use. 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;

Answer 5

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 complexity O(n), the recursive solution has complexity O(log(n)). This should compensate for the overload for calling methods.

Sorry about the Python code, it was the language I was working on, but I think you can express the concept. If you have time later, I can try translating 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