Bifalgorithm post · Computer science one · Recursion

How is memoization implemented for recursive Fibonacci in C?

How is memoization implemented for recursive Fibonacci in C? (Computer science one · Recursion) — "C is not a language that provides implicit memoization. Inst…

Ideas in this flowchart

C requires explicit memoization using a table.
C does not provide implicit memoization.
Memoized values must be tracked explicitly in a table.
The table is passed to the function as an argument.
The fibonacciMemoization function demonstrates this approach.
If n is negative, the function returns 0.
If n is at most 1, the function returns 1.
If table[n] already contains a positive value, that value is returned.
Otherwise, the function recursively computes the values for n - 1 and n - 2.
The computed result is stored in table[n] and returned.
The calling function must ensure that the table is large enough.
To compute the n-th Fibonacci number, the table must have at least n + 1 elements.

Bifalgorithm

Feed/

How is memoization implemented for recursive Fibonacci in C?

No cover

Channel

Computer science one

1 page

sam23

Ebook2w

"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."

Flowchart preview

👍

0 comments0 shares