What makes speed of these recursive pieces so different?

Question

I have to work out a recursive function to apply on an assignment(for which im not allowed to use the standard math library about the tower of Hanoi. I stumbled upon the following code which i thought would be a good piece for the assignment to work with, however it is impossible to run it for (n > 30) as it's just so slow:

#include <stdio.h>
#include <stdlib.h>

int TOH(int,char,char,char);

int main()
{
    int n;
    printf("\nEnter number of disks:");
    scanf("%d",&n);
    int c = TOH(n,'A','C','B');
    printf("\nTotal number of moves = %d \n ", c);
    return 0;
}

int TOH(int n,char x,char y,char z)
{
    int count = 0;

    if(n>0){
    count = TOH(n-1, x, z, y);
    count++;
    count += TOH(n-1, z, y, x);
    }
    return count;
}

While looking for a solution for the speed, i stumbled upon this code, which runs instantly while using recursion. I'm lost on where this difference in speed comes from:

#include <stdio.h>
#include <stdlib.h>

float count_moves(int);
float power(int);

int main()
{
    int STACKS;
    printf("\nEnter numbers of disks: ");
    scanf("%d", &STACKS);
    float total = count_moves(STACKS);
    printf("\nTotal number of moves: %.0f\n", total);
    return 0;
}

float power(int multi)
{
    if(!multi)
    {
        return 1;
    }

    else
    {
        return 2 * power(multi - 1);
    } 
}

float count_moves(int layers)
{
    if(!layers)
    {
        return 0;
    }

    else
    {
        return power(layers - 1) + count_moves(layers - 1);
    }
}

How is the second one able to instantly print something in the console, while the second one takes longer the bigger a number i make n/STACKS?

Answer 1

Firstly I would suggest you to draw the recursion tree. See how big it becomes for pegs = 30. Refer to Complexity for towers of Hanoi? It has a complexity of O(2^n). http://www.iitk.ac.in/esc101/08Jan/lecnotes/lecture32.pdf

The second solution is not computing it in the traditional way. It is making a single call. T(n-1) + c = O(n^2)

So, 2^30 vs 30^2. Guess, which one is faster!

See for yourself.

add a counter to the functions like (make 'c' and 'd' global)

float power(int multi)
{
    printf("d = %d\n",d);
    d++;
    if(!multi)
    {
        return 1;
    }

    else
    {
        return 2 * power(multi - 1);
    } 
}

float count_moves(int layers)
{
    printf("c = %d\n",c);
    c++;
    if(!layers)
    {
        return 0;
    }

    else
    {
        return power(layers - 1) + count_moves(layers - 1);
    }
}

and see the number of times they are called.

Answer 2

Ignoring the pointless parameters, the first algorithm is count = (n > 0) ? TOH(n-1)+TOH(n-1)+1 : 0. Each call to TOH results in two further calls to TOH. Its complexity is O(2^n). Each time that n goes up by one, costs will double.

The second is (layers > 0) ? [something linear] + count_moves(layers - 1) : 0. It's two tail-recursive methods but each call to either generates at most one further call. But it's "do this n times, and for each time, do this other thing n times" so that's n*n. It's O(n^2).

O(2^n) goes up a lot more quickly than O(n^2).

Answer 3

Your first version follows the scheme that would actually compute the sequence of steps to move the rings. But you don't explicitly compute these steps; indeed, your TOH version ignores its arguments! (Except for passing them to recursive calls which also ignore them except for passing them to recursive calls.)

This means that TOH's return value only depends on its first argument n. This also means that your two recursive calls with n-1 will return the same value, so it suffices to all TOH once and use the return value twice. Changing the body of the if inside TOH to this:

int tmp = TOH(n-1, x, y, z);
count = tmp + 1 + tmp;

makes your code terminate immediately with the same answer as before. Note that you will probably get arithmetic overflow above an initial n value of 31.

By the way, GCC at level -O3 seems to be smart enough to perform this optimization automagically on your original code, with no changes whatsoever.