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

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

  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:

    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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s