Recursive Fibonacci memoization

Question

I need some help with a program I'm writing for my Programming II class at universtiy. The question asks that one calculates the Fibonacci sequence using recursion. One must store the calculated Fibonacci numbers in an array to stop unnecessary repeated calculations and to cut down to the calculation time.

I managed to get the program working without the array and memorization, now I'm trying to implement that and I'm stuck. I'm not sure how to structure it. I've Googled and skimmed through some books but haven't found much to help me solve how to implement a solution.

import javax.swing.JOptionPane;
public class question2
{
static int count = 0;
static int [] dictionary;

public static void main(String[] args)
{

int answer;
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:"));

javax.swing.JOptionPane.showMessageDialog(null, 
        "About to calculate fibonacci(" + num + ")");

//giving the array "n" elements
dictionary= new int [num];

if (dictionary.length>=0)
dictionary[0]= 0;

if (dictionary.length>=1)
dictionary[0]= 0;
dictionary[1]= 1;


//method call
answer = fibonacci(num);

//output
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)");
}



  static int fibonacci(int n)
  {
count++;

// Only defined for n >= 0
if (n < 0) {
  System.out.println("ERROR: fibonacci sequence not defined for negative numbers.");
  System.exit(1);
}

// Base cases: f(0) is 0, f(1) is 1
// Other cases: f(n) = f(n-1) + f(n-2)/
if (n == 0) 
{
  return dictionary[0];
}

else if (n == 1) 
{
  return dictionary[1];
}

else
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);
  
 

}

}

The above is incorrect, the end of my fib method is the main problem. I've no idea how to get it to add the numbers recursively to the correctly parts of the array.

You know that setting the values in a loop from the start is much faster than using recursion. I would only use recursion if this is homework and you have to. In fact calculating the largest number you can represent is so fast this way, it is likely to don't need to remember values. i.e. it will take much longer just to draw the result on the screen. — Peter Lawrey, Oct 24 '11 at 13:12
How I would love that....It's specific to the question to use recursion though. Some way of teaching us how it works I guess. — Eogcloud, Oct 24 '11 at 13:42
BTW the term is [memoization](http://en.wikipedia.org/wiki/Memoization), not memorization. — Miserable Variable, Oct 24 '11 at 14:40

score 26 · Accepted Answer · answered Oct 24 '11 at 12:15

26

You need to distinguish between already calculated number and not calculated numbers in the dictionary, which you currently don't: you always recalculate the numbers.

if (n == 0) 
{
  // special case because fib(0) is 0
  return dictionary[0];
}
else 
{
  int f = dictionary[n];
  if (f == 0) {
    // number wasn't calculated yet.
    f = fibonacci(n-1) + fibonacci(n-2);
    dictionary[n] = f;
  }
  return f;
}

answered Oct 24 '11 at 12:15

Joachim Sauer

302,674
57
556
614

Thank you for this, I was looking at it for an hour and couldn't determine what I was doing wrong or how I could fix it. Is there any real need for the special case as I've defined fib(1) and fib(0) in the Main method? – Eogcloud Oct 24 '11 at 12:20
3

@Eogcloud: the special case is necessary as fib(0) and fib(1) can't be caclculated with the code in the general case (as fib(-2) and fib(-1) are undefined!). You could replace the special case with `if (n < 2) { return n; }` to avoid the array lookup. – Joachim Sauer Oct 24 '11 at 12:33

score 13 · Answer 2 · edited Feb 18 '18 at 14:02

13

public static int fib(int n, Map<Integer,Integer> map){

    if(n ==0){
        return 0;
    }

    if(n ==1){
        return 1;
    }

    if(map.containsKey(n)){
        return map.get(n);
    }

    Integer fibForN = fib(n-1,map) + fib(n-2,map);
    map.put(n, fibForN);

    return fibForN; 

}

Similar to most solutions above but using a Map instead.

edited Feb 18 '18 at 14:02

AlexMelw

2,406
26
35

answered Sep 09 '16 at 06:10

user3403187

129
1
2

Using a Map definitely works; however, I would try to avoid adding unnecessary complexity into code. An array containing integers as elements can be considered to be a mapping from an index into an associated integer. – Adam Bak Jul 25 '17 at 00:09
I like his approach better – Anthony Moon Beam Toorie Apr 11 '20 at 11:51

Rohit · Answer 3 · 2013-11-10T19:54:42.280

Program to print first n fibonacci numbers using Memoization.

int[] dictionary; 
// Get Fibonacci with Memoization
public int getFibWithMem(int n) {
    if (dictionary == null) {
        dictionary = new int[n];
    }

    if (dictionary[n - 1] == 0) {
        if (n <= 2) {
            dictionary[n - 1] = n - 1;
        } else {
            dictionary[n - 1] = getFibWithMem(n - 1) + getFibWithMem(n - 2);
        }
    }

    return dictionary[n - 1];
}

public void printFibonacci()
{
    for (int curr : dictionary) {
        System.out.print("F[" + i++ + "]:" + curr + ", ");
    }
}

score 4 · Answer 4 · answered Nov 22 '15 at 01:21

Here is my implementation of recursive fibonacci memoization. Using BigInteger and ArrayList allows to calculate 100th or even larger term. I tried 1000th terms, and result is returned in a matter of milliseconds, here is the code:

    private static List<BigInteger> dict = new ArrayList<BigInteger>();
    public static void printFebonachiRecursion (int num){
    if (num==1){
        printFebonachiRecursion(num-1);
        System.out.printf("Term %d: %d%n",num,1);
        dict.add(BigInteger.ONE);
    }
    else if (num==0){
        System.out.printf("Term %d: %d%n",num,0);
        dict.add(BigInteger.ZERO);
    }
    else {
    printFebonachiRecursion(num-1);
    dict.add(dict.get(num-2).add(dict.get(num-1)));
    System.out.printf("Term %d: %d%n",num,dict.get(num));
    }
}

Output example

printFebonachiRecursion(100);

Term 0: 0
Term 1: 1
Term 2: 1
Term 3: 2
...
Term 98: 135301852344706746049
Term 99: 218922995834555169026
Term 100: 354224848179261915075

score 4 · Answer 5 · answered Oct 24 '11 at 12:15

I believe you forget to actually look up stuff in your dictionary.

Change

else
    return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);

to

else {
    if (dictionary[n] > 0)
        return dictionary[n];

    return dictionary[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

and it works just fine (tested it myself :)

AlexMelw · Answer 6 · 2018-02-19T19:55:55.843

Here is a fully-fledged class that leverages the memoization concept:

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    public static Fibonacci getInstance() {
        return new Fibonacci();
    }

    public int fib(int n) {
        HashMap<Integer, Integer> memoizedMap = new HashMap<>();

        memoizedMap.put(0, 0);
        memoizedMap.put(1, 1);

        return fib(n, memoizedMap);
    }

    private int fib(int n, Map<Integer, Integer> map) {
        if (map.containsKey(n))
            return map.get(n);

        int fibFromN = fib(n - 1, map) + fib(n - 2, map);

        // MEMOIZE the computed value
        map.put(n, fibFromN);

        return fibFromN;
    }
}

Notice that

memoizedMap.put(0, 0);
memoizedMap.put(1, 1);

are used to eliminate the necessity of the following check

if (n == 0) return 0;
if (n == 1) return 1;

at each recursive function call.

score 1 · Answer 7 · answered Aug 22 '12 at 20:54

int F(int Num){
int i =0;
int* A = NULL;
if(Num > 0)
{
 A = (int*) malloc(Num * sizeof(int));
}
else
 return Num;

for(;i<Num;i++)
 A[i] = -1;

return F_M(Num, &A);


}

int F_M(int Num, int** Ap){
int Num1 = 0;
int Num2 = 0;

if((*Ap)[Num - 1] < 0)
{
  Num1 = F_M(Num - 1, Ap);
  (*Ap)[Num -1] = Num1;
  printf("Num1:%d\n",Num1);
}
else
  Num1 = (*Ap)[Num - 1];

if((*Ap)[Num - 2] < 0)
{
  Num2 = F_M(Num - 2, Ap);
  (*Ap)[Num -2] = Num2;
  printf("Num2:%d\n",Num2);
}
else
  Num2 = (*Ap)[Num - 2];

if(0 == Num || 1 == Num)
{
 (*Ap)[Num] = Num;
 return Num;
}
else{
//  return ((*Ap)[Num - 2] > 0?(*Ap)[Num - 2] = F_M(Num -2, Ap): (*Ap)[Num - 2]  ) +     ((*Ap)[Num - 1] > 0?(*Ap)[Num - 1] = F_M(Num -1, Ap): (*Ap)[Num - 1]  );
  return (Num1 + Num2);
}

}

int main(int argc, char** argv){
int Num = 0;
if(argc>1){
sscanf(argv[1], "%d", &Num);
}

printf("F(%d) = %d", Num, F(Num));

return 0;

}

score 1 · Answer 8 · answered Apr 25 '15 at 12:52

This is another way to approach memoization for recursive fibonacci() method using a static array of values -

public static long fibArray[]=new long[50];\\Keep it as large as you need

public static long fibonacci(long n){
long fibValue=0;
if(n==0 ){
    return 0;
}else if(n==1){
    return 1;
}else if(fibArray[(int)n]!=0){
    return fibArray[(int)n];    
}
else{
    fibValue=fibonacci(n-1)+fibonacci(n-2);
    fibArray[(int) n]=fibValue;
    return fibValue;
}
}

Note that this method uses a global(class level) static array fibArray[]. To have a look at the whole code with explanation you can also see the following - http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

Naren · Answer 9 · 2019-04-11T17:10:29.890

import java.util.HashMap;
import java.util.Map;

public class FibonacciSequence {

    public static int fibonacci(int n, Map<Integer, Integer> memo) {
        if (n < 2) {
            return n;
        }
        if (!memo.containsKey(n)) {
            memo.put(n, fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
        }
        return memo.get(n);
    }

    public static int fibonacci(int n, int[] memo) {
        if (n < 2) {
            return n;
        }
        if (memo[n - 1] != 0) {
            return memo[n - 1];
        }
        return memo[n - 1] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    }

    public static void main(String[] s) {
        int n = 10;

        System.out.println("f(n) = " + fibonacci(n, new HashMap<Integer, Integer>()));
        System.out.println("f(n) = " + fibonacci(n, new int[n]));
    }
}

score 0 · Answer 10 · answered Nov 17 '20 at 12:29

In Swift 5.3

This is a very quick one using memoisation. First I initialise my cache dictionary.

var cache = [Int:Int]()

Then I create my Fibonacci number generator. Since it is a recursive function, every call to the function would theoretically compute the whole Fibonacci sequence again up to the requested number. This is why we use the cache, to speed up the recursive function:

func fibonacci(_ number: Int) -> Int {
    // if the value is in the dictionary I just return it
    if let value = cache[number] { return value }

    // Otherwise I calculate it recursively. 
    // Every recursion will check the cache again, 
    // this is why memoisation is faster!
    let newValue = number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
    cache[number] = newValue
    return newValue
}

I can save my sequence in an array like this:

var numbers = Array(0..<10).map(fibonacci) //[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Or use the function in a loop.

score 0 · Answer 11 · answered Jun 17 '21 at 05:38

using System; using System.Collections.Generic;

namespace Fibonacci { public class FibonacciSeries {

        static void Main(string[] args)
    {
        int n;
        Dictionary<int, long> dict = new Dictionary<int, long>();
        Console.WriteLine("ENTER NUMBER::");
        n = Convert.ToInt32(Console.ReadLine());
        for (int j = 0; j <= n; j++)
        {
            Console.WriteLine(Fib(j, dict));
        }
    }

   

    public static long Fib(int n, Dictionary<int, long> dict)
    {
        if (n <= 1)
            return n;
        if (dict.ContainsKey(n))
            return dict[n]; 
       
        var value = Fib(n - 1,dict) + Fib(n - 2,dict);
        dict[n] = value;
        return value;
    }

}

}

score -1 · Answer 12 · answered Oct 23 '19 at 18:41

Might be too old but here is my solution for swift

class Recursion {
    func fibonacci(_ input: Int) {
        var dictioner: [Int: Int] = [:]
        dictioner[0] = 0
        dictioner[1] = 1
       print(fibonacciCal(input, dictioner: &dictioner))
    }

    func fibonacciCal(_ input: Int, dictioner: inout [Int: Int]) -> Int {
        if let va = dictioner[input]{
            return va
        } else {
            let firstPart = fibonacciCal(input-1, dictioner: &dictioner)

            let secondPart = fibonacciCal(input-2, dictioner: &dictioner)

            if dictioner[input] == nil {
                dictioner[input] = firstPart+secondPart
            }

            return firstPart+secondPart
        }
    }
}

// 0,1,1,2,3,5,8
class TestRecursion {
    func testRecursion () {
        let t = Recursion()
        t.fibonacci(3)
    }
}

score -1 · Answer 13 · edited Jun 03 '20 at 11:13

public class FiboSeries {

    // first two terms of Fibonacci
    int x1 = 0;
    int x2 = 1;
    long xn; // nth number in Fibo series
    long[] array; // an array for implementing memoization

    // print the Nth number of Fibonacci - logic is f(n) = f(n-1) + f(n-2)

    long fibo(int n) {

        // initialize the array having n elements if it does not exist already
        if (array == null) {

            array = new long[n + 1];

        }

        // Fetch the memoized value from the array instead of recursion
        // for instance, fibo(3) will be calculated just once and stored inside this
        // array for next call
        if (array[n] != 0)

        {
            xn = array[n];
            return xn;
        }

        // value of fibo(1)
        if (n == 1) {
            xn = x1;

        }

        // value of fibo(2)
        if (n == 2) {
            xn = x2;

        }

        // value of Fibo(n) using non linear recursion
        if (n > 2) {

            xn = fibo(n - 1) + fibo(n - 2);
        }

        // before returning the value - store it at nth position of an array
        // However, before saving the value into array, check if the position is already 
        //full or not

        if (array[n] == 0) {

            array[n] = xn;
        }

        return xn;

    }

    public static void main(String[] args) {

        FiboSeries f = new FiboSeries();

        int n = 50;
        long number = f.fibo(n);

        System.out.println(number);

    }


}

While this code may solve the question, [including an explanation](https://meta.stackexchange.com/q/114762) of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please [edit] your answer to add explanations and give an indication of what limitations and assumptions apply. — David Buck, Jun 03 '20 at 11:13

score -2 · Answer 14 · answered Mar 17 '18 at 21:07

-2

#include <stdio.h>
long int A[100]={1,1};
long int fib(int n){
    if (A[n])
    {
        return A[n];
    }
    else
    {
         return A[n]=fib(n-1)+fib(n-2);
    }
}
int main(){
    printf("%ld",fib(30));
}

answered Mar 17 '18 at 21:07

MAHDI AKBARIZARKESH

23
5

Please add more explanation. – laughing Nov 12 '22 at 00:41

Lin Endian · Answer 15 · 2018-09-26T16:04:51.990

-2

Here is my implementation.

private static int F(int N, int[] A) {
    if ((N == 0) || (N == 1)) return N;
    if (A[N] != 0) return A[N];

    if ((A[N - 1] != 0) && (A[N - 2] != 0)) {
        A[N] = A[N - 1] + A[N - 2];
        return A[N];
    }

    if (A[N-2] != 0) {
        A[N] = A[N - 2] + F(N - 1, A);
        return A[N];
    }
    if (A[N-1] != 0) {
        A[N] = A[N - 1] + F(N - 2, A);
        return A[N];
    }
    A[N] = F(N-1, A) + F(N-2, A);
    return A[N];
}

edited Sep 26 '18 at 16:04

answered Sep 26 '18 at 15:51

Lin Endian

93
3
9

I would definitely not call methods "F" or arguments N or A, it isn't very clear to others trying to read it. – Eogcloud Oct 04 '18 at 14:59
F is Fibonacci, N is the standard math convention for a natural number > 0. A is an array. The choices are not unreasonable unless one does not have a math or CS background. – Lin Endian Oct 06 '18 at 01:59
naming convention should be followed so that others can learn. This is not competition, therefore is no need to use shortcuts. – laughing Nov 12 '22 at 00:40

Recursive Fibonacci memoization

15 Answers15

In Swift 5.3

Linked