Recursion samples

Sample files

Please open Fibonacci.lava in LavaPE.

Please open FiboTailRecursion.lava in LavaPE.

Please open Factorial.lava in LavaPE.

Please open FacTailRecursion.lava in LavaPE.

Topics

Recursive functions as a substitute for sequential loops. See also the introduction to our repetitive computation samples.

Overview

If you are accustomed to sequential loops, as most of us, it is quite straightforward, nevertheless, to switch to recursive functions, since sequential loops can be easily transformed into "tail recursion" (and vice versa).

A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call, or in other words: A tail recursive function returns the value of the last recursive call as the value of the function. See here for general background information on direct, indirect, linear, tail and tree recursion.

A tail-recursive invocation of the current function can be viewed as a "continue" operation which returns control to the beginning of the loop that is represented by the recursive function.

The difference (and advantage), compared to conventional loops, is that you explicitly pass parameters to the recursive function. In this way you point out quite clearly which variables are involved in the repetitive computation.

Where to look and what to do

Fibonacci:

The Fibonacci sample is a typical tree recursion sample which clearly exhibits the rule that generates the Finonacci numbers but which, on the other hand, is very inefficient for computing these. Run the sample program.

FiboTailRecursion:

Its tail recursion counterpart is much more efficient as you can also see if you run both samples: The tree recursion algorithm takes a quite sensible amount of time to compute Fibonacci(25). Run the sample program.

Factorial:

The factorial sample illustrates linear recursion: The recursive call occurs within an arithmetic expression, while with

FacTailRecursion:

the result of the recursive call is returned to the caller without further processing. Run both sample programs.

Summary

Traditional loops are replaced by tail recursion in Lava. The input parameters of the tail-recursive replacement function f represent the variables that are changed by the loop. They are assigned new values on every recursive invocation of f. Every such recursive invocation of f corresponds to a jump to the beginning of the traditional loop.

Single-assignment and absence of loops cause the data flow in Lava programs to be directed strictly from top to bottom and enable complete initialization checks for variables.