Creating memorization algorithm given a fibonacci recursive function

Question

For a school assignment, we have to create a memorized fibonacci function that reuses the recursive implementation of computing the fibonacci.

What is a good way to design our memorized function such that it takes advantage of an already existing function? This is my implementation so far:

Base class:

    public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }
        return computeFibonacci(position - 1) + computeFibonacci(position - 2);
    }

Inherited class:

    public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }

        if (this.memoizedList.containsKey(position)) {
            return this.memoizedList.get(position);
        }
        int result = super.computeFibonacci(position - 1) + super.computeFibonacci(position - 2);
        this.memoizedList.put(position, result);
        return result;
    }

you wanna read this post for optimal solution - geeksforgeeks.org/… — roottraveller
– roottraveller, Commented Nov 6, 2019 at 6:48
You don't need to call super implementation. If you call super implementation then you won't be able to make use of memoized values. — vaibhavatul47
– vaibhavatul47, Commented Nov 6, 2019 at 11:43

Tttttsing · Accepted Answer · 2019-11-06 11:18:09Z

2

There is a confusion about reusing the recursive implementation in Base Class. If you call the recursive implementation, it will recursively calculate fib(n) = fib(n-1) + fib(n-2) = ..., which is conflict with memo function. Memo function tries to save time for calculated ones. For memo:

public int computeFibonacci(int position) {
        assertPosition(position);

        if (position < 2) {
            return 1;
        }

        if (this.memoizedList.containsKey(position)) {
            return this.memoizedList.get(position);
        }
        int result = computeFibonacci(position - 1) + computeFibonacci(position - 2);
        this.memoizedList.put(position, result);
        return result;
    }

For example, you try to print the first 1000 elements in fibonacci, memo function will save time on calculated ones.

answered Nov 6, 2019 at 11:18

Tttttsing

1051 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Eran · Accepted Answer · 2019-11-06 06:51:20Z

1

Your sub-class version doesn't take full advantage of the cached values. For example, if you call computeFibonacci(5), and memoizedList doesn't contain that key, you would call super.computeFibonacci(4) and super.computeFibonacci(3) even if they are already cached. Instead, you should call super.computeFibonacci(5).

public int computeFibonacci(int position) {
    assertPosition(position);

    if (position < 2) {
        return 1;
    }

    if (this.memoizedList.containsKey(position)) {
        return this.memoizedList.get(position);
    } else {
        int result = super.computeFibonacci(position);
        this.memoizedList.put(position, result);
        return result;
    }
}

answered Nov 6, 2019 at 6:51

Eran

395k57 gold badges726 silver badges793 bronze badges

3 Comments

Joop Eggen Over a year ago

Note that this function does not reimplement the original computeFibonacci. If reimplementing the original function is superfluous.

Eran Over a year ago

@JoopEggen I'm not sure what you mean by that. My suggestion for the sub-class's computeFibonacci obtains the value stored in the cache (if available) or calls the super class implementation otherwise.

Joop Eggen Over a year ago

Oh it was praise in a way, as the OP repeated the implementation of the original method. Your answer is halfways to a general solution for memoisation.

Collectives™ on Stack Overflow

Creating memorization algorithm given a fibonacci recursive function

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related