We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The problem here is that your fiboAdd has too many unnecessary calculations:
The most serious offender is the fiboEven function. Let's say you calculate fiboEven(10), you recursively call fiboEven(9) and fiboEven(8) but the whole recursive subtree rooted at fiboEven(8) is contained in fiboEven(9). You need memoization. This is the same reasoning as the standard reasoning for why it's good to have memoization for recursive fibonacci series calculation. You don't want a recursion tree (with branching factor a=2) if you can effectively get a recursion list (with branching factor a=1).
The successive fiboEven(i) calls in addFibo(N) are also redundant with the recursion tree for i+1 going through recursion tree for i, even though you just went through it in the previous outer fiboEven call. You need to keep track of the previously calculated fiboEven(i-1) to quickly calculate fiboEven(i).
Also, for each i you call fiboEven(i) in fiboAdd twice: inside if statement and on the next line. So, you can cut you workload in half by saving the result in a variable and reusing.
Personally, I think (bottom-up) iterative approach is a better fit here because you don't need any memoization you just keep the previous fiboEven number, the current fiboEven number and the current sum in memory and that's it.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #2: Even Fibonacci numbers
You are viewing a single comment's thread. Return to all comments →
The problem here is that your fiboAdd has too many unnecessary calculations:
The most serious offender is the fiboEven function. Let's say you calculate fiboEven(10), you recursively call fiboEven(9) and fiboEven(8) but the whole recursive subtree rooted at fiboEven(8) is contained in fiboEven(9). You need memoization. This is the same reasoning as the standard reasoning for why it's good to have memoization for recursive fibonacci series calculation. You don't want a recursion tree (with branching factor a=2) if you can effectively get a recursion list (with branching factor a=1).
The successive fiboEven(i) calls in addFibo(N) are also redundant with the recursion tree for i+1 going through recursion tree for i, even though you just went through it in the previous outer fiboEven call. You need to keep track of the previously calculated fiboEven(i-1) to quickly calculate fiboEven(i).
Also, for each i you call fiboEven(i) in fiboAdd twice: inside if statement and on the next line. So, you can cut you workload in half by saving the result in a variable and reusing.
Personally, I think (bottom-up) iterative approach is a better fit here because you don't need any memoization you just keep the previous fiboEven number, the current fiboEven number and the current sum in memory and that's it.