Recursion Troubles...

[shuffman]

I'm working on this problem that has n positive integers in a row except for the first column, which always contains zero, these numbers represent the cost to enter each column. I'm supposed to get to the end of the board with the path that costs the least. I can either jump 1 or 2 spaces at a time.

So say the board was:
0 3 80 6 57 10

then I would chose; 3, 6 and 10 for a cost of 19. I 'm just having troubles on how the heck I'm supposed to make this a recursive problem. I'm a second year programmer and this is the first time I've come to one of these sites to ask for help because I usually like to figure it out on my own but I just can't seem to think of what I'm doing wrong.

Here is what I have so far:

int jumpIt( int board[], int pos )
{
    int value;
    if( board[pos+1] < board[pos+2] )
    {
        value = board[pos+1];
        return value;
    }
    else
    {
        pos = pos+1;
        jumpIt( board, pos );
    }
}

Any help on this would be great, hell even an algorithm to get me off on the right foot would be very appreciated.

Thanks,
Scott

[shuffman]

I forgot to mention that I am calling this function inside a for loop:

//calculate the cheapest way of getting to the end by calling the function jumpIt()
    for( int x = 0; x < ARRAY_SIZE; x++ )
    {
        total += jumpIt( board, x );
    }

[shuffman]

OKAY! I think I actually solved it on my own...I don't know if it works for the end case though...I've done multiple test runs and it seems to me that it does...but for some reason I don't want to trust myself on this. Can someone tell me if I messed up with the end case?

#include <iostream>
using namespace std;

const int ARRAY_SIZE = 10;
int pos = 1;

int jumpIt( int board[], int pos );


int main()
{
    int board[ARRAY_SIZE];
    int total = 0;
    board[0] = 0;
    srand(54); // 54 chosen arbitrarily
    for (int k = 1; k < ARRAY_SIZE; k++)
        board[k] = (rand() % 100) + 1;  // costs are 1-100, uniformly distributed

    //print out the array
    for( int k = 0; k < ARRAY_SIZE; k++ )
        cout << board[k] << endl;

    //calculat the cheapest way of getting to the end by calling the function jumpIt()
    total += jumpIt( board, pos );

    cout << total << endl;
    return 0;
}

int jumpIt( int board[], int pos )
{
    if( pos == (ARRAY_SIZE-1) )
        return board[pos];
    else
    {
        if( board[pos] < board[pos+1] )
        {
            return board[pos] + jumpIt( board, pos+1 );
        }
        else if( board[pos] > board[pos+1] && !((pos+2) > (ARRAY_SIZE-1) ))
        {
            return board[pos+1] + jumpIt( board, pos+2 );
        }
    }
}