This pattern appears frequently in nature and in mathematical puzzles:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
If you've seen the Fibonacci sequence before, you already know how to calculate its next element, which is 144. The rule is simple: To get any number in the sequence, add the previous two.
The script in Listing 12.1 contains two functions to find the nth element (counting from zero, as usual) in the Fibonacci sequence: one iterative and the other recursive. When run, it shows that both functions get correct results; but there is a dramatic difference in the performance numbers.
01: #!/usr/bin/env ruby 02: 03: # A performance test of iterative and recursive functions 04: # that calculate ...