SICP insight of the day: iterative programming doesn’t require a for loop. Tail recursion is iterative programming. It looks very close to recursion, but the distinction is: a program is iterative if everything it needs is stored in a few state variables. In an imperative style the state is stored in mutable variables. In a functional style the state is passed as parameters to the function, over and over again.
The key difference between recursion and iteration is whether any necessary information is stored on the stack between calls. Is there any operation to perform after the recursive call completes? If so, we need the stack. If not, tail recursion, iterative program. Of course, this is why iterative programs can go on forever, while recursive programs will eventually run out of stack space. Recursion requires the computer to store more state for every pass. Iterative programs have a fixed amount of state.
The awesome concept here is the distinction between the shape of program execution vs the style it is written in. Look at what the code does, not how it goes about it.
There is one advantage of tail recursion over a for loop, even though both produce the same kind of program. Tail recursion lets everything stay immutable. This is safer.
When we’re training ourselves to think functionally, using recursion in place of loops and mutables: look at the for loop. What state is tracked within there? Typically there is some state that determines when to stop (a counter, typically) and one or more running totals that represent the output of the loop. Take each of these and make it a parameter to the recursive function. Pattern-match on the state to determine when to end the loop; output the running totals at that point. In the recursive call, increment or advance the pieces of state and pass the updated ones as parameters to the next call.
For instance:
String printContents(String[] arr) {
String output = "";
for (int i = 0; i < arr.length; i++) {
output += " " + i + ") " + arr[i] + "\n";
}
return output;
}
Here, the state of the iteration is contained in the the counter i and the aggregator output. A direct, simple translation to a tail-recursive function is then:
String printContents(int i, String output, String[] arr) {
i >= arr.length?
output :
printContents(i + 1, output + " " + i + ") " + arr[i] + "\n", arr);
}
See how the loop counter became an argument and the aggregator became an argument? The input was an argument to begin with and stays there. This transfers the needed state to the next call.
People familiar with functional style will immediately recognize that there are easier ways to flip through the contents of an array or collection. That’s fine — functional languages have syntax to make this very common pattern extra-clean. The point is that when we’re used to thinking of iteration in terms of loops, we can train ourselves to recognize the iterative state and move it into parameters.
Now, if the purpose of your for-loop is to produce a bunch of side effects, I got no help for ya.
Disclaimer: never do this in real life in Java because tail-recursion is not supported.
Personal footnote: The other day a friend gave me some serious geek cred points when he noticed the Wizard Book on my nightstand. It is a classic, and it’s filling in holes in my education. I’m only on chapter one, but every section that I read makes my day.