Assignment: #PadovanSequence Due: 10/25/2017 Points: 4

Specification

Write a C++ program that calls a function int padovan(int n) that returns the nth number from the Padovan integer sequence. The function is used to print the first 32 numbers of the Padovan sequence.

The Padovan integer sequence is defined as follows.

   p(n) = p(n-2) + p(n-3)  

   where p(0) = 1, p(1) = p(2) = 0

The padovan(n) function must be implemented using recursion.

You are free to use the following main() function to test your padovan(n) function.

   int main(int, char**) {
      const int HOW_MANY = 32;
      int padovan(int);
      for (int n = 1; n <= HOW_MANY; n++) 
         cout << "padovan(" << n << ") = " 
              << padovan(n - 1) << endl;
   }

The output of your program should look as follows.

   padovan(1) = 1
   padovan(2) = 0
   padovan(3) = 0
   padovan(4) = 1
   padovan(5) = 0
   padovan(6) = 1
   padovan(7) = 1
   padovan(8) = 1
   padovan(9) = 2
   padovan(10) = 2
   padovan(11) = 3
   padovan(12) = 4
   padovan(13) = 5
   padovan(14) = 7
   padovan(15) = 9
   padovan(16) = 12
   padovan(17) = 16
   padovan(18) = 21
   padovan(19) = 28
   padovan(20) = 37
   padovan(21) = 49
   padovan(22) = 65
   padovan(23) = 86
   padovan(24) = 114
   padovan(25) = 151
   padovan(26) = 200
   padovan(27) = 265
   padovan(28) = 351
   padovan(29) = 465
   padovan(30) = 616
   padovan(31) = 816
   padovan(32) = 1081