Help: This sketch is attempting too much recursion, but there isn't much recursion

Processing Libraries
1

Hello everyone!

I have a problem with my code, and I’m not sure where to start, as the error doesn’t give me much information (or rather, I don’t agree with the error).

I have a sketch where I’m using thread() to create a new thread to play back morse code via a recursive function to get the timing right. The code works through an array of morse characters, plays back the current one, then deletes it and calls itself after a defined break to continue working through the queue. If there are no characters in the queue, it waits for 100ms, then tries again. That’s the recursion part.

The problem is, after 4330 - 4340 recursive calls (tried 8 times with different delays, always within this range) the code crashes with “StackOverflowError: This sketch is attempting too much recursion”. There are maybe 8 calls per second, but I tried it with both 1000 calls per second and 4 calls per second, the error always appears after ~4330 calls. My memory isn’t full and the cpu load is ~0%. Which leads me to think that there is some sort of internal limit on how many recursive calls you can have?

I used thread() and recursion because it seemed elegant and efficient, but now I’m stuck at this error and not sure how to solve this. My code needs to run stable over prolonged periods of time, and I’m glad I caught this. Can I somehow “clear the recursion stack”? Start it over? The function does not depend on any parameters or its previous function call (outside of variable assignments).

I recreated the sketch without functionality, just the recursive calls, and now the error message pops up after about 9000 iterations… which is still no good.

Here is the non-functionality code which showcases the problem:

int recursion_count = 0;

void setup () {
  //size(600, 400);
  // Set up the morse playback thread
  thread("morsePlayback");
}

void morsePlayback() {
  
  recursion_count++;
  println(recursion_count);
  
  // True for debug reasons
  if(0 == 0) {
    delay(2);
    morsePlayback();
    return;
  }

  // Other functionality, then recursive call
  morsePlayback();
  return;
}

The original code, crashing after ~4340 calls can be found here.

I hope my question became clear, if not I’ll try to sum it up again: My code crashes after X recursive calls, even though they are spread far apart. Why is that and how I can prevent that?

Thank you for your time already, if I can provide further information please ask!

2

The problem you are trying to solve should not use recursion, you need to find another way to do it.

When you call a method such as morsePlayback() the computer will create a stack frame and this structure is used to hold any parameters, local variables and most importantly the memory address for the program to continue when the function finishs.

The stack frame is placed on the program stack and stays there until the function code ends. If inside that function it calls another function a new stack frame is created. Your recursive function is dangerous because recursion never stops, none of the functions called ever end so none of the stack frames are removed.

It doesn’t matter how much memroy you reserve because the amount set aside for the program stack is finite and you will eventually use it all and your sketch will crash.

2 Likes
3

Have you considered using a queue data structure instead – or a cursor? If you want to process things in your thread for a long time, so long as a condition is met, and you don’t want to constantly start new threads, then use while, and break out as appropriate.

4

Hi quark, thanks for your reply! Now I see why the code is crashing, thanks for the explanation :slight_smile:

I’ve found it difficult to do anything precise with processing, as (to my understanding) the draw-loop is the only thing constantly running, and at 30 / 60 fps that’s only precise up to 16 ms. Do you know a better way to do something precise without using recursion in a separate thread? I guess I could start a new thread each time the morse playback is called… and when it’s finished I set a variable and only then the next thread starts. It seems a bit overcomplicated, so maybe I’m missing something obvious here?

Thanks for your help!

5

Hi Jeremy, thank you for your reply! I haven’t worked with cursors yet, but it sounds like it would just be an index to tell the queue which item should be processed? I figured I’d run out of memory at some point if I don’t delete items as they’re done processing, that’s why I’m just deleting them and then calling the next one.

Could you elaborate on the “break out as appropriate”? Because that sounds like a timing thing, which is exactly why I used recursion in a separate thread the first time: the ability to delay() as needed.

Maybe I should use a very high framerate and then use the draw-loop? Since there is not much going on computing-wise, it shouldn’t be too demanding on the cpu… but it seems like a sub-optimal solution. :confused: I don’t know, I feel like it’s a lot of sidestepping to solve a pretty simple issue?

6

I would suggest using a thread safe queue data structure. The main sketch thread would be responsible for putting new characters onto the queue and a single infinite thread would read the queue and play the morse.

There would be no recursion at all. :grinning:

A thread safe queue

1 Like
7

Hi quark, thanks for the recommendation. I’ve never heard of these (not a java dev), but the concept seems simple enough! :slight_smile:

My question now would be: How do I create a single infinite thread? Is it just a thread() call to a function with while(queuelength > 1) { ... } with some delays sprinkled in to stop it from running thousand times per second?

Edit: no wait, if there is no while(true) the thread would finish at some point… So I think I just use delays?

8

The following sketch demonstrates what I mean. Hopefully you should be able to follow the code but ask it you need any explanation.
When you click the mouse a word is split into its characters and added to a queue. An infinite thread reads the characters one by one and displays them in the console pane.

import java.util.concurrent.*;

String s = "Mary had a little lamb " +
  "its fleece as white as snow " +
  "and every where Mary went " + 
  "the lamb was sure to go";
int wn = 0;

String[] words;
String sent = "";

ConcurrentLinkedQueue<MorseCharacter> queue =
  new ConcurrentLinkedQueue<MorseCharacter>();

void setup() {
  size(640, 480);
  textSize(40);
  words = s.split(" ");
  println("##########################");
  thread("play_morse");
}

void draw() {
  background(0);
  fill(255);
  text(sent, 0, 0, width, height);
}

void mouseClicked() {
  addWordToQueue();
}

void addWordToQueue() {
  if (wn < words.length) {
    String w = words[wn] + " ";
    sent += w;
    for (int i = 0; i < w.length(); i++) {
      char c = w.charAt(i);
      MorseCharacter mc = new MorseCharacter(c);
      queue.add(mc);
    }
    wn++;
  }
}

public void play_morse() {
  // infinite loop will end when application ends
  while (true) { 
    while (queue.isEmpty()) {
      // Don't hog the CPU if the queue is empty
      delay(100);
    }
    MorseCharacter mc = queue.poll();
    mc.play();
  }
}

class MorseCharacter {

  char c;

  public MorseCharacter(char c) {
    this.c = c;
  }

  public void play() {
    if (c == ' ') {
      println();
    } else {
      print(c);
    }
    delay(1000); // wait a second to simulate time to play morse
  }
}
1 Like
9

Hi quark, this is perfectly understandable! I’ll try to implement this approach for my code first thing tomorrow. :slight_smile: Thank you for your time, and the example code!

10

Rather than directly use delay() itself, you could instead use this very simple “Countdown.java” library:

For each delay duration, create a new instance of Countdown.

Then call start() over the Countdown instance having the desired delay duration.

And then keep pooling its done field. When it becomes true, it means that delay duration has finished.

Notice we can call start() to re-initiate the delay duration from a Countdown instance as many times as we wish.