Concept
How is memoization implemented for recursive Fibonacci in C?
ComputerScienceOne / Recursion
"C is not a language that provides implicit memoization. Instead, we need to explicitly keep track of values using a table. In the following example, the table is passed to the function as an argument.\n\nint fibonacciMemoization(int n, int *table) {\n\nif(n < 0) {\n\nreturn 0;\n\n} else if(n <= 1) {\n\nreturn 1;\n\n} else if(table[n] > 0) {\n\nreturn table[n];\n\n} else {\n\nint a = fibonacciMemoization(n-1, table);\n\nint b = fibonacciMemoization(n-2, table);\n\nint result = (a + b);\n\ntable[n] = result;\n\nreturn result;\n\n}\n\n}\n\nIt is the responsibility of the calling function to ensure that the table array is large enough to accommodate all values. In this case should be at least of size (n + 1) to compute the n-th Fibonacci number."
Related Ideas
- How can Fibonacci numbers be computed recursively in Java?ComputerScienceOne · Recursion
- How can BigInteger be used for large recursive Fibonacci values?ComputerScienceOne · Recursion
- How can recursive functions be written in C?ComputerScienceOne · Recursion
- What does the recursive Fibonacci computation tree show?ComputerScienceOne · A DNA Sequence
- How do recursive Fibonacci functions work with memoization?ComputerScienceOne · Scaling a Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- How is recursion implemented in Java?ComputerScienceOne · Recursion
- What happens when a function calls itself?ComputerScienceOne · Recursion
- Where is section 11.2.1, Memoization, listed?ComputerScienceOne · Avoiding Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .