Plotting intermediate values of an argument in a recursive function

Question

I've read through the documentation on tuning and debugging but feel like I am missing some important concepts. Many of the examples given presume the programmer is explicitly generating ranges of values for a symbolic variable. For example, on the Reap documentation page, we have this canonical example:

Reap[Sum[Sow[i^2] + 1, {i, 10}]]

Here, the Sow and Reap functions work together to collect intermediate states of the calculation i*i, where i is set to iterate from 1-10. No problems here, as the variable is a symbol (i) and its iteration bounds are set in the expression.

However, there are other approaches to writing expressions, including recursive definitions where a single value will be passed in to a variable and it may be useful to monitor that variable as it is transformed throughout the recursive calculation.

For example, given a homemade gcd function based on the Euclidean approach:

gcd[x_, y_] := If [Equal[y, 0], x, gcd[y, Mod[x, y]]]

We can trace this function as follows:

However, that output is a bit verbose and cannot be immediately graphed (as far as I know). I've tried Reap/Sow, Monitor, and others, however, as noted above, the example assume mostly a symbolic variable that is given a range rather than a recursive function with a value passed in. It is not clear to me how to use these tools for the case of a recursive function such as the gcd example above where a value is passed into the function and the desired behaviour is to monitor / accumulate transformations of a function variable.

What would be the correct way to:

1. Accumulate a list of intermediate values for variable x in gcd[x, y] as this variable is updated through successive recursive calls;
2. Plot these intermediate values of x to visualise how the function iterates towards a final solution?

Answer 1

Here is one approach:

Cases[Trace[gcd[4, 16]], gcd[x_, _] :> x, All]
(* {4, 16, 4} *)

This should work in most simple cases. It extracts the relevant parameters from the calls listed in the output of Trace. For very long traces with a lot of irrelevant stuff, this might not be very efficient however. We can improve this by supplying a filter to Trace:

Cases[Trace[gcd[4, 16], gcd], gcd[x_, _] :> x, All]
(* {4, 16, 4} *)