A few days ago I talked a little about tail recursion, and I mentioned a pattern I called iterator/builder to transform some simple recursive functions into tail-recursive functions. The transformation looks like this (in Erlang).
% not tail recursive factorial_a( 0 ) -> 1; factorial_a( N ) -> N * factorial_a( N - 1 ). % tail recursive factorial_b( N ) -> fact_tail( N, 1 ). fact_tail( 0, Product ) -> Product; fact_tail( N, Product ) -> fact_tail( N - 1, N * Product ).
In this example of the iterator/builder pattern, N is the iterator and Product is the builder. Here are some more examples.
% count items in a list % not tail recursive count_a( [ ] ) -> 0; count_a( [_ | R] ) -> 1 + count_a( R). % tail recursive count_b( List ) -> count_t( List, 0). count_t( [ ], Total ) -> Total; count_t( [_ | R], Total ) -> count_t( R, 1 + Total ). % triangle number (0 + 1 + 2 + 3 ...) % not tail recursive triangle_a( 0 ) -> 0; triangle_a( N ) -> N + triangle_a( N - 1 ). % tail recursive triangle_b( N ) -> triangle_t( N, 0 ). triangle_t( 0, Sum ) -> Sum; triangle_t( N, Sum ) -> triangle_t( N - 1, N + Sum ).
Transforming these functions to be tail-recursive is simple. The pattern looks like this:
% Iterator/Builder pattern to transform a recursive % function into a tail-recursive function. % This is a common pattern. It is probably described % elsewhere with a different a name. % % Pattern variables: % null_pattern - matches null iter % null_value - initial value % iter_pattern - matches non-null iter % iter_first - first element value % iter_rest - iter with first element removed % fn_name( iter ) % combine_expression( iter_first, iter ) % Before (not tail recursive): fn_name( null_pattern ) -> null_value; fn_name( iter_pattern ) -> combine_expression( iter_first, fn_name( iter_rest )). % After (tail recursive): fn_name( X ) -> fn_name_tail( pre_transform( X ), null_value ). fn_name_tail( null_pattern, Collect ) -> Collect; fn_name_tail( iter_pattern, Collect ) -> fn_name_tail( iter_rest, combine_expression( iter_first, Collect )).
This is not perfect however. Consider the triangle function above. triangle_a(3) calculates (3+(2+(1+0))) while triangle_b(3) calculates (1+(2+(3+0))). If you change N+Sum to Sum+N in triangle_b you end up calculating (((0+3)+2)+1) instead. This is the left-fold vs right-fold problem that you sometimes run into when you flatten recursion, and also shows how the initial value for the fold operation (zero in this case) can move around. For an operation like + (plus) it doesn’t matter since + is associative and commutative, but it matters in other cases. Consider the stutter/1 function.
% stutter( [a,b,c] ) -> [a,a,b,b,c,c] % not tail recursive: stutter_a( [ ] ) -> ; stutter_a( [H | R] ) -> glom( H, stutter_a( R )). % tail recursive stutter_b( A ) -> lists:reverse( stutter_t( A,  )). stutter_t(  , C ) -> C; stutter_t( [H | R], C ) -> stutter_t( R, glom( H, C )). % another tail recursive version stutter_c( A ) -> stutter_t( lists:reverse( A ),  ). % combine expression for stutter glom( H, R ) -> [H, H | R].
stutter_a([a,b,c]) calculates glom(a,glom(b,glom(c,))) while stutter_b([a,b,c]) calculates glom(c,glom(b,glom(a,))) and then reverses the result. stutter_c([a,b,c]) starts by reversing the iterator and so calculates glom(a,glom(b,glom(c,))) just like stutter_a.
So the simple transformative pattern described above sometimes has to be modified if the combine expression is not associative and commutative. Sometimes you can fix the result, sometimes you can reverse the initial iterator, sometimes you need an extra end-of-iterator parameter when you reverse the iterator, and sometimes you have to change the combine expression.
And of course sometimes you just want to leave the function alone and forget about tail recursing. This kind of code transformation or re-factoring requires some understanding of the problem before being applied.