Really recursion is overvalued.

I realize that recursive function teaching is not usually done the right way (in my opinion of course) when the example is always used to do something that is sequential rather than recursive. Of course it can be recursive. But recursion goes well when you're going to blow up subsequent executions 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 recursion.

Consumption

If the language does not provide an optimization, the memory consumption and processing may be much larger than the loop version. It can cause run-time problems, such as the stack overflow . Current PHP (on the date of this response) does not optimize.

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

Note that languages that optimize, transform recursion into iteration. Handling the iteration is best for the computer. Recursion may be better for the human to understand.

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

It is important to 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 being recursive or iterative.

You can do manual optimization, such as memoing , for example. In iterative it is a help. In recursion it may be mandatory and still not solve everything. It is a way to prevent recursion from occurring or to decrease its depth, which may be the difference between whether it works or not.

Where is interesting

Recursive functions are interesting when executing an inherently recursive algorithm. Working in data trees , for example, is often best expressed recursively.

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

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

Unless language lacks the feature of the loop, recursion should only be used when it will clearly make the code more readable to everyone, not just the academics who often 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 I have already done on the subject. Although the utluiz response there responds more directly to the question, I find the response of mgibsonbr more interesting to the context here.

TL; DR

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

Consider, for example, 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 data structure, often a stack, whereas 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 method method execution.

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)

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 . Scheduling works makes everything heavy of that capacity.
• It's more compact . Less code means easier maintenance, less possibility of errors, and so on.
• Automatic status management . In the iterative example a stack ( stack ) was used. Now think of languages where memory management is not automatic. In C, for example, you would have to add code to allocate and release stack elements at each iteration.

  

2nd How does the memory consumption?

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

Recursive routines often use more memory by relocating 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 good or ill. It is possible to create a more optimized routine than the recursive version. But you should not take this as a rule, there are excellent recursive implementations that are more efficient than the average of iterative implementations.

In addition, efficiency depends greatly on the number of runs and the level of recursion. As well as sort routines, some implementations work best when there are few iterations and others when there are more iterations. Some recursive implementations are best for small processing. See, for example, on this site that 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 >.

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

• Memoization , or memorizing results
• Tail call , or tail recursion

  

3rd. Should I use a recursive function rather than a common Repetition Loop (eg for / while)? What would be the ideal situations for using recursive functions?

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

I believe that ideal situations have been exemplified above, ie:

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

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 for knowing when to deploy is when you need to run multiple variable number repetition loops.

When you are sure you can solve something with X number of repeat loops, then it stands to reason that it is wiser to apply multiple loops as long as there are not many loops. For example, 10 loops is a lot of stuff then it would be a case of thinking about using recursion.

Imagine

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

How would that look in a recursion?

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

Below is a practical example of usage.

In this situation I had to create a function to normalize a path (filesystem). In PHP there is the realpath() function, however, this function normalizes only one 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 just to normalize.

This is a practical example of using recursion. Here you would not have 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;

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 that.

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 overhead for calling methods.

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