Enhancing Recursive Function Efficiency with Memoization
Recursive functions call themselves and may suffer from performance issues due to repeated calculations.
To address this problem, the memoization technique is employed.
What is Memoization?
Memoization is a technique that stores the return values of a function so that when the function is called again with the same input, it can return the stored value instead.
It avoids redundant calculations by caching function results, thereby improving execution speed.
def fibonacci(n):
# Create an empty dictionary for memoization
memo = {}
def helper(x):
# Return stored value if it has already been calculated
if x in memo:
return memo[x]
# Base case: return x for 0 or 1
if x <= 1:
return x
# Store the calculation result in the memoization dictionary
memo[x] = helper(x - 1) + helper(x - 2)
return memo[x]
# Call the recursive function
return helper(n)
# Print the 10th Fibonacci number
print(fibonacci(10))
# 55
In the code above, the memo dictionary is used to store previously calculated values, and if a value has already been calculated, the stored value is returned.
The values stored in the dictionary represent the results of the Fibonacci sequence for the given n.
{
2: 1,
3: 2,
4: 3,
5: 5,
6: 8,
7: 13,
8: 21,
9: 34,
10: 55
}
Using memoization can significantly improve the execution speed of a function by avoiding redundant calculations, thus enhancing performance.
However, since additional memory is required to store the calculation results, It's important to consider memory usage when applying memoization.
Want to learn more?
Join CodeFriends Plus membership or enroll in a course to start your journey.