Recursion efficiency in Julia can be improved using memorization technique to store the values of previously computed functions. The following Fibonacci function below does not employ memorization, please change into a recursive function with memorization: function fib(n) if n==1 return 1 elseif n==2 return 1 elseif n<=0 printstyled("Invalid input",color=:red) return else return fib(n-1)+fib(n-2) end end
Recursion efficiency in Julia can be improved using memorization technique to store the values of previously computed functions. The following Fibonacci function below does not employ memorization, please change into a recursive function with memorization:
function fib(n) if n==1
return 1 elseif n==2
return 1 elseif n<=0
printstyled("Invalid input",color=:red)
return else
return fib(n-1)+fib(n-2) end
end
Input:
- An integer n represents the position of the Fibonacci number to calculate.
1. Create a function fib_memo(n, memo) which takes two arguments:
- n: The position of the Fibonacci number to calculate.
- memo: An array to store previously computed Fibonacci numbers.
2. Check if n is less than or equal to 0:
- If true, print "Invalid input" in red and return.
- If false, continue.
3. Check if n is less than or equal to 2:
- If true, return 1 (Fibonacci base case).
- If false, continue.
4. Check if n is within the range of the memoization array:
a. If true, check if the memoization array at index n is not 0:
i. If true, return the value stored in the memoization array at index n.
ii. If false, recursively call fib_memo(n - 1, memo) and fib_memo(n - 2, memo) to calculate Fibonacci numbers, store the result in the memoization array at index n, and return the result.
b. If false, expand the memoization array by appending zeros to it until it has a length of n, then recursively calculate and store Fibonacci numbers in the memoization array at index n and return the result.
5. Outside the function, set the value of n to the desired Fibonacci number position and initialize the memoization array with [0, 1] (the base cases).
6. Call the fib_memo(n, memo) function and store the result in a variable, e.g., result.
7. Print the result to the console, indicating the position of the Fibonacci number:
- println("Fibonacci number $n is $result").
Step by step
Solved in 4 steps with 2 images
