# Implementing local variables of a recursive function with either Module or Block

First, some quick background: I have been eagerly learning Wolfram and Mathematica for two months now, and along the way have written about 250 pages of teaching material that has ballooned into a computer science book of sorts, available at

http://www.scs.ryerson.ca/~ikokkari/Math/

The question I wanted to ask concerns the difference of Module and Block, specifically when used in recursion. I have googled the Wolfram documentation, StackExchange and other places where I have previously learned a bunch of stuff, but this is still not entirely clear.

Suppose we try out the functional programming and list manipulation standard textbook exercise of implementing Flatten.

flatten[x_List] := Module[{result = {}},
Scan[(result = Join[result, flatten[#]]) &, x];
result
];
flatten[x_] := List[x];


I get the correct results from this function when I try it out, so I assume that Module always creates new versions of its local symbols by tacking a dollar sign and a running number to the end of each symbol name. Despite the fact that the documentation says that Module uses lexical scoping, this seems to be done dynamically each time that the module is entered recursively, so the different levels of recursion end up having differently named local variables that cannot clash, the running tally of ModuleNumber increasing by one at each recursive call.

Alternatively, we can use Block:

flattenblock[x_List] := Block[{result = {}},
Scan[(result = Join[result, flattenblock[#]]) &, x];
result
];
flattenblock[x_] := List[x];


As I understood it, there now exists only one instance of the variable result that is shared by all levels of recursion, but each time the recursive Block is entered, its old value is pushed into an internal stack, from where it is popped the moment that the Block is exited, so the different levels of recursion again end up using separate values of the same variable. This is similar to the way that recursion is usually implemented in imperative stack-based languages.

Question: outside advanced metaprogramming and staying within the realm of the recursion exercises traditionally seen in computer science textbooks, does there exist a simple situation where Module and Block, when used inside a recursively defined function that uses them to define a local variable that represents an intermediate result, would produce a different end result? Or are these two always pretty much equivalent, even with recursion?

-
The differences between Module, Block and With are discussed extensively here. Please take a look and see if the answer to your question can be found there. – Michael E2 Sep 1 '14 at 18:50

flatten and flattenblock themselves provide an example of how Module and Block differ in behaviour:
flatten[{a, {result}}]

It is easy to imagine flattenblock being called from within another function that uses the symbol result as a variable name. The results would likely be unexpected. It is safest to stick to Module for the normal cases, reserving Block for the special applications that require dynamic scoping.