Benchmark: Recursion vs Iteration (with tail recursion)

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;
   else
     return sum_recurse(arr, i + 1, sum + arr[i]);
  }
  
  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 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/123.0.0.0 Safari/537.36 OPR/109.0.0.0

Browser/OS: Opera 109 on Windows

View result in a separate tab

Test name	Executions per second
recursion	548839.1 Ops/sec
while loop	3232907.8 Ops/sec
for loop	3647159.5 Ops/sec
recurse (tail)	569380.4 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's dive into the benchmark and explain what's being tested.

**Benchmark Definition**

The benchmark compares four different approaches to sum up an array of numbers:

1. **Recursion (with tail recursion)**: This approach uses a recursive function `sum_recurse` that adds each element in the array recursively, with a twist. The function takes two arguments: `arr` and `i`, where `i` is the current index. If `i` exceeds the length of the array, the function returns 0. Otherwise, it calls itself with `i + 1` and adds the current element to the sum.
2. **Recursion (without tail recursion)**: This approach uses a recursive function `sum_recurse` that is similar to the previous one but without the optimization for tail recursion.
3. **While loop**: This approach uses a while loop to iterate over the array, adding each element to a running total.
4. **For loop**: This approach uses a for loop to iterate over the array, adding each element to a running total.

**Options Compared**

The benchmark compares the execution time of these four approaches on the same input data:

* `nums`: an array of 10 numbers from 1 to 10

**Pros and Cons**

Here's a brief summary of the pros and cons of each approach:

* **Recursion (with tail recursion)**:
	+ Pros: can be easier to implement, especially for small arrays.
	+ Cons: may lead to stack overflow errors for large inputs due to recursive calls.
* **Recursion (without tail recursion)**:
	+ Pros: more straightforward implementation.
	+ Cons: may be less efficient than tail recursion and more prone to stack overflow errors.
* **While loop**:
	+ Pros: can be more efficient than loops, as it only increments the index.
	+ Cons: may require more manual handling of edge cases (e.g., array bounds checking).
* **For loop**:
	+ Pros: typically faster than while loops due to compiler optimizations.
	+ Cons: may not be as flexible or easy to implement for specific use cases.

**Library and Special JS Feature**

The benchmark uses JavaScript, which is a high-level, interpreted language with many built-in features. There are no external libraries mentioned in the benchmark definition. However, the benchmark does utilize:

* **Recursion**: a common programming technique where a function calls itself to solve a problem.
* **Looping constructs**: while loops and for loops are used to iterate over arrays.

**Other Considerations**

When writing benchmarks like this one, it's essential to consider factors such as:

* **Input size**: the benchmark uses an array of 10 numbers, which is relatively small. Larger inputs can affect performance significantly.
* **Compiler optimizations**: the choice of loop type (while or for) can impact performance due to compiler optimizations.
* **System resources**: memory usage and CPU utilization can also be important factors in performance benchmarks.

**Alternatives**

If you're looking for alternative approaches, consider:

* **Iterators**: a more functional programming approach that uses iterators to iterate over arrays.
* **Closures**: a technique where functions have access to their own scope, which can be useful for loop optimization.

Keep in mind that the choice of approach depends on the specific problem and requirements.

Related benchmarks:

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

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

Created: 4 years ago by: Guest

Jump to the latest result

recursion

while loop

for loop

recurse (tail)

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):