Transformative pattern: re-factoring a function to make it tail recursive

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.

January 8, 2009 | Filed Under erlang, metaprogramming, Programming

1 Comment 

Comments

One Response to “Transformative pattern: re-factoring a function to make it tail recursive”

  1. Nora on August 19th, 2012 9:43 am

    Wow! This can be one particular of the most
    useful blogs We have ever arrive across on this subject. Actually Magnificent.
    Im also a specialist in this topic therefore I can understand your hard work.