Tower Hopper problem recursive approach The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from tower[0] (0 indexed) to outside of the array.

For ex, if we have towers = [4, 2, 0, 0, 2, 0], we can jump from towers[0] to towers[4] and then outside of the bounds of the array. Or we could jump from towers[0] to towers[1] to towers[4] and then out of the array.
But if we had towers = [4, 2, 0, 0, 1, 0], there would be no way to hop out of the array and we should return False.

I wrote a recursive function that starts from the last array index.

I'm concerned that the way I wrote the function is not the most efficient. It seems to work but I'm thinking I might not have to pass in that many arguments. I very much welcome any other kind of criticism (style, syntax, design...).

I was also wondering (but maybe I should post this as another question) how to turn this into a dynamic programming format. Hints on how to do that (rather than a straight up solution) would be greatly appreciated. 

int main(int argc, char const *argv[])
{

    int num_towers = 6;

    int towers[6] = {5, 4, 3, 3, 1, 0};

    printf("These towers are %s\n", is_hoppable(towers, num_towers - 1, num_towers) ? "hoppable" : "NOT hoppable");

    return 0;
}




int is_hoppable(int* towers, int jumpTower, int targetTower){   

    if (jumpTower == 0){
        if (jumpTower + towers[jumpTower] &gt;= targetTower)
            return 1;
        else 
            return 0;
    }

    if (jumpTower + towers[jumpTower] &gt;= targetTower)
        return is_hoppable(towers, jumpTower - 1, jumpTower);
    else 
        return is_hoppable(towers, jumpTower - 1, targetTower);

}
The recursion stop condition looks clumsy. First, inside the if clause you already know that jumpTower == 0. Second,

    if (condition)
        return 1;
    else
        return 0;


is a long way to say return condition. Suggested rewrite:

    if (jumpTower == 0) {
        return towers[0] &gt;= targetTower;
    }




The two recursive calls differ only by the last parameter. This strongly hints to make the function tail-recursive:

    if (jumpTower + towers[jumpTower &gt;= targetTower) {
       targetTower = jumpTower;
    }
    jumpTower -= 1;
    return is_hoppable(towers, jumpTower, targetTower);


and mechanically eliminate tail recursion (sorry for another shameless self promotion):

    while (jumpTower &gt; 0) {
        if (jumpTower + towers[jumpTower &gt;= targetTower) {
           targetTower = jumpTower;
        }
        jumpTower -= 1;
    }
    return towers[0] &gt;= targetTower;


Now the problem is reduced to a single loop. It doesn't look right. But don't blame me. It is a mechanical rewrite (much like a C compiler would do), so if there's a problem here, there must be a problem in the original code.



The printf line is too long to my taste. I was almost sure that you print int as %s. Then I scrolled.



Returning bool rather than int would clarify intentions.