December 3, 2010
Sequence Generation – Recursive
Problem
Given the following sequence of integer numbers:
1 |
1 1 2 3 5 8 13 21 34 55 89 ... |
Write a recursive function that receives the index of a given number in the sequence above and returns the corresponding sequence number for example if index = 2 the function should return 2, if the index = 5 the function should return 8 and so on
Solution
This is the same problem that we solved before but now we are going to solve it recursively. The base case is going to be the same as that in the iterative solution which is index = 0 or index = 1 in that case we just return 1 otherwise we simply return the sum of the previous two elements. Please refer to the code below for more information
Code
Here is the code in Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#!/usr/bin/perl # Print the first 11 elements of the # sequence for ($k = 0; $k <= 10; $k++) { print &Sequence($k) . " "; } # Given an index print the corresponding sequence number sub Sequence { # Pass index number my ($index) = @_; # Base case if ($index == 0 || $index == 1) { return 1; } # Return the sum of the previous two elements return Sequence($index-1) + Sequence($index-2); } |