Benchmark: Recursion vs Iteration (with tail recursion)2

Script Preparation code:

  var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  
  function sum_recurse(arr, i) {
   i = i || 0;
   if (i > arr.length)
     return 0;
   else
     return arr[i] + sum_recurse(arr, i + 1);
  }

 function sum_recurse_tail(arr, i, sum = 0) {
   i = i || 0;
   if (i > arr.length)
     return 0;
	i++;
    sum += arr[i]
   return sum_recurse(arr, i, sum);
  }
  
  function sum_while(arr) {
   var total = 0,
       i = 0,
       len = arr.length;
  
   while (i < len) {
    total += arr[i++];
   }
  
   return total;
  }
  
  function sum_for(arr) {
   var total = 0,
       len = arr.length;
  
   for (var i = 0; i < len; i++) {
    total += arr[i];
   }
  
   return total;
  }

Tests:

recursion
sum_recurse(nums)
while loop
sum_while(nums)
for loop
sum_for(nums)
recurse (tail)
sum_recurse_tail(nums)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
recursion
while loop
for loop
recurse (tail)

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.0 Safari/605.1.15

Browser/OS: Safari 17 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
recursion	1539516.5 Ops/sec
while loop	10713835.0 Ops/sec
for loop	10727867.0 Ops/sec
recurse (tail)	1794756.6 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

LLMs can make mistakes. Check important info.

Let's dive into explaining the benchmark and its various components.

**Benchmark Definition JSON**

The provided JSON represents a JavaScript microbenchmarking framework. It defines two main components:

1. **Script Preparation Code**: This section contains the code that is used to prepare the test environment and generate the benchmark input data.
2. **Html Preparation Code**: This section would typically contain HTML code to set up the testing environment, but it's empty in this case.

The script preparation code defines a function `sum_recurse` with two variants: `sum_recurse` (traditional recursion) and `sum_recurse_tail` (tail recursion). It also defines two other functions: `sum_while` and `sum_for`, which will be used as alternative implementations for the same problem.

**Test Cases**

The test cases are defined in an array of objects, each containing a `Benchmark Definition` property that specifies the function to be tested. In this case, there are four test cases:

1. **recursion**: Tests the traditional `sum_recurse` function.
2. **while loop**: Tests the `sum_while` function.
3. **for loop**: Tests the `sum_for` function.
4. **recurse (tail)**: Tests the `sum_recurse_tail` function.

**Options Compared**

The benchmark compares four different approaches to solving the same problem:

1. **Traditional Recursion (`sum_recurse`)**
2. **Tail Recursion (`sum_recurse_tail`)**
3. **While Loop (`sum_while`)**
4. **For Loop (`sum_for`)**

Each of these approaches has its pros and cons:

* **Traditional Recursion**: Can be elegant and easy to understand, but can lead to stack overflows for large inputs.
* **Tail Recursion**: Avoids stack overflows by reusing the same stack frame, but can be more complex to implement correctly.
* **While Loop**: A simple and efficient approach that avoids recursion overhead, but can be slower than optimized loops.
* **For Loop**: Similar to while loops, but with a fixed number of iterations, making it easier to optimize.

**Library Used**

None, the code is self-contained.

**Special JS Features/Syntax**

There are no special JavaScript features or syntax used in this benchmark. However, it's worth noting that some modern browsers may optimize certain functions (like `sum_recurse_tail`) using specialized optimization techniques, such as tail call elimination.

**Other Alternatives**

If you're interested in alternative approaches to solving the same problem, here are a few options:

1. **Iterative Solutions**: Instead of using loops or recursion, you could use iterative solutions like a linear search or a more complex algorithm.
2. **Functional Programming Approaches**: You could use functional programming techniques like map-reduce or fold to solve the problem.
3. **GPU Acceleration**: For very large inputs, you might consider using GPU acceleration to speed up the computation.

These alternatives would likely require significant changes to the benchmark and its test cases, but could provide interesting insights into different problem-solving approaches.

Related benchmarks:

Recursion vs Iteration (with tail recursion)2 (version: 0)

Comparing performance of: recursion vs while loop vs for loop vs recurse (tail)

Created: 3 years ago by: Guest

Jump to the latest result

recursion

while loop

for loop

recurse (tail)

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):