Because the Fibonacci sequence is simply defined by recursion, it makes for an elegant programming exercise. Here is one way to do it in SAS, and another way to do it in R. I've also included unit testing code to check that it works.
Fibonacci sequence in SAS using a recursive macro:
%macro fib(n); %if &n = 1 %then 1; * first seed value; %else %if &n = 2 %then 1; * second seed value; %else %eval(%fib(%eval(&n-1))+%fib(%eval(&n-2))); * use recursion; %mend; * show values 1-5; %put %fib(1); %put %fib(2); %put %fib(3); %put %fib(4); %put %fib(5); * check values 1-10; %macro check_fib; %if %fib(1) ne 1 %then %abort; %if %fib(2) ne 1 %then %abort; %if %fib(3) ne 2 %then %abort; %if %fib(4) ne 3 %then %abort; %if %fib(5) ne 5 %then %abort; %if %fib(6) ne 8 %then %abort; %if %fib(7) ne 13 %then %abort; %if %fib(8) ne 21 %then %abort; %if %fib(9) ne 34 %then %abort; %if %fib(10) ne 55 %then %abort; %put NOTE: OK!; %mend; %check_fib;
Fibonacci sequence in R using a recursive function that supports either single integers or a vector of integers:
fib <- function(n)
{
if (length(n) > 1) return(sapply(n, fib)) # accept a numeric vector
if (n == 1) return(1) # first seed value
if (n == 2) return(1) # second seed value
return(fib(n-1)+fib(n-2)) # use recursion
}
# print first five Fibonacci numbers
fib(1)
fib(2)
fib(3)
fib(4)
fib(5)
# verify the Fibonacci sequence 1 through 10
(actual <- fib(1:10))
(expected <- c(1,1,2,3,5,8,13,21,34,55))
all.equal(actual,expected)
For alternative implements, see SAS and R: Example 7.1: Create a Fibonacci sequence. In SAS, Nick Horton calculates the Fibonacci sequence using a DATA STEP, and in R he uses a FOR loop.
Adam Rich responded with his post Fibonacci Sequence in R with Memoization which gives a performance boost by caching the results.
In the comments below, Rick Wicklin referred to his SAS/IML solution that generates the Fibonacci sequence iteratively and Matrices, eigenvalues, Fibonacci, and the golden ratio.
This post first appeared on Heuristic Andrew.
What are the structures in the R unit test called (the ones in parentheses)? Or to put it in another way, why have you enclosed those expressions within parentheses?
ReplyDeleteNavneeth: the lines that define actual and expected (copied below) are enclosed in parentheses to print the value of the assignment. Without the parentheses, the assignment would still happen, but nothing would be printed.
Delete(actual <- fib(1:10))
(expected <- c(1,1,2,3,5,8,13,21,34,55))'
Try pasting the code yourself into r-fiddle.org
Thank you, Andrew.
DeleteYou can also generate the Fibonacci sequence iteratively:
ReplyDeletehttp://blogs.sas.com/content/iml/2010/09/30/twitter-and-the-fibonacci-sequence/
And, since the Fibonacci sequence is simply a linear relationship based on the two previous values, you can define the "Fibonacci matrix," which not only generates the sequence but also has interesting geometric properties: http://blogs.sas.com/content/iml/2010/10/05/matrices-eigenvalues-fibonacci-and-the-golden-ratio/
Hi Rick, thank you for the comment. I included your links in the article to make them easier to click.
Delete