Recursive Function help/ Vector

[lew13]

Oh, yeah :P thanks.

[lew13]

I think my base case needs something else now. Because it prints 0 and nothing else, so I think that once my base case is reached it just returns 0 instead of the actual value.

[lew13]

So it is printing the value at index 1 which I am positive is because of my base case. How would I make it so that it returns the value to to the cost and then prints the cost when I call it in my main? Line 21

#include <iostream>
#include <vector>
#include<string>
#include<sstream>
#include<algorithm>

using namespace std;


int cost (vector<int> gameBoard, int index)
        {
            if (index > 1)
            {
                int costOne = cost(gameBoard,(index-1));
                int costTwo = cost(gameBoard,(index-2));

                return min(costOne,costTwo) + gameBoard[index];
            }

            else if (index == 0 || index == 1)
                return gameBoard[index];
        }

int main()
{
    char goAgain;

	do{
    int k, index(0);
    vector<int> gameBoard;
    string input;

    cout << "Please enter the numbers of a game board on one line, separating numbers by spaces,then press the Enter key." << endl ;

    getline (cin, input);std:: cout <<endl;

    stringstream inputStringStream(input);

    while (inputStringStream >> k)
        gameBoard.push_back(k);

    int cost (vector<int>gameBoard, int index);

    cout<<"For the game board" << endl << endl;
    for (int i = 0; i < gameBoard.size(); i++)
        cout << gameBoard[i]<< ' ';

    cout<< cost(gameBoard,index);

	cout <<endl<<endl<< "Would you like to enter a new Game Board (Y/N)?" << endl;
	cin >> goAgain;

    cin.ignore(9999, '\n');

	}while(goAgain == 'Y'|| goAgain == 'y');

 return 0;
}

[fg109]

lew13 wrote:

How would I make it so that it returns the value to to the cost and then prints the cost when I call it in my main?

I'm not sure I understand what you're asking, but it doesn't sound like something you need a recursive function for.

Can you give an example for input and output?

[lew13]

Well I have the recursion function down I think that my call to the function in my main is messed up I'm wanting something like

Input: 0 1 56 2 45 3

The recursion would either jump one or two spaces but it would try to take the most "cost efficient" route. So 0+1+2+3 so I would print out 6. Does that make sense? I am just having trouble getting it to print the correct output.

[fg109]

OK... so it's a game where you provide a list of numbers, and the player has to reach the end of the list. The player can only move 1 or 2 "spaces" at a time. Each number the player lands on has its value added to some "score". Like in golf, you want to reach the goal with the lowest "score" possible.

Is that correct?

[lew13]

Yes exactly, the only rules are it has to use recursion and it has to be a vector. Which I'm pretty sure I have right for the most part. I just need the correct output and I dont know if it is from my function prototype or in my cout statement. I think the function prototype is confusing the parameter index, but I am not sure.

[fg109]

There is nothing wrong with the function prototype (except that maybe you should pass the vector by reference instead of by value). The problem is with the code inside of it. I'm not sure how I can help you fix it without just giving you the code, but I'll try.

int cost (vector<int> gameBoard, int index)
        {
            if (index > 1)
            {
                int costOne = cost(gameBoard,(index-1));
                int costTwo = cost(gameBoard,(index-2));

                return min(costOne,costTwo) + gameBoard[index];
            }

            else if (index == 0 || index == 1)
                return gameBoard[index];
        }

So your function stops recursion when index == 0 || index == 1. But what about the rules we just talked about? The player starts from the beginning of the list. That means index == 0 in the first call of the function. What does the code you wrote mean in light of that? It means stopping the "game" before we've even begun.

Instead of using that as a condition, use the condition for the end of the game... which is when the player reaches the end of the list, right? Think about how that would be in code.

Now in light of all that, what do you think should change about these lines?

            if (index > 1)
            {
                int costOne = cost(gameBoard,(index-1));
                int costTwo = cost(gameBoard,(index-2));

You also need to think about what you actually return from the function.

^Those are actually just intermediate steps, because the whole way you're going about this is wrong.

You're only looking at 2 numbers at a time. But what if the numbers you're looking at are

0 1 50 100 1

or even

0 20 50 40 40 100 1

Looking at only 2 numbers in those cases will not give you the most cost-efficient route.

[lew13]

Man I honestly don't know what to do. You're telling me all my code is wrong and my instructor is telling me my functions are correct I just need to change the cout statement so it returns a different index, and instead of helping it's just making it worse. I'll look at it after work and see what I can make of it, it's due tonight and I'm about done with it all.

[fg109]

Forget about what I said of your code only looking at two numbers at a time. Once I thought of how to find the most cost-efficient route, that's the same thing I came up with (assuming that you don't need to print out the actual steps you take).

I am not sure if I am going to be on later so I'll just give you the correct code. If you don't understand it, leave a post and I'll try to explain it tomorrow.

//gameBoard is passed as a reference, so you don't need to keep making new vectors in recursive calls
int cost (vector<int> &gameBoard, int index)
{
	//first create a break point for when the recursion should end
	if (index == gameBoard.size() - 1) //index is the last element in the vector, should only be the case if size == 1
		return gameBoard[index]; //no recursive calls, just return the value of the last element
	else if (index == gameBoard.size() - 2) //next to last element
		return gameBoard[index] + gameBoard[index + 1]; //there's only one possible move from this point
	else if (index == gameBoard.size() - 3) //third to last element
		return gameBoard[index] + gameBoard[index + 2]; //obviously finishing in 2 moves is better than 3 moves
	
	//from this point, we know that there are at least 3 elements after the current index
	int costOne = cost(gameBoard, index + 1);
	int costTwo = cost(gameBoard, index + 2);
	return min(costOne,costTwo) + gameBoard[index];
}

[lew13]

I understand what you are trying to do with the base case, however, even if I implement your function it still doesn't act properly all the time, so the problem has to be elsewhere. I am really just trying to figure out what to type into my cout statement to get it to work at this point. I have tried so many different statements and nothing does the trick.

[fg109]

It'll work with the code you last posted if you delete line 42 of the code in that post.

[lew13]

I got it man it was just in my cout statement. Unfortunately I didn't figure it out until after it was due, but thanks for all your help man.