CODEWITHSUNDEEP
javaalgorithm
Marz
Marz

Reputation: 263

Fibonacci function result confusion

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }
}

Let's assume that the user input "java Fibonacci 7", so the result would be like this:

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13

I seem to be totally confused with how this works, starting with argument 3. When the fib(i) method gets passed 3, shouldn't it return 3 as well since if n = 3 then the sum of fib(n-1) /n-1 is 2/ and fib(n-2) /n-2 is 1/ is 3. And so on the other numbers forward.

Upvotes: 3

Views: 56628

Answers (22)

ankit singh
ankit singh

Reputation: 1

We can do it using Java8 in much simpler ways as below.

Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
            .limit(10)
            .map(t -> t[0])
            .forEach(System.out::print);

Upvotes: 0

David William
David William

Reputation: 101

import java.util.*;

public class FibonacciSeries {


public static void main(String[] args) {
int x=0;
int y=1;
Scanner in= new Scanner(System.in);
System.out.println("Enter number of series you want?");
//user will enter a number
int z=in.nextInt();
System.out.print(x+" "+y+" ");
while((z-2)>0)
{
int a=x+y;
System.out.print(a+" ");
x=y;
y=a;
z--;
}
}

}

Upvotes: 0

Arvind Kumar Avinash
Arvind Kumar Avinash

Reputation: 78975

To understand the code in your question, I recommend you first understand the concept of the Fibonacci sequence, in which each number is the sum of the two preceding ones. The accepted answer has explained nicely how the recursive calls are generating the sequence.

I am writing this answer to show the use of Java-8 Stream API to generate a Fibonacci sequence.

Java-8 Stream API Solution

import java.util.stream.Stream;

public class Solution {
    public static void main(String[] args) {
        int maxSize = 7;
        Stream.iterate(new int[] { 1, 1 }, arr -> new int[] { arr[1], arr[0] + arr[1] })
                .map(arr -> arr[0])
                .limit(maxSize)
                .forEach(System.out::println);
    }
}

Output:

1
1
2
3
5
8
13

Explanation

  1. Here, we are limiting the infinite sequential ordered Stream returned by Stream#iterate with the help of Stream#limit.
  2. We are using new int[] { 1, 1 } as a seed where the first and second elements represent the first and second numbers in the Fibonacci sequence. If you want to start the sequence with 0, you will use new int[] { 0, 1 }.
  3. Out of the array of the two elements, we are getting the first element by mapping the array into its first element and then printing it.
  4. The UnaryOperator is preparing a new array for the next iterations.

Upvotes: 0

Maninder
Maninder

Reputation: 1919

package Loops;
import java.util.Scanner;
public class FibonacciClass {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        System.out.println("Enter the number upto which you want to generate Fibonacci series");
        int x= sc.nextInt();
        int [] testing= new int[x];
        int first_Value=0;
        int second_value=1;
        int third_value=0;
        System.out.println(first_Value);
        for(int i=1;i<testing.length;i++){
            first_Value=second_value;
            second_value=third_value;
            third_value=first_Value+second_value;
            System.out.println(third_value);
            }
        }
        }

Upvotes: 0

Meysam Keshvari
Meysam Keshvari

Reputation: 1201

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89

public void fibonacci(){
    int n1 = 0;
    int n2 = 1;
    int n3;
    int count = 10;
    Log.d("DBG",n1 + " , " + n2);
    for (int i = 1; i <= count ; i++) {
        n3 = n1 + n2;
        Log.d("DBG",i + "= " + n3+"");
        n1 = n2;
        n2 = n3;
    }
}

Upvotes: 0

David William
David William

Reputation: 101

import java.util.Scanner;
public class Fibonacci {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System. in );
        System.out.println("Enter a number upto which fibonacci numbers should be displayed");
        int fib = scn.nextInt();
        int a = 0,
        b = 1,
        res = 0;
        System.out.print(a + " " + b + " ");
        while (res <= fib) {
            res = a + b;
            a = b;
            b = res;
            if (res > fib) break;
            System.out.print(res + " ");
        }
    }
}

Upvotes: 0

Chris Michael
Chris Michael

Reputation: 329

This is my dynamic programming implementation using BigInteger.

   import java.math.BigInteger;
   import java.util.HashMap;
   import java.util.Map;
   import java.util.Scanner;

/**
 * Topic: Dynamic Programming
 * Algorithm: Fib Algorithm Implementation
 *
 * Author: Chris M. Perez Santiago
 * Date: 4 / 15 / 2018
 **/


  public class Main {
     private static BigInteger[] b = new BigInteger[100000001];
     private static Scanner console = new Scanner(System.in);

  public static void main(String[] args) {
     long n = console.nextLong();
     for(long i=1;i<=n;i++) System.out.println(initFib(i));
  }

  private static BigInteger dpFib(Map<Long , BigInteger> map , long n){
     if(map.containsKey(n)) return map.get(n);

     map.put(n - 1 , dpFib(map , n - 1));
     map.put(n - 2 , dpFib(map , n - 2));
     BigInteger sum = map.get(n - 1).add(map.get(n - 2));
     map.put(n , sum);
     return sum;
  }

  private static BigInteger initFib(long n){
     if(BigInteger.valueOf(n).equals(BigInteger.ONE) || BigInteger.valueOf(n).equals(BigInteger.ZERO))
       return BigInteger.ONE;
     Map<Long , BigInteger> map = new HashMap<>();
     map.put(1L , BigInteger.ONE);
     map.put(2L , BigInteger.ONE);
     return dpFib(map , n);
  }
}

Upvotes: 0

alexandru catanet
alexandru catanet

Reputation: 87

Why you don't use the next formula:

private static int fibonacci(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Upvotes: 0

toludav
toludav

Reputation: 31

The method below returns the fibonacci number at index n. 

 public static long getFibonacci(int n) {
            List<Long> fibonacciNumbers = new ArrayList();
            long j = 0;
            int k = 0;
            for (int i = 0; i <= n; i++) {
                System.out.println("i = " + i);
                if (i == 2) {
                    j += (i - 2);
                } else if (i > 2) {
                    j = fibonacciNumbers.get(i - 1) + fibonacciNumbers.get(k - 2);
                } else {
                    j += i;
                }
                fibonacciNumbers.add(j);
                k++;
                System.out.println("Fibonacci Array = " + Arrays.toString(fibonacciNumbers.toArray()));
            }
            return fibonacciNumbers.get(fibonacciNumbers.size() - 1);
        }

Upvotes: 0

codebusta
codebusta

Reputation: 2053

public static int f(int n){
    if (n <= 1) {
        return n;
    } else {
        return f(n - 1) + f(n - 2);
    }
}

public static void main(String[] args){
    Integer c = 4;
    Integer answer = f(c);
    System.out.println("Fibonacci " + c + "'s number is: " + answer);
}

Upvotes: 2

Ihor Rybak
Ihor Rybak

Reputation: 3279

My solution using Java 8 Stream:

public class Main {
    public static void main(String[] args) {
        final int n = 7;
        Fibonacci fibonacci = new Fibonacci();
        Stream.generate(fibonacci::next)
                .limit(n)
                .forEach(System.out::println);
    }
}

public class Fibonacci {
    private long next = 1;
    private long current = 1;
    private int count = 1;

    public FibonacciNumber next() {
        FibonacciNumber fibonacciNumber = new FibonacciNumber(count++, current);
        long previous = current;
        current = next;
        next = current + previous;
        return fibonacciNumber;
    }
}

public class FibonacciNumber {
    private final int count;
    private final long value;

    public FibonacciNumber(int count, long value) {
        this.count = count;
        this.value = value;
    }

    @Override
    public String toString() {
        return count + ": " + value;
    }
}

Upvotes: 2

Olu
Olu

Reputation: 1

import java.math.BigDecimal;

public abstract class Fibonacci {

    public static void main(String[] args) {
        Integer max = Integer.valueOf(args[0]);
        BigDecimal[] fibs = { new BigDecimal(0), new BigDecimal(1) };
        BigDecimal current;
        System.out.print("1 ");
        for (int i = 0; i < max + 1; i++) {
            current = fibs[1].add(fibs[0]);
            System.out.print(current + " ");
            fibs[0] = fibs[1];
            fibs[1] = current;
        }
    }
}

Upvotes: 0

morphytronx
morphytronx

Reputation: 113

You can do it in two lines!

Shortest typing to do this (albeit, not the most efficient):

    int fib( int x ) {
        return x > 1 ? fib(x - 1) + fib(x - 2) : x; }

If you want a fast algorithm, give this one a shot:

        ///fast version fibbonacci sequence.
        public static float fibonacci(int x){
           float[] sequence = new float[x];
           sequence[0] = 1;
           sequence[1] = 1;
          if (x > 1){
             for (int i = 2; i < x; i++){
               sequence[i] = sequence[i-1] + sequence[i-2];
             }
          }
          for (float z : sequence){
              System.out.print("{ " + z + "}, ");
          }
          return sequence[x-1];
        }

Upvotes: 1

J.K
J.K

Reputation: 2393

This is a much simpler code to generate Fibonacci sequence like '0 1 1 2 3 ...'.

public static void main (String[] args) {
    int f = 0;
    int g = 1;

    for (int i = 1; i <= 10; i++) {
        System.out.print(f + " ");
        f = f + g;
        g = f - g;
    } 

    System.out.println();
}

Upvotes: 15

Mcfaith
Mcfaith

Reputation: 275

import java.util.Scanner;

public class Fibonacci2 {

    public static void main(String[]args){

        int a;
        try (Scanner sc = new Scanner(System.in)) {
            System.out.print("Number of Fibonacci numbers to print: ");
            a = sc.nextInt();
            sc.close();
        }
        int c=1; /*c current number b last number*/
        int b=0;
        System.out.println(b);
        System.out.println(c);
        int bb;
        for (int z = 2; z < a ; z++){
        bb = b; 
        b = c;
        c = bb + b; /*bb last last number*/
        System.out.println(z);

    }
    }
}

Upvotes: -2

Milaci
Milaci

Reputation: 515

Is a Recursion method... fib(3)=fib(3-1)+fib(3-2)= fib(2)+fib(1)=(fib(2-1)+fib(1-1))+fib(1)= fib(1)+fib(0)+fib(1)= 1 + 0 + 1

Upvotes: 0

Amandeep Kamboj
Amandeep Kamboj

Reputation: 161

                           F(n)
                            /    \
                        F(n-1)   F(n-2)
                        /   \     /      \
                    F(n-2) F(n-3) F(n-3)  F(n-4)
                   /    \
                 F(n-3) F(n-4)

Notice that many computations are repeated! Important point to note is this algorithm is exponential because it does not store the result of previous calculated numbers. eg F(n-3) is called 3 times.

For more details refer algorithm by dasgupta chapter 0.2

Upvotes: 2

Imtiaz Zaman Nishith
Imtiaz Zaman Nishith

Reputation: 490

Fibonacci numbers are the calculated sum of previous consecutive two numbers. It starts with 0 1 1 2 3 5 8... and so on. So its something like--

fib(3) = fib(2) + fib(1)
       = fib(1) + fib(0) + 1 //fib(1) = 1
       = 1 + 0 + 1 //fib(0) = 0
       = 2

Recursion method is less efficient as it involves function calls which uses stack, also there are chances of stack overflow if function is called frequently for calculating larger Fibonacci numbers.

Upvotes: 1

Christopher Gertz
Christopher Gertz

Reputation: 2026

The Fibonacci series either starts with zero or with 1, non of which options has the 3 as the third number.

1 1 2 3 5 ...

0 1 1 2 3 5 8 ...

The usual way is to have the second option but starting at index 0 so that fib(0) = 0, fib(1) = fib(2) = 1, as stated for example here: http://oeis.org/A000045

Upvotes: 0

Alex VII
Alex VII

Reputation: 930

If you pass 3 to your function it will do the following:

fib(3) = fib(2) + fib(1) //so we we are into the else statement, because 3 > 1
= fib(2) + 1             //fib(1) = 1 because 1 <= 1 so you return it (if statement)
= (fib(1) + fib(0)) + 1  //2 > 1 => we go to the else statement
= (1 + 0) + 1            //0 <= 1 & 1 <= 1 so we are into the if and return the values 
= 2

Upvotes: 4

Bhushankumar Lilapara
Bhushankumar Lilapara

Reputation: 780

why dont you try this easy code. It's same like we do in Fibonacci without recursion.

public class FinnonnacciDemo2 {

    static int no = 0, n = 8;

    public static void main(String[] args) {
        // This will print series till 8
        fib(0, 1);
    }

    public static void fib(int a, int b) {
        // Terminating condition.
        if (a >= n) {
            return;
        }

        else {
            System.out.print("\t" + no);
            no = a + b;
            a = b;
            b = no;
            fib(a, b);
        }
    }
}

Upvotes: 1

hoekki
hoekki

Reputation: 238

I think you are confusing the index (n) in the Fibonacci sequence with the actual value at that index. fib(n=3) = fib(n-1=2) + fib(n-2=1) = 1 + 1 = 2

Upvotes: 1

Related Questions