Concepts / Recursion in Threads

Recursion in Threads

A Finish button cannot directly stop a recursive algorithm, because the click can arrive many levels deep in the recursion and all pending calls must return first.

  • Programming
Interactive lab

Try it: The Call Stack

How the call stack keeps track of function calls: each call pushes a frame with its own arguments and local variables, and each return pops it.

How it works

  1. Calling a function pushes a new frame on top of the stack; the caller pauses.
  2. The frame holds that call's parameters and local variables.
  3. When the function returns, its frame is popped and the return value goes back to the paused caller.
  4. A recursive function pushes one frame per call until the base case, then the frames unwind in reverse order.

Default run (17 steps): Program starts: main is about to call factorial(4). … The stack is empty again. Result: 24. Deepest point: 4 frames, 4 calls in total.

Educational simulation

Loading the simulation…

Why a Finish Click Cannot Stop Recursion Directly

Many programs let a user cancel a long-running task. In a graphical sorting demo, a Finish button should abort the sort and terminate the thread that is running it. This sounds simple, but a recursive algorithm makes it harder than it first appears. The problem is timing. The Finish button can be clicked at any moment, including when the algorithm is many levels down in its recursion.

A recursive algorithm is not sitting in one simple loop that can be broken out of. It is a stack of method calls, each waiting on the one it made. When the click arrives, the thread is in the middle of several nested calls, and each of those calls is still pending. The source states the consequence directly: before the thread can terminate, all of those recursive method calls must return. A button handler cannot simply reach down into the stack and remove the deepest call.

quicksort call 1waiting on call 2quicksort call 2waiting on call 3quicksort call 3waiting on call 4quicksort call 4deepest, running when clickarrivescallscallscalls
When the click arrives, which nested calls are still pending on the stack, and why must they all return before the thread can stop?

A Volatile Flag as a Stop Signal

The solution starts with a signal rather than an interruption. Pressing the Finish button sets the value of a boolean variable named running to false. That change is the message to the thread: it should terminate. The thread does not get interrupted directly by the button. Instead, the thread keeps checking the flag at safe points in its work.

The flag is declared volatile. In this demo, the button handler runs on the UI thread and writes the flag, while the worker thread reads it. The volatile declaration is what lets the worker thread see that change, and the source describes this flag as a stop signal that works without a lock.

Finish buttonUI thread handlerrunning = falsevolatile booleandelay() reads flagworker threadThreadTerminationExceptionthrown when flag is falsewritesread byif false
How does the button handler on the UI thread write the flag, and how does the worker thread see that change without a lock?
Key point

The flag itself does not stop anything. It only carries the request. Something must read the flag and act on it, and in this demo that job belongs to the delay() method, which the animation calls between steps.

Where the Abort Request Is Read

The delay() method is where the abort request is read. The demo's delay() method checks the running flag twice, once before the sleep and once after. Each check has its own job, and the two together cover the timing problem described above.

  1. 1
    First check, before Thread.sleep(): if running is already false, the thread stops before it starts a new pause. This prevents a thread from beginning a new pause after an abort has already been requested.
  2. 2
    Thread.sleep() runs: the thread pauses for the delay. The flag may change while the thread is asleep, because the button handler runs on another thread.
  3. 3
    Second check, after Thread.sleep(): if running is now false, delay() throws ThreadTerminationException. This handles the case the source explicitly describes, where the value may have changed during the sleep.

What do you think happens?

If the Finish button sets running to false, does the worker thread stop at that instant?

  • Yes, the thread stops immediately when the button is clicked

  • No, the flag only carries the request until delay() reads it

Reveal answer
Answer:

No, the flag only carries the request until delay() reads it

Setting the flag changes a value and nothing more. The thread keeps running until it reaches a point where the flag is checked, which in this demo is inside delay().

Unwinding Recursion with an Exception

Once the flag is false, the thread needs every pending recursive call to return. The demo uses an exception for this. QuickSortThreadDemo defines a new exception class, ThreadTerminationException, for this purpose. When delay() sees that running is false, it throws that exception.

An exception propagates up through the chain of method calls. Because each recursive call is waiting on the one it made, the exception passes from the deepest call back through each caller in turn. This unwinds the recursion, and eventually the animation thread itself terminates. The exception does the work that a normal return would otherwise need to do at every level.

delay() throwsdeepest callquicksort call 3exception passes throughquicksort call 2exception passes throughquicksort call 1exception passes throughthread terminatesanimation thread endspropagatespropagatespropagatesends thread
After an exception is thrown at the deepest level, how does control pass back up through each recursive frame until the thread terminates?

Tracing a Click Through a Three-Level Recursion

Worked example

Abort during the third recursive level

A recursive sort runs in a worker thread. It is three calls deep when the user clicks Finish during a pause. Trace what happens from the click until the thread terminates. Assume the flag is checked in delay() as in the demo.

  1. 1
    Click arrives

    The Finish handler on the UI thread sets running to false. The worker thread is inside its third call and is currently in Thread.sleep() inside delay().

  2. 2
    Sleep ends

    The worker thread wakes up. Nothing stopped it during the pause, because the flag was only written, not acted on.

  3. 3
    Second check fires

    delay() reads running after the sleep, sees false, and throws ThreadTerminationException rather than returning normally.

  4. 4
    Third call unwinds

    The exception leaves the third call without that call returning normally. It propagates to the second call, which was waiting on the third.

  5. 5
    First call unwinds and thread ends

    The exception passes through the second call and then the first call. No pending call finishes its remaining work, and the animation thread terminates.

Result

The abort takes effect at the next check after the click, which here is the second check inside delay(). The exception then removes every pending recursive call, and the thread terminates.

Mistakes When Making Recursion Cancellable

  • Common mistake

    Expecting the button click to stop the thread directly

    What it looks like

    Writing a Finish handler that only sets running to false and assuming the sort halts at that moment.

    Why it fails

    The flag only carries the request. The thread keeps running until it reaches a point where the flag is read, and a recursive algorithm may be many levels deep when the click arrives.

    Do this instead

    Read the flag at safe points inside the work, such as inside delay(), and let the exception unwind the recursion.

  • Common mistake

    Catching the termination exception inside the recursive method

    What it looks like

    Wrapping the recursive call in a try block that swallows ThreadTerminationException at each level.

    Why it fails

    The exception is what returns the recursive calls to the top. Catching it inside the recursion stops the unwinding at that level.

    Do this instead

    Let ThreadTerminationException propagate out of the recursion so every pending call unwinds.

  • Common mistake

    Checking the flag only once per pause

    What it looks like

    Checking running only before Thread.sleep() inside delay().

    Why it fails

    A click during the sleep goes unnoticed until the next call to delay(), so the abort is delayed.

    Do this instead

    Check the flag both before and after Thread.sleep(), as the demo does.

  • Common mistake

    Treating the boolean as an ordinary variable when the worker thread reads it, instead of declaring it volatile

Practice Tracing an Abort

MEDIUM

A recursive algorithm in a worker thread checks a volatile flag only once, at the very start of each recursive call. The user clicks Finish while the algorithm is four calls deep and currently inside a pause that is not preceded by a check. Explain how and when the abort takes effect, and identify which mechanism causes the thread to terminate.

Hints
  • Ask which points in the code actually read the flag, and whether the click can happen at a point that is not one of those reads.
  • Think about which mechanism carries the termination out of the recursion: the flag, or an exception that propagates up through the calls.

Key Takeaways

  • A Finish click cannot stop a deep recursive algorithm directly, because the thread is inside a stack of pending calls that must all return first.
  • A volatile boolean such as running works as a stop signal: setting it to false carries the request, but does not stop anything by itself.
  • The abort takes effect where the flag is read, which in the demo is delay(), checked both before and after Thread.sleep().
  • Throwing ThreadTerminationException unwinds every recursive call, and catching it inside the recursion would defeat that purpose.

Related Topics