Pattern for algorithm that outputs an explanation of how it gets to a solution when needed

The "pattern" you are looking for is called "logging", just make the logging statements as verbose as you need them. By using a decent logging framework you should be able to switch it on and off at run time, provide different verbosity levels, or tailor the output for different purposes (like web vs. console).

If this has a noteable performance impact (even if logging is switched off) will probably depend on the language, the framework and the number of logging statements you need in the specific case. In compiled languages, if this really becomes a problem, you could provide a compiler switch to build "logging variant" and a "non-logging variant" of your code. However, I heavily recommend against optimizing "just in case", without measuring first.

A good pattern is Observer. https://en.wikipedia.org/wiki/Observer_pattern

In your algorithm, at each point where you want to output something, you notify some observer(s). They then decide what to do, be it to output your text on the console, or to send it to the HTML engine/Apache etc.

Depending on your programming language there may be different ways to make it fast. For example, in Java (treat it as pseudocode, for brevity; making it "correct", with getters, setters, is left to the reader):

interface AlgoLogObserver {
   public void observe(String message);
}

class AlgorithmXyz {   
   AlgoLogObserver observer = null;
   void runCalculation() {   
       if (observer!=null) { oberserver.observe("Hello"); }
       ...
   }   
}

...
algo = new AlgorithmXyz();
algo.observer = new ConsoleLoggingObserver();  // yes, yes make a 
                                               // setter instead, or use Ruby :-)
algo.runCalculation();

This is slightly verbose, but the check for ==null should be as fast as it can get.

(Note that in the general case, observer would probably be a Vector observers instead to allow for more than one observer; this is of course possible as well and will not lead to more overhead; you can still put in the optimization that you set observers=null instead of having an empty Vector.)

Of course, you'd implement different kinds of observers depending on what you want to achieve. You can also put in timing statistics etc. there, or do other fancy stuff.

As a slight improvement to straight logging, create some sort of object that models one execution of the algorithm. Add a "step" to this container object each time your code does something interesting. At the end of the algorithm, log the accumulated steps from the container.

This has a few advantages:

1. You can log the full execution as one log entry, often useful when there's the possibility of other threads logging stuff in between your algo steps
2. In my Java version of this class (called simply "Debug"), I don't add strings as log entries, but lambdas that produce strings. These lambdas are only evaluated IF actual logging will take place, i.e. if the Debug object finds that its log level is currently activated. This way, there is no performance overhead of constructing log strings unnecessarily.

EDIT: As commented by others, lambdas have overhead, so you would have to benchmark to ensure this overhead is less than the unnecessary evaluation of code required to construct the log string (log entries are often not simple literals, but involve getting contextual info from participating objects).

I usually look for the branching, meaning i look for if-statements. Because these indicate that i evaluate a value, that will control the flow of the algorithm. In each such occurance (each condition) i can then log the chosen path, and why it was chosen.

So basically i would log the entry values (initial state), every branch chosen (conditionals) and the values when entering the chosen branch (temp state).