I need to stop execution during recursive algorithm

Question

Hey, I have a problem in choosing the right method to accomplish my goal. I'm working on Algorithms teaching system, I'm using C#. I need to divide my algorithm into steps, each step will contain a recursion. I have to stop execution after each step, user can then move to the next step(next recursion) using a button in my GUI.

After searching, threads was the right choice, but I found several methods:

• (Thread.sleep/interrupt): didn't work, my GUI freezed !!

• (Suspend/Resume): I've read that it's a bad idea to use.

• (Waithandles): still reading about them.

• (Monitor wait/resume).

I don't have much time to try and read all previous methods, please help me in choosing the best method that fits my system.Any suggestions are extremal welcomed.

Answer 1

You only need to use threads if you want to do work "in the background" while your user interface continues to be interactive, or if you want to split a slow task up so that it can be executed on multiple processor cores.

What you describe sounds like you only need to write a single thread:

• Remember where the user is up to in the sequence.
• Each time they click your button, execute the next step

If you wish to use threads, then you could use an AutoResetEvent to allow your thread to loop through the steps, and WaitOne on each iteration. Your user interface would then signal that event whenever the user clicks the button to start the next step. (You would also need to inform the UI when the step completes so the user can only run the steps in sequence - thought you could just set button.Enabled=false when they start a step, and the thread could use button.Invoke to set Enabled=true when it finishes the step). But threading sounds overcomplicated for what you seem to be describing.

Answer 2

Everything you listed will block execution, and if your code is executed in the main thread will freeze the UI.

If all you need is to suspend operation and then either resume it or cancel - then you have to move the calculation into a separate thread so that freezing it would not impact UI.

You can also approach your problem from a different angle. You can redesign your algorithms so that they can be restarted from any point - make your recursion stack external and pass it as a parameter

Answer 3

Threads are good as long as you are using it the right way. I would say start with following steps:

1. Create a form with, well, two buttons and two ProgressBars (b1, b2, p1, p2... for instance).
2. When button b1 gets clicked, start your recursive algo1 in BackgroundWorker, and show the progress in progress bar p1. If its important that you keep your user from pressing other buttons, then you may disable the buttons, until p1 completes.
3. When user clicks on the button b1, update the progress bar in p2.

This example might help.

Answer 4

You are heading in the right direction with waithandles.

Try using AutoResetEvent. I think this is one way to get you where you want to go.

Answer 5

Fundamentally, this question is not really about recursion or multi-threading, it is simply this:

How do I execute a long-running operation in the background of a GUI app so that the app stays responsive?

Implementing your own threading model is not the way to go here, especially if you are just starting to learn about multi-threaded/async operations. The .NET Framework already has a component for what you want to do: BackgroundWorker, which works in both Winforms and WPF (and almost any other architecture).

It is very, very easy to do what you want using the BackgroundWorker. I'll assume Winforms for this example but this is just as easy in WPF.

// Don't actually write this line; it will be in the .designer.cs file when you
// drop a BackgroundWorker onto the form/control.  This is for reference only.
private BackgroundWorker bwRecursive;

private void bwRecursive_DoWork(object sender, DoWorkEventArgs e)
{
    MyTreeNode root = (MyTreeNode)e.Argument;
    ExecuteRecursiveOperation(root);
}

private void bwRecursive_RunWorkerCompleted(object sender,
    RunWorkerCompletedEventArgs e)
{
    // Optionally update the GUI with the results here
}

private void ExecuteRecursiveOperation(MyTreeNode node)
{
    if (bwRecursive.CancellationPending)
        return;

    foreach (MyTreeNode childNode in node.ChildNodes)
    {
        if (bwRecursive.CancellationPending)
            break;

        ExecuteRecursiveOperation(childNode);
    }
}

You obviously also have to wire up the DoWork and RunWorkerCompleted events, and make sure to set WorkerSupportsCancellation to true on the BackgroundWorker. After that, you run the operation with:

bwRecursive.RunWorkerAsync(someTreeNode);

And cancel with:

bwRecursive.CancelAsync();

---

The only wrinkle here is that you say you want to pause (not stop) execution after each "step". I would probably do this using an AutoResetEvent, which is a type of event that resets its signaled ("ready") state every time a wait succeeds. Again, it's only a few lines of code to integrate:

public class MyForm : Form
{
    private AutoResetEvent continueEvent = new AutoResetEvent(false);

    // Previous BackgroundWorker code would go here

    private void ExecuteRecursiveOperation(MyTreeNode node)
    {
        if (bwRecursive.CancellationPending)
            return;

        foreach (MyTreeNode childNode in node.ChildNodes)
        {
            continueEvent.WaitOne();  // <--- This is the new code

            if (bwRecursive.CancellationPending)
                break;

            ExecuteRecursiveOperation(childNode);
        }
    }

    private void btnContinue_Click(object sender, EventArgs e)
    {
        continueEvent.Set();
    }

    private void btnCancel_Click(object sender, EventArgs e)
    {
        bwRecursive.CancelAsync();
        continueEvent.Set();
    }

    private void btnStart_Click(object sender, EventArgs e)
    {
        continueEvent.Set();
        bwRecursive.RunWorkerAsync(...);
    }
}

There's one thing that might warrant additional explanation here and that is the cancel method, which first cancels and then sets the continueEvent. It's necessary to do this because if the worker is still waiting for the event, it won't actually get to the cancellation stage, so when you cancel, you need to allow the worker to continue. You also need to set the continueEvent when you start the worker if you want it to execute the first step without requiring the user to hit "continue."

Answer 6

If you're interested in teaching about recursion, while allowing the algorithm to pause at each iteration, you may want to consider creating a state manager class that wraps the algorithm and exposes an explicit Stack. Recursive algorithms are really a form of stack-based algorithms, so having the ability to run single iterations and see the contents of the stack will help demonstrate how the recursion is actually functioning. I could imagine something like:

public struct AlgorithmParameters
{
    public readonly int Parameter1;
    public readonly int Parameter2;

    public AlgorithmParameters(int parameter1, int parameter2)
    {
        Parameter1 = parameter1;
        Parameter2 = parameter2;
    }
}

public class RecursiveAlgorithm
{
    private Stack<AlgorithmParameters> _parameterStack = new Stack<AlgorithmParameters>();

    public IEnumerable<AlgorithmParameters> ParameterStack
    {
        get { return _parameterStack; }
    }

    public IEnumerable<RecursiveAlgorithm> RunAlgorithm(int parameter1, int parameter2)
    {
        return RunAlgorithm(new AlgorithmParameters(parameter1, parameter2));
    }

    public IEnumerable<RecursiveAlgorithm> RunAlgorithm(AlgorithmParameters parameters)
    {
        //Push parameters onto the stack
        _parameterStack.Push(parameters);

        //Return the current state of the algorithm before we start running
        yield return this;

        //Now execute the algorithm and return subsequent states
        foreach (var state in Execute())
            yield return state;
    }

    private IEnumerable<RecursiveAlgorithm> Execute()
    {
        //Get the parameters for this recursive call
        var parameters = _parameterStack.Pop();

        //Some algorithm implementation here...

        //If the algorithm calls itself, do this:
        int newParameter1 = 2; //Parameters determined above...
        int newParameter2 = 5;
        foreach (var state in RunAlgorithm(newParameter1, newParameter2))
            yield return state;

        //More implementation here...

        //We've finished one recursive call, so return the current state
        yield return this;
    }
}

I haven't tested this code, but hopefully this gives you the idea. The "yield return" construct will essentially turn this into a state machine that implements the recursive algorithm, with a stack representing the parameters at each iteration. To run the algorithm iteratively, get an IEnumerator and iterate at whatever pace you'd like. After each iteration, you can inspect the stack and display it to provide helpful information on how the algorithm is progressing.

Answer 7

You don't really need multithreading for this. A recursive or iterative algorithm already lends itself well to stepping.

class MainWnd : Form{
    /*
     * A typical recursive factorial function would be
     * implemented something like this:
     */
    double Factorial(int n){
        return (double)n * Factorial(n - 1);
    }

    /*
     * Alternatively, factorial can be implemented iteratively:
     */
    double Factorial(int n){
        double product = n;
        while(--n > 1)
            product *= n;
        return product;
    }

    /*
     * Let's break the logic up into steps, so that it
     * saves its state between steps and resumes where
     * it left off for the next step.
     */

    int    factorialN;
    double factorialProduct;

    void BeginSteppedFactorial(int n){
        factorialProduct = n;
        factorialN       = n - 1;
    }
    bool StepFactorial(){
        if(factorialN <= 1)
            return true; // we're done, the result is ready

        factorialProduct *= factorialN--;
        return false; // we're not yet done, call the next step
    }
    double GetSteppedFactorialResult(){return factorialProduct;}


    static void Main(){Application.Run(new MainWnd());}
    MainWnd(){
        BeginSteppedFactorial(32);

        Label lbl = new Label(){
            AutoSize = true,
            Location = new Point(10, 10),
            Text     = GetSteppedFactorialResult().ToString(),
            Parent   = this
        };
        Button btn = new Button(){
            Location = new Point(10, 30),
            Text     = "Next Step",
            Parent   = this
        };
        btn.Click += (s, e)=>{
            if(StepFactorial()){
               btn.Text = "Finished";
               btn.Enabled = false;
            }
            lbl.Text = GetSteppedFactorialResult().ToString();
        };
    }
}

That's a working example, and although factorial is a very simple function, the skeleton is here for more complicated routines.

Answer 8

AutoResetEvent + BackgroundWorker was the perfect choice :)