Computational Complexity of Recursive Functions

Nov 7, 2016 · Gian Sass

A function is deemed recursive if it satisfies the following three rules:

There must be at least one halting condition.
The function must call itself.
The parameters thereof must be altered such that the halting condition will eventually stop the recursion.

The easiest example of a recursive function would be calculating the factorial of a (natural) number.

int fact(int n)
{
    if (n == 0) /* 1. Halting condition */
        return 1;
    else
        return n * fact ( n - 1 ); /* 2. Recursive call, 3. alteration of the parameter */;
}

As there is only a single recursive call, the recursive function will call itself a total of n times. Therefore its complexity is $O(n)$ .

A more interesting example is an algorithm for calculating the nth Fibonacci number.

int fib(int n)
{
    if( n == 0 )
        return 0;
    else if( n == 1 )
        return 1;
    else
        return fib( n - 1 ) + fib( n - 2 );
}

Now there is a total of two recursive calls with two halting conditions (also called the seed values of the iteration). Noticeable is the curious amount of calls it takes for one recursion to end. If we graph the amount of calls vs. n we find a graph looking similar to an exponential function.

As we now assume that the function determining the amount of calls is exponential, and that the amount of calls of n is equal to the amount of calls of n-1 plus the amount of calls of n-2. We can now, by induction, find the function mathematically.

Let $F(n) = F(n-1) + F(n-2).$

Since we assume the function to be exponential we can substitute: $x^n = x^{n-1} + x^{n-2}.$

Dividing by $x^{n-2}$ leaves us with $x^2= x + 1.$

Solving, we find $x = \frac{1+\sqrt{5}}{2} \approx 1.618$ , also called the Golden ratio. The second solution can be discarded as it is negative (approaches zero as n approaches infinity). Thus, the computational complexity of the Fibonacci function happens to be $O(\phi^n)$ . But as there is bias to powers of two in computer science the complexity may be formally declared $O(2^n)$ .

Another method of determining the computational complexity would have been sheer analysis. The iterations of a function exponentially increase by the amount of recursive calls. As the Fibonacci function calls itself two times per iteration, the analysed complexity would be $O(2^n)$ , which is roughly equal to our non-rounded solution.