Recursion issue with my code?

Projects Programming
1

Hi all. I'm an Arduino and programming beginner. I'm working on a reaction game where I've got 4 buttons, each next to an LED. When the LED lights you press the corresponding button to "score" then another LED lights up. Sometimes, the same LED lights up multiple times in a row and I wanted to stop that behavior so I added a condition to check...

int pickButton() {
  nextButton = random(1, 5);
  if (nextButton == previousButton) {
    //debugging
    repeat++;
    Serial.print("Duplicate -- prev: ");
    Serial.print(previousButton);
    Serial.print(", next: ");
    Serial.print(nextButton);
    Serial.print(", repeats: ");
    Serial.println(repeat);
    pickButton();
  } else {
    repeat = 0;
    previousButton = nextButton;
    return nextButton;
  }
}

For some reason, my game hangs when the nextButton == previousButton condition is met and the pickButton() function is recursively called. The LED lights up and pressing the corresponding button does nothing.

When I comment out the recursive call and just return the duplicate result it works fine:

int pickButton() {
  nextButton = random(1, 5);
  if (nextButton == previousButton) {
    //debugging
    repeat++;
    Serial.print("Duplicate -- prev: ");
    Serial.print(previousButton);
    Serial.print(", next: ");
    Serial.print(nextButton);
    Serial.print(", repeats: ");
    Serial.println(repeat);
    //pickButton();
    return nextButton;
  } else {
    repeat = 0;
    previousButton = nextButton;
    return nextButton;
  }
}

I assume there's some kind of basic logic that's staring me in the face. Would appreciate someone pointing it out. Thanks!

Edited to add: The Arduino itself doesn't hang. That was a bad choice of word. I have the game set to a time limit. Once the time limit is reached, the game ends as it's supposed to. It just becomes unresponsive.

2

With the first example (recursive), you do not return any value from the “outer” pickButton, if there is equal value. (The value returned from th “inside” call is discarded, as it is not used)

1 Like
3

Thank you! My thinking was that if the inside call resulted in a non-duplicate it would just "break" out of the recursion. I added 'return nextButton;' after the recursive function call and it's working properly now. Thanks again!

4

While it's an interesting concept to learn about for a beginner, it's generally best to avoid using recursion on most Arduino, which for many models have very limited memory. Recursion can result in running out of memory, which causes all kinds of strange side-effects that can be very puzzling and difficult to debug.

Rarely, recursion can be the best and simplest way to code an algorithm, but usually it is easy to avoid the need to use recursion by using a loop for example.

In your case, it's easy to avoid.

int pickButton() {
  while(true) {
    nextButton = random(1, 5);
    if (nextButton != previousButton) break;
    //debugging
    repeat++;
    Serial.print("Duplicate -- prev: ");
    Serial.print(previousButton);
    Serial.print(", next: ");
    Serial.print(nextButton);
    Serial.print(", repeats: ");
    Serial.println(repeat);
  }
  repeat = 0;
  previousButton = nextButton;
  return nextButton;
}

Even more simply without the debugging

int pickButton() {
  do {
    nextButton = random(1, 5);
  while (nextButton == previousButton);
  previousButton = nextButton;
  return nextButton;
}
1 Like
5

Hi Paul, thanks for that! Even better! I wasn't familiar with do...while.

The reason I implemented this was sometimes the same button would light up 4, 5 times in a row. After implementing your solution I decided I didn't mind if the the same button lit up twice so I used this:

int pickButton() {
  nextButton = random(1, 5);
  if (nextButton == previousButton) {
    repeatedButton++;
  }
  do {
    nextButton = random(1, 5);
    repeatedButton = 0;
  }
  while (repeatedButton > 0);
  previousButton = nextButton;
  return nextButton;
}

Thanks again!

6

That code need re-thinking. I'll give you some more tips:

  • The code lines inside a do-while loop always execute at least once, so even if your first selected random number is not the same as the previous random number, it will immediately get replaced with a second random number, which does not get checked.
  • Your do-while loop can only ever get executed once because of how it is controlled by the value repeatedButton.
  • As a result, the code lines inside your do-while loop always get executed exactly once. So there is no point having that loop.
1 Like
7

then just extend the solution offered by @PaulRB

You'll need to add a previousPreviousButton global variable alongside your existing ones:

int previousButton = 0;
int previousPreviousButton = 0;

and the function becomes

int pickButton() {
  do {
    nextButton = random(1, 5);
  } while (nextButton == previousButton && nextButton == previousPreviousButton);
  previousPreviousButton = previousButton;
  previousButton = nextButton;
  return nextButton;
}

This way the loop only rejects a button if it matches both the last button AND the one before that.

side note: if your buttons are numbered from 1 to 4, you don't need an int to represent that, a byte will be enough.

1 Like
8

Paul, Jackson -- thanks to you both for taking the time to help.

Paul, when you first suggested do...while I looked it up on W3Schools. It seemed to be working properly so I was happy. I looked it up again after your last reply and saw that, in the 4 sentences on the page, it mentions twice that the code is always executed once. Durrr...

W3Schools let's you try out code so I've been playing in their editor instead of waiting for code to compile in the Arduino IDE. I came up with this:

#include <iostream>
#include <cstdlib>
using namespace std;

int previousButton;
int nextButton;
int timesRepeated = 0;
int pickButton();

int main() {
	for (int i = 0; i < 500; i++) {
    	cout << i + 1 << ". " << pickButton() << endl;
        }
	return 0;
}

int pickButton() {
	nextButton = (rand() % (4 - 1 + 1)) + 1;
    if (nextButton == previousButton) {
    	timesRepeated++;
        cout << "*"; //debugging
    } else { timesRepeated = 0; }
    while (timesRepeated > 1) {
    	cout << nextButton << " repeated again. Replace with "; //debugging
    	nextButton = (rand() % (4 - 1 + 1)) + 1;
        if (nextButton == previousButton) {
        	timesRepeated++;
        } else { timesRepeated = 0; }
    }
    previousButton = nextButton;
    return nextButton;
}

Hopefully, this is proper now.

Jackson, thanks for suggesting to replace 'int' with 'byte'. That makes sense. I'm using int in my example here though because the W3Schools editor doesn't support the byte type. I'm keeping the (renamed) 'timesRepeated' variable instead of previousPreviousButton because it gives me the flexibility to change my mind later, say, if I want to allow the same button to repeat 3 times.

Edited to add: Paul, thanks for presenting your last reply in a way that made me think about the problem at hand and learn.

Edited again to add: I realized I don't need to increment timesRepeated again in the while loop so I've replaced the if...then with:

        if (nextButton != previousButton) {
        	timesRepeated = 0;
        }
9

It's better than your previous attempts, but it is still longer and more complex than it needs to be and contains repeated code.

Need more tips?

  • Try to avoid having repeated code. It's bad practice for reasons that will become clear as your level of experience grows
  • If a piece of code needs to run zero or one times, use an if statement
  • If a piece of code needs to run zero, one or more times and you know in advance how many times, use a for-loop
  • If a piece of code needs to run zero, one or more times and you don't know in advance how many, use a while-loop
  • If a piece of code needs to run at least once or more times and you don't know in advance how many, use a do-while loop

In your code, you need to choose a new button randomly, at least once and possibly several times, and you don't know in advance how many times.

1 Like
10

This feels weird - doesn’t it ?

You would use uint8_t as the type then - but not in your case. A byte was fine because the value was small - less than what a byte can safely hold (<=4 for the button number) but in the present case you have no clue how long it will take to get a non repeated number so you can accumulate a large number of tries - possibly more than 255 and if you have only a byte then 255+1=256 which be represented as 0 in a byte and fail your test.

I applaud your attempt at doing it your way - that’s how you learn - but at the same time don’t fall into the trap of building wrong habits, learn from code snippets and best practices. @PaulRB named a few for decision making on iterative statements.

2 Likes
13

As far as I can remember, when writing Arduino code over the last 10 years, I used recursion only once.

I was writing a connect-4 game which played against a human opponent. It evaluated every possible move it could make (dropping a counter into one of 7 columns), given the current state of the board, and chose the best. But that would not be enough to beat a human opponent. So it then evaluated every possible move it's opponent could make as their next move, then every possible move it could make in response, and every possible move it's opponent could make, and so on, up to about 4 moves ahead. This made it very difficult to beat! But I used recursion to explore all the possible sequences of moves the Arduino and the human opponent could make.

14

When computing a factorial, which one is more natural to use -- recursion or iteration?”

15

I think it probably feels more natural to use recursion, because that's how factorial is often mathematically defined. But more efficient to iterate!

Recursion:

unsigned long factorial(unsigned long n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Iteration:

unsigned long factorial(unsigned long n) {
  unsigned long result = 1;
  while (n > 1) result *= n--;
  return result;
}

Both untested!

Oops, I just used a while loop where the number of iterations was known in advance! Well, it's a rule, not a law...

1 Like
16

You could add to the rule that the traditional for is preferred when an index is useful otherwise a while can do the job

To your point about the game - it’s basically the idea of the minimax algorithm which evaluates a game tree where each position leads to multiple possible future positions until a terminal state is reached. Recursion is well suited because the same evaluation procedure is applied repeatedly to each deeper level of the tree: a function evaluates a position by calling itself on all child positions, then returns either the maximum or minimum value depending on which player’s turn it is. This directly mirrors the hierarchical structure of the game tree and allows the algorithm to propagate scores from terminal states back up to the root in a natural and concise way.

1 Like
17

see no need for recursion
(millis() didn't work without using setup/loop())

const int PinLed [] = { 12, 11, 10 };
const int PinBut [] = { A1, A2, A3 };
const int NLed      = sizeof(PinBut)/sizeof(int);

enum { LedOff = HIGH, LedOn = LOW };

const unsigned long MsecTest = 1000;
const unsigned long MsecIdle = 1000;
unsigned long msecPeriod     = MsecIdle;
unsigned long msec0;
unsigned long msec;

const char *StrStim [] = { "None", "Timer", "But" };
enum { None, Timer, But };

const char *StrState [] = {"Idle", "Test" };
enum { Idle, Test}; 
int state = Idle;

const int NoBut = -1;
int testBut;

char s [90];

// -----------------------------------------------------------------------------
int
getBut ()
{
    for (int n = 0; n < NLed; n++)  {
        if (LOW == digitalRead (PinBut [n]))
            return n;
    }
    return NoBut;
}

// -----------------------------------------------------------------------------
void
ledAll (
    int onOff)
{
    for (int n = 0; n < NLed; n++)
       digitalWrite (PinLed [n], onOff);
}

// -----------------------------------------------------------------------------
int
selectLed ()
{
    int n = random(0, NLed);
    digitalWrite (PinLed [n], LedOn);
    return n;
}

// -----------------------------------------------------------------------------

void sm (
    int stim,
    int but )
{

    if (NoBut != stim)  {
        sprintf (s, "sm: state %s, stim %s, led %d,  %8lu ms", 
                        StrState [state], StrStim [stim], testBut, msec);
        Serial.println (s);
    }

    switch (state) {
    case Idle:
        if (Timer == stim)  {
            state      = Test;
            msec0      = msec;
            msecPeriod = MsecTest;

            ledAll (LedOff);
            testBut    = selectLed();
            digitalWrite (PinLed [testBut], LedOn);
        }
        break;

    case Test:
        if (Timer == stim)  {
            state      = Idle;
            msec0      = msec;
            msecPeriod = MsecIdle;
            ledAll (LedOn);
        }
        else if (But == stim)  {
            state      = Idle;
            msec0      = msec;
            msecPeriod = MsecIdle;

            if (testBut == but)
                digitalWrite (PinLed [testBut], LedOff);
            else  {
                ledAll (LedOn);
            }
        }
        break;
    }
}

// -----------------------------------------------------------------------------
void loop ()
{
    msec = millis ();
    if (msec - msec0 >= msecPeriod)  {
        msec0 = msec;
        sm (Timer, 0);
    }

    int but = getBut ();
    if (NoBut != but)
        sm (But, but);
}

// -----------------------------------------------------------------------------
void setup ()
{
    Serial.begin (9600);

    for (int n = 0; n < NLed; n++)  {
        pinMode (PinBut [n], INPUT_PULLUP);
        pinMode (PinLed [n], OUTPUT);
        digitalWrite (PinLed [n], LedOff);
    }
}
1 Like
18

LOL.

Good thing I was between sips of my beverage.

a7

2 Likes
19

Thanks, I appreciate the additional tips and how you break done how to choose the right conditional.

Yeah, I was giving that repeated code the side eye but didn't want to think about it anymore after I finished it. I worked it out for a bit and I think this is the version. Well, it's definitely better than the last one lol.

#include <iostream>
#include <cstdlib>
using namespace std;

int previousButton;
int nextButton;
int timesRepeated = 0;
int maxRepeats = 1;
int pickButton();

int main() {
	for (int i = 0; i < 500; i++) {
    	cout << i + 1 << ". " << pickButton() << endl;
        }
	return 0;
}

int pickButton() {
	do {
    	nextButton = (rand() % (4 - 1 + 1)) + 1;
        if (nextButton == previousButton) {
        	timesRepeated++;
        } else { timesRepeated = 0; }
       }
    while ( timesRepeated > maxRepeats );
    
    previousButton = nextButton;
    return nextButton;
}

Thanks so much for your help. As soon as I finished this, I was struck at how much more elegant (and efficient) it is.

20

If you want you can use the ternary operator and (useless but fun) assign the value as you return

int pickButton() {
  do {
    nextButton = rand() % 4 + 1;
    timesRepeated = (nextButton == previousButton) ? timesRepeated + 1 : 0;
  } while (timesRepeated > maxRepeats);
  return previousButton = nextButton;
}
1 Like
21

Yeah. Looking at non-Arduino cpp code versus Arduino cpp code goes whoosh over my head and makes me feel anxious and cross eyed, lol.

uint8_t isn't supported in W3School's editor either, but I will implement it in my Arduino code. Thanks for bringing this to my attention. Memory management isn't something I need to worry about now with my little programs but it's going to save me down the road. Better to learn better practices early. Thanks again, Jackson!

22

Thanks for that. At first glance my beginner brain is going :skull: but I'll dig into it to try to understand. I appreciate the example of using an array to store the pin values for the leds and buttons. I'd considered that but couldn't quite wrap my head around it at the time.