Not understanding this Recursion

Limewire

Hello, I am trying to update this array of numbers (scoreboard) by inserting in a new number, then shuffling the numbers down accordingly. i.e if i scored 210 and the scoreboard looked like this: 100,80,60,40,20 then this would change it to this: 210,100,80,60,40

The array of scoreboard goes from 0 -> 4 (0 being 1st place, 4 being last place) the numbers in scoreboard looks like this: 100[0],80[1],60[2],40[3],20[4]

void Save(int s){ int temp; for(int i = 0; i <=4; i ++){ if(s > scoreboard[i]){ if(i == 4) scoreboard[i] = s; else { temp = scoreboard[i]; scoreboard[i] = s; Save(temp); } } print(scoreboard[i] + " " + i); }

I do realise there is a curly bracket missing to finish the method, it's just commented out code.

Many Thanks!

TfGuy44

Let's take your example and run with it!

The existing scoreboard is [100,80,60,40,20]. Someone scores a 210! Nice! Let's save that score.

First step, we have a new variable called temp. We're not using it for anything yet but it's there.

Then we're going to do a loop. The looping variable is i, and it starts at 0 and keeps looping as long as i is <= 4. So i will take the values of 0, 1, 2, 3, 4, in turn.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, yes. 210 > 100

Next, we do another check. Is this the fourth position? That is, is i == 4? No. This time in the loop, i is 0. So we step into the else block.

Now we're using that variable temp. We use it to save the score in the i'th position. This is the value 100 in this example.

Then we put the new high score in that position. So now we have this state:

scoreboard := [210,80,60,40,20] temp := 100 i := 0

But we can't just throw out that highscore of 100! So we have to save it in the score board! Ah ha! We have a function that does that - it's this function! But we can call it from itself anyway. This is the recursion. We save the score of 100.

---

The existing scoreboard is [210,80,60,40,20]. Someone scores a 100! Nice! Let's save that score.

First step, we have a new variable called temp. We're not using it for anything yet but it's there.

Then we're going to do a loop. The looping variable is i, and it starts at 0 and keeps looping as long as i is <= 4. So i will take the values of 0, 1, 2, 3, 4, in turn.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 210 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 1.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, yes. 100 > 80

Next, we do another check. Is this the fourth position? That is, is i == 4? No. This time in the loop, i is 1. So we step into the else block.

Now we're using that variable temp. We use it to save the score in the i'th position. This is the value 80 in this example.

Then we put the new high score in that position. So now we have this state:

scoreboard := [210,100,60,40,20] temp := 80 i := 1

But we can't just throw out that highscore of 80! So we have to save it in the score board! Ah ha! We have a function that does that - it's this function! But we can call it from itself anyway. This is the recursion. We save the score of 80.

---

The existing scoreboard is [210,100,60,40,20]. Someone scores a 80! Nice! Let's save that score.

First step, we have a new variable called temp. We're not using it for anything yet but it's there.

Then we're going to do a loop. The looping variable is i, and it starts at 0 and keeps looping as long as i is <= 4. So i will take the values of 0, 1, 2, 3, 4, in turn.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 210 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 1.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 100 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 2.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, yes. 80 > 60

Next, we do another check. Is this the fourth position? That is, is i == 4? No. This time in the loop, i is 2. So we step into the else block.

Now we're using that variable temp. We use it to save the score in the i'th position. This is the value 60 in this example.

Then we put the new high score in that position. So now we have this state:

scoreboard := [210,100,80,40,20] temp := 60 i := 2

But we can't just throw out that highscore of 60! So we have to save it in the score board! Ah ha! We have a function that does that - it's this function! But we can call it from itself anyway. This is the recursion. We save the score of 60.

---

The same thing happens with 40, just one more position down.

scoreboard := [210,100,80,60,20] temp := 40 i := 3

We still have to save the value of 40, because we can't throw this one out either.

---

The existing scoreboard is [210,100,60,60,20]. Someone scores a 40! Nice! Let's save that score.

First step, we have a new variable called temp. We're not using it for anything yet but it's there.

Then we're going to do a loop. The looping variable is i, and it starts at 0 and keeps looping as long as i is <= 4. So i will take the values of 0, 1, 2, 3, 4, in turn.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 210 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 1.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 100 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 2.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 80 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 3.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, no. 60 is still greater. So there's nothing to do when the loop runs this time. We move on to the next value of i, which is 4.

Now we're checking a condition. Is the new score, s, greater than the score in position i in the scoreboard? Well, yes. 40 > 20

Next, we do another check. Is this the fourth position? That is, is i == 4? YES! This time in the loop, i is 4. So we save this score in he 4th position. And that's all we do this time. We don't need to worry about dealing with the score that was there - the 20 - because it is the lowest score on the scoreboard, so it just gets removed.

So now we have this state:

scoreboard := [210,100,80,40,20] temp := wasn't used. i := 4

So far so good.

Sadly everything goes to hell from here. So now we print out the scores... Or do we? More on this later.

---

Now that the score of 40 is saved, where were we? Or right. We are in save(60) and had just called save(40).

This is the state now:

s := 60 scoreboard := [210,100,80,60,40] temp := 40 i := 3

Our loop continues. i is4, and 60 > 40, so we put 60 in there. Cussword, this isn't right!

We should have bailed out right after we called save(40). In short, we should just return now...

Chrisir

It could be a sorting algorithm but I think it’s fairly bad

I think it either inserts at the end or swaps the values, pushing the older and smaller value further down

TfGuy44

Here's a working example that uses two functions, one which you can call and one that does the recursive adding.

int[] scoreboard = {100,80,60,40,20};

void setup(){
  size(400,400);
  new_score(210);
}

void draw(){};


void new_score(int s){
  save_rec(s);
  for(int i = 0; i < scoreboard.length; i++){
    println( "" + (i+1) + ": " + scoreboard[i] );
  }
}

void save_rec(int s){
  int temp;
  for(int i = 0; i <=4; i++){
    if(s > scoreboard[i]){
      if(i == 4) {
        scoreboard[i] = s;
      } else {
        temp = scoreboard[i];
        scoreboard[i] = s;
        save_rec(temp);
        return;
      }
    }
  }
}

Notice that I moved the printing to the function that isn't recursive, and that the recursive functions are now done (that is, they call return) immediately after they take the recursive step.

Limewire

Hello TfGuy44!

That really helped me see what was happening with my code, but the code that you have given me doesn't seem to fix my problem either. I have the have the same inputs and it seems to overwrite all of the data with the new score

i.e 100,80,60,40,20, -> 210,210,210,210,210,

I'm not too sure what is happening, but my guess is the return function is not returning the compiler to the previous method. It overwrites the number it is greater than in the string and pushes the other numbers to the end of the stack until they get overwritten.

Thanks for the help!

TfGuy44

This code:

int[] scoreboard = {100,80,60,40,20};

void setup(){
  size(400,400);
  new_score(210);
}

void draw(){};


void new_score(int s){
  save_rec(s);
  for(int i = 0; i < scoreboard.length; i++){
    println( "" + (i+1) + ": " + scoreboard[i] );
  }
}

void save_rec(int s){
  int temp;
  for(int i = 0; i <=4; i++){
    if(s > scoreboard[i]){
      if(i == 4) {
        scoreboard[i] = s;
      } else {
        temp = scoreboard[i];
        scoreboard[i] = s;
        save_rec(temp);
        return;
      }
    }
  }
}

As is, produces this output for me:

1: 210
2: 100
3: 80
4: 60
5: 40

Which is correct. Without seeing how you are trying to do it in your code, I have no idea what is wrong with your code. Is it possible that you are calling save(210)more than once? Are you returning at the right place? I have no idea. Post your code.

Limewire

It worked! Thank you!

The method that it was being called in was being called multiple times when the game ended. I used a very crude method of using a Boolean to make sure it was only being called once but it worked! I used it to save to a file so now i can have a permanent table for the game!

Cheers mate!

koogs

There's absolutely no need for recursion here. And if you use the right container rather than an array then sorting will be automatic.