less_retarded_wiki/recursion.md

Recursion

See recursion.

Recursion (from Latin recursio, "running back") in general is a situation in which a definition refers to itself; for example the definition of a human's ancestor as "the human's parents and the ancestors of his parents" (fractals are also very nice example of what a simple recursive definition can achieve). In programming recursion takes on a meaning of a function that calls itself; this is the meaning we'll suppose in this article, unless noted otherwise.

We divide recursion to a direct and indirect one. In direct recursion the function calls itself directly, in indirect function A calls a function B which ends up (even possibly by calling some more functions) calling A again. Indirect recursion is tricky because it may appear by mistake and cause a bug (which is nevertheless easily noticed as the program will mostly run out of memory and crash).

When a function calls itself, it starts "diving" deeper and deeper and in most situations we want this to stop at some point, so in most cases a recursion has to contain a terminating condition. Without this condition the recursion will keep recurring and end up in an equivalent of an infinite loop (which in case of recursion will however crash the program with a stack overflow exception). Let's see this on perhaps the most typical example of using recursion, a factorial function:

unsigned int factorial(unsigned int x)
{
  if (x > 1)
    return x * factorial(x - 1); // recursive call
  else
    return 1; // terminating condition
}

See that as long as x > 1, recursive calls are being made; with each the x is decremented so that inevitably x will at one point come to equal 1. Then the else branch of the condition will be taken -- the terminating condition has been met -- and in this branch no further recursive call is made, i.e. the recursion is stopped here and the code starts to descend from the recursion. The following diagram show graphically computation of factorial(4):

factorial(4) = 4 * 6 = 24
 |                 ^
 |                 | return
 |                 '------------.
 | call                         |
 '-----> factorial(3) = 3 * 2 = 6
          |                 ^
          |                 | return
          |                 '------------.
          | call                         |
          '-----> factorial(2) = 2 * 1 = 2
                   |                 ^
                   |                 | return
                   |                 '-----.
                   | call                  |
                   '------> factorial(1) = 1  <-- end condition met

Note that even in computing we can use an infinite recursion sometimes. For example in Hashell it is possible to define infinite data structures with a recursive definition; however this kind of recursion is intentionally allowed, it is treated as a mathematical definition and with correct use it won't crash the program.

Every recursion can be replaced by iteration and vice versa (iteration meaning a loop such as while). In fact some language (e.g. functional) do not have loops and handle repetition solely by recursion. This means that you, a programmer, always have a choice between recursion and iteration, and here you should know that recursion is typically slower than iteration. This is because recursion has a lot of overhead: remember that every level of recursion is a function call that involves things such as pushing and popping values on stack, handling return addresses etc. The usual advice is therefore to prefer iteration, even though recursion can sometimes be more elegant/simple and if you don't mind the overhead, it's not necessarily wrong to go for it. Typically this is the case when you have multiple branches to dive into, e.g. in case of quicksort. In the above example of factorial we only have one recurring branch, so it's much better to implement the function with iteration:

unsigned int factorial(unsigned int x)
{
  unsigned int result = 1;
  
  while (x > 1)
  {
    result *= x;
    x--;
  }

  return result;
}

How do the computers practically make recursion happen? Basically they use a stack to remember states on each level of the recursion. In programming languages that support recursive function calls this is hidden behind the scenes in the form of call stack. This is why an infinite recursion causes stack overflow.

Another important type of recursion is tail recursion which happens when the recursive call in a function is the very last command. It is utilized in functional languages that use recursion instead of loops. This kind of recursion can be optimized by the compiler into basically the same code a loop would produce, so that e.g. stack won't grow tremendously.

Mathematical recursive functions find use in computability theory where they help us (similarly to e.g. Turing machines) define classes of functions (such as primitive recursive and partial recursive) by "how strong of a computer" we need to compute them.