Recursion and the Ackermann Function

The art of defining something in terms of itself, which is a naughty no-no in dictionaries but often works out okay in computer programs.

Recursion can be used in computer science to breakdown what would normally be a complicated problem into smaller instances of the same problem.

To illustrate this concept we will use factorials. If you remember from math class a factorial is the product of all positive integers less than or equal to itself.

!4 = 4x3x2x1 -> 24

This is rather a easy concept however, how can we use recursion to solve this same problem no matter the number to be factored?

// Use recusion to solve for !n
function fact(n) {
  if (n === 1) return 1;
  return n * fact(n-1);
}

const fact4 = fact(4); //returns 24
console.log(fact4); //Prints 24

Let's break the code down. Because the function knows what the factorial of 1 is. We check to see if the argument passed is 1. If so we tell whoever asked that its 1. If the argument is not 1 then we tell whoever is asking that the factorial of n is n times whatever the factorial of n-1 is. return n*fact(n-1);

Recursion in nature is very expensive computationally because each time you use recursion this requires another instance to be placed on the stack. In computer science anything that can be done recursively can be done iteratively. If this is the case why would you want or need to use recursion. The best answer is readability and if the computation is small in number (stacks needed) to return an answer it makes sense. Lets see this same example using a while loop.

    // use a while loop to solve for !n
    function fact(n) {
        let count = 1;
        let product = 1;
        while(n >= count) {
            product = product * count;
            count++;
        }
        return product;
    }

Although this works, the code itself is more complex than it needs to be. The need to instantiate and update variables is similar to recursions use of the stack; values are updated until the condition is met. In contrast when the condition is met the value is returned and multiplied by itself. While, iterations are more useful and less expensive in most cases this is a prime example when to use recursion instead of iteration.

You still might ask why do we have recursion if technically speaking we don't need it. That's where I say there are things so fundamentally recursive that a loop can't be used. The Ackermann Function is a total computable function that is not primitive recursive. What primitive recursive means is that the algorithm can not be derecursed.

Ackermann Function

    Function ack(m, n) {
        if (m === 0) return n+1;
        if (m > 0 && n === 0) return ack(m-1, 1);
        if (m > 0 && n > 0) return ack(m-1, ack(m, n-1));
    }
 ```javascript line-numbers  
This is a illustration of an algorithm that is computable but can not be solved using a loop. It's proven to compute if given a positive integer value. This is because m and n are constantly decreasing until both values are zero.