|
![]() |
||||||||||||||
Program Structure TutorialRecursionBeing 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 #}
|
|
||||||||||||||
© 2006 Saša Malkov | |||||||||||||||