## Interview Question: Recursive Series

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++]

This entry was posted in Sample Qs. Bookmark the permalink.

### 10 Responses to Interview Question: Recursive Series

1. Brett says:

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.

2. Avi says:

3. heath says:

Solutions please? With the best O(n)

4. Brett says:

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

5. Bin says:

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);}

6. Brett says:

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

7. Brett says:

[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

8. James says:

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?

9. Brett says:

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

10. James says:

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;}