The Padovan Sequence is a recursive series I discovered recently, and it is similar to the Fibonacci Sequence I’ve written about before. The difference is the patterns the two recursive sequences make.
This is a graphic representation of the Fibonacci Sequence:
And this is a graphic representation of the Padovan Sequence:
The base case of the Padovan Sequence is defined as
f(0) = f(1) = f(2) = 1
and the general case is defined as
f(n) = f(n − 2) + f(n − 3)
So you can see that we can easily create an algorithm to return the Padovan Sequence using any language which supports recursion, and I have chosen Fortran to do so. We can do this with an if/else block, defining first the general case, and then the base caes (or vice versa, if you’re so inclined.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | ! ---------------------------------------------------------- ! Programmer: Jonathan Landrum ! Date: 17 February 2012 ! ---------------------------------------------------------- ! Program: padovanSequence.f95 ! Purpose: Calculates the Padovan Sequence. ! Assumptions: None. ! ---------------------------------------------------------- PROGRAM padovanSequence IMPLICIT NONE INTEGER :: counter = 0, input = 0, padovan WRITE (*,*) '* * * * * * * * * * * * * * * * * * * * * * *' WRITE (*,*) '* *' WRITE (*,*) '* FORTRAN PADOVAN SEQUENCE GENERATOR *' WRITE (*,*) '* *' WRITE (*,*) '* * * * * * * * * * * * * * * * * * * * * * *' WRITE (*,*) WRITE (*,*) 'This program calculates and returns members' WRITE (*,*) 'of the Padovan Sequence.' WRITE (*,*) WRITE (*,*) 'How many Padovan Numbers would like to return?' WRITE (*,*) READ (*,*) input ! If the user inputs a negative number, ask again DO WHILE (input < 0) WRITE (*,*) WRITE (*,*) 'ERROR: Negative input' WRITE (*,*) WRITE (*,*) 'How many Padovan Numbers would like to return?' WRITE (*,*) READ (*,*) input END DO ! END while negative WRITE (*,*) WRITE (*,*) '--------------------------------------------------' ! We have a legitimate number, do the calculation DO WHILE (counter < input) WRITE (*,*) padovan(counter) counter = counter + 1 END DO ! END Processing loop WRITE (*,*) '--------------------------------------------------' WRITE (*,*) WRITE (*,*) '\\//_ Live long and prosper.' WRITE (*,*) END PROGRAM padovanSequence ! ---------------------------------------------------------- ! FUNCTION padovan: ! Calculates and returns the integer of the Padovan Sequence ! at the specified input position. The sequence is: ! 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, etc. ! ---------------------------------------------------------- RECURSIVE FUNCTION padovan (input) RESULT (output) IMPLICIT NONE INTEGER :: input INTEGER :: output IF (input > 2) THEN output = padovan(input - 2) + padovan(input - 3) ELSE output = 1 END IF END FUNCTION padovan |
Because this program uses recursion, caution should be observed when asking for more than 50 or 60 numbers. By putting the general case first in the padovan() function, I’ve saved a little time insofar that the if/else block only has one test now versus the three it would have if I had put the base case first.
A better way to get larger members of the set would be to either call for each member individually, or save previous output to an array or external file and have the function start from the previous number. Or you could even do as I did with my prime number calculator and have the user define a range. As it stands, the program re-calculates every number back to 1 each time, and it starts with 0 each time. So it is not useful for finding the higher members of the set. However, it was certainly a fun programming experience, as I hadn’t tried recursion with Fortran before.
~Jonathan
