Wafl Home

Program Structure Tutorial

Recursion

Being a functional programming language, Wafl does not posses variables, so any iterative processing is impossible. The only way to express repetitive behaviour of functions is to use recursion.

Recursion is very significant technique, that allows a function definition to use the function itself. Recursion is frequently used in mathematics, as a tool for defining indefinite (but still enumerable) structures. In Wafl, functions may be mutually recursive, i.e. use each other.

The usual example of recursive definition in mathematics is the definition of factorial. Factorial, usually denoted using postfix operator !, is defined such that:

    0! = 1
(n+1)! = (n+1) * n!

The definition of recursive functions is based on two steps: (1) recognition of terminal condition, i.e. if the arguments allow non-recursive, direct evaluation of the result and (2) definition of recursive evaluation in a way that each application of the step leads evaluation closer to the terminal condition. In the previous example, the terminal condition is satisfied if the argument is zero. In that case, the result can be directly evaluated to one. In other cases the result is defined based on the application of the same principles for smaller argument. It is obvious that one can evaluate the n! in n steps following these rules.

Another example of recursive definitions are Fibonacci numbers. First and second elements of the sequence are defined to be 1, while each of other elements is defined as a sum of two preceding elements:

fib0 = 1
fib1 = 1
fibn+2 = fibn+1 + fibn

The main considerations in recursion usage are well definitions of terminal conditions and recursive evaluation.

The definitions of factorial and Fibonacci numbers in Wafl are following.

Source code:

{#
factorial(0),
factorial(1),
factorial(2),
factorial(3),
factorial(4),
factorial(5),
fib(1),
fib(2),
fib(3),
fib(4),
fib(5),
fib(6)
#}
where{
    factorial( n ) = 
        if n<=1 then 1
        else n * factorial(n-1);
    fib( n ) = 
        if n<=2 then 1
        else fib(n-1) + fib(n-2);
}

Result:

{# 1, 1, 2, 6, 24, 120, 1, 1, 2, 3, 5, 8 #}

 

Table of Contents

Let's Start

Program Structure

Primitive Data Types

List

Tuple

Record

HTML

Command Line Interpreter

Using Web Servers

Syntax

Examples

Tips

The most of examples evaluates with both command line and Web server Wafl interpreters. If any example is based on specific features of an interpreter, it is explicitly annotated.