Recursion: Fibonacci Numbers

  • + 8 comments

    O(n) time-complexity; O(1) space-complexity. Passes all cases.

    public static int fibonacci(int n) {
        int[] fib = new int[2]; 
        fib[0] = 0; fib[1] = 1;
        for (int i = 2; i <= n; ++i) {
            fib[i % 2] = fib[0] + fib[1];
        }
        return fib[n % 2];
    }
    
    • + 7 comments

      Nice :)

      Here is a one-liner in python,

      fib = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)
      print (fib(int(input())))
      

      Complexity :

      • + 2 comments

        Oh wow! How does this work?

        • + 1 comment

          TBH, I took it from here. It evaluates a closed-form expression. You can learn about it here too. :)

        • + 0 comments

          here is problem solution in java python c++ c and javascript programming.

          HackerRank Recursion: Fibonacci Numbers solution

      • + 1 comment

        Python one-liners are so sexy.

        • + 2 comments

          C++ one-liners are sexy, too (and rare?):

          int fibonacci(int n) { return (n < 2) ? n : (fibonacci(n - 1) + fibonacci(n - 2)); }

          • + 0 comments

            Unfortunately most oneliners suffer from unreadability.

          • + 0 comments

            Time Complexity is high. O(2^n)

      • + 0 comments

        please explain this problem

      • + 0 comments

        holly shit.... lambda as supre powerful...

      • + 0 comments

        Although it's curious to find a non-iterative, closed-form solution, this isn't a practical method at all. We're doing integer arithmetic with integers of size O(n2) bits, and in fact, before performing the final bit-wise and, we've got an integer that is the first n Fibonacci numbers concatenated together!

        Not sure you'd want to use it, though.

      • + 0 comments

        Well done.

      • + 0 comments

        Recursive method, one-liner Python, passed all test cases

        return fibonacci(n-1) + fibonacci(n-2) if n > 1 else 1 if n == 1 else 0
        
    • + 2 comments

      To be picky: The problem asked for recursion :P

      • + 0 comments

        Yep, I agree on that. Just sharing different solutions :)

      • + 2 comments

        To be fair, if this were an actual interview question, I think I would want to point out that the naive recursive solution (without memoization or special formulas) is absolutely the worst way to compute Fibonacci numbers. If you draw out the call tree for say fib(10), you see that the function gets called a crazy number of times with the same values. The iterative version is just a better solution.

        • + 1 comment

          but you can do it recursively in O(n) time complexity with O(n) space complexity

          • + 2 comments

            How, without memoization or special formulas? To elaborate a bit more, here is a list of the different methods I can think of for computing the Fibonacci numbers:

            1. Binet's formula
            2. Iterative solution without memoization
            3. Iterative solution with memoization
            4. Recursive solution without memoization
            5. Recursive solution with memoization
            6. Recursive solution using formulas for F(2n) and F(2n+1) with or without memoization.

            If you only plan to call the function a few times and you're not worried about possible floating point errors, then 1 is the best. If you're calling it many times, then 3 is better than 5 is better than 1. If you need to calculate really large Fibonacci numbers, then 6 is the best. Without memoization the performance of solution 4 is horrible.

            • + 0 comments

              I was referring to 5. Recursive solution with memoization

            • + 1 comment
              #include <iostream>
              
              using namespace std;
              
              void fibonacci(int n, int *fn, int *fn1) {
                  // Complete the function.
                  if(n==1){
                      *fn=1;
                      *fn1=0;
                      return;
                  }
                  int fn_, fn1_;
                  fibonacci(n-1, &fn_, &fn1_);
                  *fn = fn_+fn1_;
                  *fn1 = fn_;
              }
              int main() {
                  int n;
                  int fn, fn1;
                  cin >> n;
                  fibonacci(n,&fn,&fn1);
                  cout << fn;
                  return 0;
              }
              
              • + 0 comments

                Cool trick!

        • + 0 comments

          Implementation with cache to reduce redundant calculations and help with response times.

          static Map cache = new HashMap();

          public static int fibonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(cache.get(n) != null) return (int) cache.get(n); int a = fibonacci(n-1); int b = fibonacci(n-2); cache.put(n-1,a); return a+b; }

    • + 0 comments

      Here was my idea which is similar, but easier to read/remember because it's more mechanical--the modulo math is removed, and instead an extra copy operation is used to keep the array ordered newest-to-oldest. Special case 0 and start the loop at 1.

      public static int Fibonacci(int n) {
              if (n == 0) {
                  return 0;
              }
              
              int[] answers = new int[] { 0, 1 };
              for (int ii = 1; ii < n; ii++) {
                  answers[1] = answers[0] + (answers[0] = answers[1]);
              }
              return answers[1];
          }
      
    • + 0 comments

      I am not able to get this.... n%2 is either equal to 1 or 0. which means that the function will return value either 1 or 0 for any fibonacci n.

    • + 0 comments

      This is cool.

    • + 0 comments

      without a loop in C#, so O(1) time and complexity https://math.stackexchange.com/questions/90821/how-to-find-the-closed-form-to-the-fibonacci-numbers

      using System;
      using System.Collections.Generic;
      using System.IO;
      
      class Solution {
      
          public static int Fibonacci(int n) {
              double sqrt_5 = Math.Sqrt(5);
              double inv_sqrt_5 = 1 / sqrt_5;
              double part_one = inv_sqrt_5 * Math.Pow((1 + sqrt_5) / 2, n);
              double part_two = inv_sqrt_5 * Math.Pow((1 - sqrt_5) / 2, n);
              return Convert.ToInt32(part_one - part_two);
          }
      
              static void Main(String[] args) {
                      int n = Convert.ToInt32(Console.ReadLine());
                      Console.WriteLine(Fibonacci(n));
              }
      }
      
    • + 0 comments

      Reread the specifications. You have to solve it recursively calling fibonacci.