How to "remember" previously calculated values in an expensive recursive function in react?

Question

Suppose I have a recursive callback such as this (but more complex):

const weightedFactorial = useCallback(n => {
  if (n === 0) {
    return 1;
  }

  return weight * n * weightedFactorial(n - 1);
},[weight]);

Is there a way to store previously calculated values, such that if the function is called on a repeated index, it is possible to skip the recursion?

const value1 = weightedFactorial(60) 
// Calculate recursively

const value2 = weightedFactorial(30) 
// This value should already be known 
// and the calculation should be skipped

I've tried to keep a state with known values but I seem to get stuck in a loop, probably because it needs to be a dependency of the callback,

const [knownValues, setKnownValues] = useState([{ n: 0, value: 1 }]);
const weightedFactorial = useCallback(n => {
  const known = knownValues.find(known => known.n === n);
  if (known?.value) {
    return known.value;
  }

  const newValue = weight * n * weightedFactorial(n - 1);
  setKnownValues(knownValues => [...knownValues, { n, value: newValue }]);
  return newValue;
},[knownValues, weight]);

Don't use a state. Use a ref. And make it either a simple array or a `Map` in which you can lookup by index. — Bergi, Oct 28 '21 at 21:20
Doesn't look like a good use case for `useCallback()` (because, it is not guaranteed that all previously _remembered_ values are still accessible, in the first place). That rather seems to be a dynamic programming task, but there's no way to suggest some meaningful solution without seeing your actual callback. — Yevhen Horbunkov, Oct 28 '21 at 21:50
@Bergi - Thank you, this is exactly the hint I needed. I also had to add a useEffect to reset the map when some of the dependencies change, but it is working perfectly. Feel free to submit an answer so I can accept it. — Luís Alves, Oct 29 '21 at 09:48
@YevgenGorbunkov - That seems to be why my sample code didn't work, but it is possible with a ref — Luís Alves, Oct 29 '21 at 09:50

Bergi · Accepted Answer · 2021-10-29T12:29:01.823

The easiest way to store results for memoisation is a Map, or an array if your function parameter is a positive integer:

function FactorialExamples(props) {
  const results = [1];
  const factorial = n => {
    if (n in results) return results[n]; // also takes care of our base case n==0
    return results[n] = n * factorial(n-1);
  };
  
  return <p>
    5!: { factorial(5) }
    <br />
    10!: { factorial(10) }
  </p>;
}

This will work nicely and not compute factorials more than once if you call factorial multiple times. However, it will still redo the computation on every rendering of your function component. To persist the results across re-renders, move the results variable out of the function into the module scope, or put it inside a reference (that will be stored once per mounted component):

function Factorial(props) {
  const results = useRef([1]).current;

  const factorial = n => {
    if (n in results) return results[n];
    return results[n] = n * factorial(n-1);
  };

  return <p>
    {props.n}!: { factorial(props.n) }
  </p>;
}

function Demo() {
  const [value, setValue] = useState(0);
  return <div>
    <input type="number" value={value} onInput=(e => setValue(e.currentTarget.valueAsNumber)} min="0" />
    <Factorial n={value} />
  </div>;
}

But you have a more complicated case: the weightedFactorial also depends on a weight state, not just on its argument¹. You could reset the reference every time the weight changes, but that's complicated and error-prone.

Instead, use an approach similar to your useCallback, that switches out the results store together with the "callback". Instead of useCallback, use useMemo and return a closure from it:

const weightedFactorial = useMemo(() => {
  const results = [1];
  return n => {
    if (n in results) return results[n]; 
    return weight * n * weightedFactorial(n - 1);
  };
}, [weight]);

_{1: Of course, you could just treat both weight and n as arguments, and use a standard approach for memoising functions with multiple arguments (see also here). Then the results could again be stored statically or in a reference.}

Wonderfully written, thank you very much. – Luís Alves Oct 29 '21 at 16:46 — Luís Alves, Oct 29 '21 at 16:46

score 0 · Answer 2 · answered Oct 28 '21 at 21:21

0

You can use React.useMemo to calculate the value on the first render or when a dependency changes. But maybe you are referring to memoization so that a previously calculate value doesn't need other computation. https://www.30secondsofcode.org/js/s/memoize or https://www.digitalocean.com/community/tutorials/js-understanding-recursion

You can combine both useMemo and memoization to achieve what you need.

answered Oct 28 '21 at 21:21

Antonio Pantano

4,592
2
23
26

That is not quite what I meant, I need to store the intermediate steps in a recursive function so that subsequent calls to that function don't need to go through the recursion and can simply be looked up. I ended up using a react ref btw – Luís Alves Oct 29 '21 at 09:52
This is exactly what a memoized functions does. It store in its internale cache all the intermediate calculations and when you call it again if found the already calculated value in the cache. – Antonio Pantano Oct 29 '21 at 18:10
Ah, I see now. You are completely correct – Luís Alves Nov 02 '21 at 09:24

How to "remember" previously calculated values in an expensive recursive function in react?

2 Answers2