Case Else:

Recursion is one of those epiphanous things; people don’t seem to grasp it at first, but once you do; it can streamline a lot of problems. I started jotting down an illustration of recursion for a coworker, and it got complicated, and then it turned into an application, so you get two. Both are batch files (don’t ask . .. it was just for sport)

Recursions can do their work inbound or outbound (there’s probably a term for it, but I don’t know what it is). In a similar way, if I want to know how far it is to your house, I can drive there, and clock the miles, or drive there then clock the miles on the return trip. The decision is made on details such as whether or not I know where your house is.

@ECHO OFF
IF "%1"=="" (
 ECHO Usage: ! [1-12]
 GOTO :EOF
)

:: For any given recursion, you have to have an end,
:: where it begins to return. This is the 'bottom' of
:: the recursion (similar to a do-while-loop)
IF "%1"=="0" (
 SET TOTAL=1
 Echo. %INDENT% ==========
 ECHO. %INDENT%  seed = 1
 Goto :EOF
)

:: Descending. Some recursions work on the way down,
:: some on the way up. This one only counts, on the way
:: down - partly because it's easier to seed The total
:: with 1 at that point, than try to create a mechanism to
:: store the number you enter, but not store any of the
:: other numbers on the way down. From the side, a
:: recursion is similar to dropping objects as you walk
:: through a maze, and picking them back up as you
:: retrace your steps.

:: Make this visual
Echo. %INDENT%Ú Count = %1
:: /a = do arithmetic
Set /a COUNT=%1-1

:: Build connecting lines, as we go
(SET INDENT=%~2³)

:: Recurse - the function calls itself for the next step.
CALL !.bat %COUNT% "%INDENT%"

:: Ascending. As each function call returns, it daisy-chains
:: back up the way it descended, doing the last half of
:: each function call as it goes.

:: This is the single functional line of the function.
Set /a TOTAL=%TOTAL% * %1

:: indent=Mid$(indent,2)
SET INDENT=%INDENT:~1%
:: Make it visual
Echo. %INDENT%À * %1 = %TOTAL%

download !.bat
!.bat calculates factorials. If you’ve forgotten, a factorial is a number multiplied by every positive integer smaller than itself: factorial X=1*2*…*X so factorial 3 (or 3!) = 3 * 2 * 1. This is an ideal case for recursive functions, because a) the series clearly ends, and b) for every value of x, that part of the function is x*x-1 or f(x)=x*f(x-1); so, if x=3, then 3! = (3 * 2!) where 2! = 2 * 1! and 1!=1. In other words, we don’t have to know anything more about the values other than for any x, x!=x*(x-1)!, and that 1!=1 (ie, that’s where we stop going deeper).

Run !.bat, and give it a number (ie, ! 3) . . . but 12 is it’s limit, because it’s doing 16-bit integer math. Beyond 65535 it rolls over like a pinball machine, and the math is just wrong. The script is simple, and you should get the hang of the code pretty quick. Heck, it’s only 40 lines, and most of them are comments, or are there to show the nesting as obviously as possible. In a real language, a lot of recursions are one or two lines long.

In the code, I embedded Unicode characters into the bat file. They look different in most other code pages, so you will probably see the following characters:

• Ú = ┌
• ³ = │
• À = └

As you may guess, those three characters form the basis for the tree structure.

As a sidebar; this little app has an overflow condition, as mentioned above. It does 16-bit math, so as the total grows, it approaches a limit where it is no longer valid. The function grows (logarithmically? it’s not exponentially) faster as it goes, but if we used a more linear function (say, f(x)=x+1 ) we would still have constraints we need to worry about. Every time you call a bat file, the system opens a new shell space for it, with its’ own environment full of it’s own copy of the existing environment variables. This environment is between 160 bytes and 32Kb, depending on how your system is set up, and all of the running shells run in the same 640Kb section of memory reserved for DOS. If you run too many shells, they’re going to fill up the reserved space, have no where to put their children, and die of overpopulation (insert planned parenthood reference, here.) In higher level (or lower level) languages, this is analogous to ‘bashing the stack‘. Because of this, it’s important to evaluate things like how big it’s going to get. Our batch file can’t process numbers larger than 12, so it’s constraint keeps it fairly small; however your implementation of a google-bottles-of-beer-on-the-wall probably wouldn’t get very far. In a case like that, putting your lyric into a function and calling it from a For loop would get you farther, because the function would be called one-at-a-time, instead of one-from-the-previous. In other words, each function call would end (and release its’ environment/stack space) before the next one was called.

The second app in the series is Recursion in Batch, Part 2: a tree command.

Originally written July 4th, 2005