DEV Community

Discussion on: Recursion, or How I Learned to Stop Thinking and Love the Thoughts

Collapse
peerreynders profile image
peerreynders
  1. Study the original function.

    function factorial(n) {
      return n > 1 ? n * factorial(n - 1) : 1;
    }
    
    console.log(factorial(5)); // 120
    
  2. Convert recursive calls into tail calls

    function factorial(n, result = 1) {
      return n > 1 ? factorial(n - 1, result * n) : result;
    }
    
    console.log(factorial(5)); // 120
    
  3. Introduce a one-shot loop around the function body.

    function factorial(n, result = 1) {
      while (true) {
        return n > 1 ? factorial(n - 1, result * n) : result;
        break;
      }
    }
    
    console.log(factorial(5)); // 120
    
  4. Replace all recursive tail calls f(x=x1, y=y1, ...) with [x, y, ...] = [x1, y1, ...]; continue.

    function factorial(n, result = 1) {
      while (true) {
        if (!(n > 1)) return result;
        [n, result] = [n - 1, result * n];
        continue;
        break;
      }
    }
    
    console.log(factorial(5)); // 120
    
  5. Tidy up

    function factorial(n) {
      let result = 1;
      while (n > 1)
         [result, n] = [result * n, n - 1];
    
      return result;
    }
    
    console.log(factorial(5)); // 120
    
  6. Make more idiomatic

    function factorial(n) {
      let result = 1;
      for (; n > 1; result *= n, n -= 1);
    
      return result;
    }
    
    console.log(factorial(5)); // 120
    

If you like that rabbit hole take a look at recursion and Recursion? We don't need no stinking recursion!.