Recursive and iterative processes and procedures

During my js ⊂ lisp talk at beerjs, I noticed there were a few questions about recursion and tail call recursion, so with this post I hope to address that.

To start with, let’s define the following methods for creating a pair and getting its values:

function cons( $a, $b ) {
return function( $second ) use ( $a, $b ) {
return $second ? $b : $a;
};
}

function car( $pair ) {
return $pair( false );
}

function cdr( $pair ) {
return $pair( true );
}

An iterative process is characterized by a process whose state is captured with variables and rules how to transform them to the next state.

A recursive process is characterized by a chain of deferred evaluations. Note that a recursive procedure need not always generate a recursive process.

An iterative procedure is a procedure that does not have any references to itself.

A recursive procedure is a procedure that has references to itself.

With this, we see that there are recursive processes, and there are recursive procedures. Combining those, we get the following table:

Now that we’ve classified the combinations, we can discuss their properties and characteristics by examples:

1. An iterative process with iterative procedure. No recursion is involved, and there is no need for deferred evaluations (since the process is iterative). It can be further optimized using other looping constructs than goto, but we will write it this way to show the similarity with 3.

   // Iterative process, iteration (for languages that don't support tail call optimization)
   function lengthiter_i( $pair, $acc = 0 ) {
   begin:
   if ( null === $pair ) {
   return $acc;
   }        $pair = cdr( $pair );
   $acc  = 1 + $acc;
   goto begin;
   }
   

2. A recursive process with iterative procedure. Recursion is involved, but since the procedure is iterative, we will implement it with the help of a list (stack), e.g. to allow for deferred evaluations in some cases:

   // Recursive process, iteration
   function lengthrec_i( $pair ) {
   $stack = [];
   $acc = 0;        while ( null !== $pair ) {
   array_push( $stack, 1 );
   $pair = cdr( $pair );
   }while ( ! empty( $stack ) ) {
   $acc += array_pop( $stack );
   }
   
   return $acc;
   }
   

3. An iterative process with recursive procedure. Similar to the iterative process with iterative procedure, although differently implemented. May fail on languages that don’t have tail call optimization. Compare this code to 1 to see the similarity (additionally we map the arguments $pair => cdr( $pair ) and $acc => 1 + $acc).

   // Iterative process, recursion
   function lengthiter_r( $pair, $acc = 0 ) {
   if ( null === $pair ) {
   return $acc;
   }        return lengthiter_r( cdr( $pair ), 1 + $acc );
   }
   

4. A recursive process with recursive procedure. Similar to the recursive process with iterative procedure, although differently implemented in the way that the stack is implicit by calling the function multiple times, so we don’t need to handle it ourselves. For example:

   // Recursive process, recursion
   function lengthrec_r( $pair ) {
   if ( null === $pair ) {
   return 0;
   }        return 1 + lengthrec_r( cdr( $pair ) );
   }