Recursion, which literally means running back, plays a pivotal role in problem-solving. For instance, a problem-solving strategy based on divide-and-conquer divides a given problem (that cannot be solved immediately) into subproblems of a similar nature so that the same strategy can be applied to these subproblems recursively; the obtained solutions to these subproblems are then combined in some manner to form a solution to the original problem.
As the first example, let us implement the factorial function that takes a natural number n and returns the product of the first n positive integers. In the following code, a function of the name fact is defined recursively:
The keyword fun initiates the definition of a function, and the function header following fun specifies that fact is a function taking an integer as its argument and returning another integer as its result. For testing fact, let us include the following line: where println! is a function-like in ATS, which resembles a function but is not actually a function. In this case, println! can be thought of as a macro that calls a print function on each of its arguments and then prints out a newline at the end. Please do not forget the symbol ! in the name println!.Suppose we need to call fact on all of the natural numbers less than a given one (e.g., 100). We can first define a function testfact as follows and then call testfact on the given natural number:
// fun testfact (n: int): void = if n > 0 then ( testfact(n-1); println! ("fact(", n-1, ") = ", n-1) ) (* end of [if] *) //
In imperative programming, a function like testfact is normally implemented in terms of a for-loop (instead of being defined recursively). While there is indeed direct support for for-loops and while-loops in ATS, I will not attempt to make use of the support in this book. I hope to make a convincing argument that making extensive use of recursion is a key to increasing one's programming producivity. In fact, I think that a functional programmer should develop a reflex for solving problems recursively.
As another example, the following function fibo is defined to compute Fibonacci numbers:
The first and the second Fibonacci numbers are 1. Given a positive integer n greater than 2, the nth Fibonacci number equals the sum of the previous two Fibonacci numbers. This implementation of fibo is of expontial time complexity, and it is probably impractical to call it on any integer that is 50 or greater.For a slightly more interesting example, please study the code in multable.dats, which can be executed to generate the html file multable.html for displaying a multiplication table.
Please find on-line the entirety the code used in this chapter. The mentioned URL link(s) can be found as follows: