Sample Question #231 (programming – general)

Can you write a recursive function, in your favorite language, that calculates the

*n*-th number in the Fibonacci series? (You may assume the series starts with 1 and 1.)[A real interview question; when I was asked of it, I was asked to write the function in C++]

Advertisements

HINT

Be sure to cover the special cases when n=1 and n=2. Also, your function should have error-checking, i.e., making sure n is a natural number.

another hint:how long will your program run?make sure you have that answer (or an estimate) before you give your final answer

Solutions please? With the best O(n)

Oops, I don’t have the definitive answer. It’s easy to do it in a loop, and I can’t figure out how to make it more efficient:

a = 1;

b = 1;

for (i = 3; i <= n; i++) {

c = a+b;

a = b;

b = c;

}

# after the loop, b holds the n-th Fibonacci number, where n>=3

What do you think?

-brett

hi Brett,thanks for your website. here is another solution for it.int f(int n){ if(n==1) return 1; if(n==2) return 2; return f(n-1)+f(n-2);}

Wow, thanks for the solution! I think your f() will work — except that I’d change the conditions to

if (n<3) return 1;

because the Fibonacci series starts with 1,1,2,3,….

-brett

ANSWER

[Many thanks to the anonymous visitor who posted the pseudo-code on 11/26/2007 at 2:09:24 AM (Eastern Time?)]

The following Perl script demonstrates the solution suggested by a kind anonymous visitor:

#!/local/bin/perl

sub f { my $n = shift; return 1 if $n < 3; return f($n-1) + f($n-2);}

my $z = f(int $ARGV[0]);print "$z\n";exit 0;

Note that this script only prints the n-th (where n is specified as the only argument on command line) Fibonacci number, not the entire series up to n.

Output for n=1 to 8:

bash-2.05b$ ./fibo.pl 713bash-2.05b$ ./fibo.pl 11bash-2.05b$ ./fibo.pl 21bash-2.05b$ ./fibo.pl 32bash-2.05b$ ./fibo.pl 43bash-2.05b$ ./fibo.pl 55bash-2.05b$ ./fibo.pl 68bash-2.05b$ ./fibo.pl 713bash-2.05b$ ./fibo.pl 821

-brett

That recursive function is a good example of macho programming. But would you really prefer something that takes nearly 2^n recursions to do a calculation when by passing a couple more arguments you could get it to just n recursions?

Good point. But since the interviewer specifically asked for a recursive function, as the candidate you’d just have to give him/her that answer. If you said "but this is stupid ‘cuz I could use an O(n) loop which is more efficient," he or she wouldn’t be happy at all. (Someday when you don the hat of an interviewer, you’d also want the interviewee to answer your question, not what he or she thinks should be the question.)

-brett

recursive function with n recursions:double f(double x, double y, int n,int c){ if(n==c) return x; double fn = f(y,x+y,n,c+1); return fn;}