Benchmarking recursion in different languages

I used the Fibonacci sequence to test the speed of recursive calls in different languages. Take the results with a grain of salt because my computer is not a controlled environment. I found that Python was slower than I expected, while JavaScript was faster than I expected. Bash was more than 100,000 times slower than C because the Bash benchmark did not finish after the 5-hour mark. My hypothesis is that Bash is very slow because math is done in sub-shells, requiring bash to spawn a process for every arithmetic operation.

Execution times for calculating the 39th term of the Fibonacci sequence:

Language	Compiler/Interpreter	Flags	Time (sec)
C	gcc 12.3.0	-O3 -Ofast	0.124
C++	g++ 12.3.0	-O3 -Ofast	0.125
Rust	rustc 1.73.0	-C opt-level=3	0.247
Java	javac/java 17.0.7	None	0.460
Dart	dart 3.3.4	compile aot-snapshot	0.466
JavaScript	node 21.2.0	None	0.802
Lua	lua 5.2.4	None	8.192
Python	python3 3.11.6	None	10.828
Perl	perl 5.38.2	None	38.966
Vimscript	nvim 0.10.0	None	346.000
Nushell	nu 0.93.0	None	710.000
Bash	bash	None	18000.000

Implementations #

/**
 * @file
 * @brief Calculate the a Fibonacci sequence number from user input.
 */
#include <stdio.h>
#include <stdlib.h>

/**
 * @brief Calculate a Fibonacci sequence number.
 *
 * @param term The sequence number to produce. Don't use large
 * numbers as the time complexity is exponential.
 * @return The sequence number.
 */
int fibonacci(int term) {
    // Base case.
    if (term <= 1) {
        return term;
    }
    // Recursive step.
    return fibonacci(term - 1) + fibonacci(term - 2);
}

/**
 * @brief Calculate a Fibonacci sequence number from user input.
 *
 * @param argc The argument count.
 * @param argv The argument vector.
 * @return The error code.
 */
int main(int argc, char **argv) {
    if (argc > 1) {
        int term = atoi(argv[1]);
        int result = fibonacci(term);
        printf("%d\n", result);
    }
    return 0;
}

C++

/**
 * @file
 * @brief Calculate a Fibonacci sequence number from user input.
 */
#include <iostream>

/**
 * @brief Calculate a Fibonacci sequence number.
 *
 * @param term The sequence number to produce. Don't use large
 * numbers as the time complexity is exponential.
 * @return The sequence number.
 */
int fibonacci(int term) {
  // Base case.
  if (term <= 1) {
    return term;
  }
  // Recursive step.
  return fibonacci(term - 1) + fibonacci(term - 2);
}

/**
 * @brief Calculate a Fibonacci sequence number from user input.
 *
 * @param argc The argument count.
 * @param argv The argument vector.
 * @return The error code.
 */
int main(int argc, char **argv) {
  if (argc > 1) {
    int term = std::stoi(argv[1]);
    int result = fibonacci(term);
    std::cout << result << std::endl;
  }
  return 0;
}

Rust

//! Calculate a Fibonacci sequence number from user input.
use std::env::args;

/// Calculate a Fibonacci sequence number.
///
/// * `term`: The sequence number to produce. Don't use large numbers as the
/// time complexity is exponential.
fn fibonacci(term: i32) -> i32 {
    // Base case.
    if term <= 1 {
        return term;
    }
    // Recursive step.
    fibonacci(term - 1) + fibonacci(term - 2)
}

/// Calculate a Fibonacci sequence number from user input.
fn main() {
    let arguments: Vec<String> = args().collect();
    if let Some(argument) = arguments.get(1) {
        let term: i32 = argument.parse().unwrap_or(0);
        let result = fibonacci(term);
        println!("{}", result);
    }
}

Java

/** Calculate a Fibonacci sequence number from user input. */
class Fibonacci {
  /**
   * Calculate a Fibonacci sequence number.
   *
   * @param term The sequence number to produce. Don't use large numbers as the time complexity is
   *     exponential.
   * @return The sequence number.
   */
  public static int fibonacci(int term) {
    // Base case.
    if (term <= 1) {
      return term;
    }
    // Recursive step.
    return fibonacci(term - 1) + fibonacci(term - 2);
  }

  /**
   * Calculate a Fibonacci sequence number from user input.
   *
   * @param args The command-line arguments.
   */
  public static void main(String[] args) {
    if (args.length > 0) {
      int term = Integer.parseInt(args[0]);
      int result = fibonacci(term);
      System.out.println(result);
    }
  }
}

Dart

/// Calculate a Fibonacci sequence number from user input.
void main(List<String> args) {
    final term = int.parse(args[0]);
    print(fibonacci(term));
}

/// Calculate the Fibonacci sequence number for the [n]-th term.
///
/// Don't use large numbers as the time complexity is exponential.
int fibonacci(int n) {
  // Base case: the first two numbers in the sequence are 0 and 1.
  if (n <= 1) {
    return n;
  }

  // Recursive step: The nth number in the sequence is the sum of the (n - 1)th
  // and (n - 2)th numbers.
  return fibonacci(n - 1) + fibonacci(n - 2);
}

JavaScript

#!/usr/bin/env node

/**
 * @module Calculate a Fibonacci sequence number from user input.
 */

/**
 * Calculate a Fibonacci sequence number.
 *
 * @param {number} term The sequence number to produce. Don't use large numbers
 * as the time complexity is exponential.
 * @returns {number} The sequence number.
 */
function fibonacci(term) {
    // Base case.
    if (term <= 1) {
        return term;
    }
    // Recursive step.
    return fibonacci(term - 1) + fibonacci(term - 2);
}

if (process.argv.length > 2) {
    const term = parseInt(process.argv[2]);
    const result = fibonacci(term);
    console.log(result);
}

Lua

#!/usr/bin/env lua
--- @module Calculate a Fibonacci sequence number from user input.

--- Calculate a Fibonacci sequence number.
--- @param term number The sequence number to produce. Don't use large numbers as
--- the time complexity is exponential.
--- @return number
local function fibonacci(term)
    -- Base case.
    if term <= 1 then
        return term;
    end
    -- Recursive step.
    return fibonacci(term - 1) + fibonacci(term - 2);
end

if #arg >= 1 then
    local term = tonumber(arg[1]) or 0;
    local result = fibonacci(term);
    print(result);
end

Python

#!/usr/bin/python3
"""Calculate a Fibonacci sequence number from user input."""
from sys import argv

def fibonacci(term: int) -> int:
    """Calculate a Fibonacci sequence number.

    Args:
        term (int): The sequence number to produce. Don't use large numbers as
        the time complexity is exponential.

    Returns:
        int: The sequence number.
    """
    # Base case.
    if term <= 1:
        return term
    # Recursive step.
    return fibonacci(term - 1) + fibonacci(term - 2)

def main():
    """Calculate a Fibonacci sequence number from user input."""
    if len(argv) >= 2:
        term = int(argv[1])
        result = fibonacci(term)
        print(result)

if __name__ == "__main__":
    main()

Perl

#!/usr/bin/env perl
use strict;
use warnings;
use feature 'say';

sub fibonacci {
    my $term = shift;
    # Base case.
    if ($term <= 1) {
        return $term;
    }
    # Recursive step.
    return fibonacci($term - 1) + fibonacci($term - 2);
}

sub main {
    if (scalar @ARGV >= 1) {
        my $value = fibonacci(int($ARGV[0]));
        say($value);
    }
}

unless (caller) {
    main();
}

__END__

=head1 DESCRIPTION

Calculate a Fibonacci sequence number from user input.

=cut

=head1 FUNCTIONS

=over

=item fibonacci($term)

Calculate a Fibonacci sequence number.

$term C<int> is the sequence number to produce. Don't use large numbers as the
time complexity is exponential.

Returns C<int>, the sequence number.

=item main

Calculate a Fibonacci sequence number from user input.

=back

=cut

Vimscript

#!/usr/bin/env -S nvim --cmd ":source fibonacci.vim"
function! Fibonacci(n)
    if a:n <= 2
        return 1
    else
        return Fibonacci(a:n - 2) + Fibonacci(a:n - 1)
    endif
endfunction

echom Fibonacci(39)
quit!

Nushell

#!/usr/bin/env nu

# Calculate a Fibonacci sequence number from user input.
def main [ term: int ] {
    print (fibonacci $term);
}

# Calculate a Fibonacci sequence number.
# Returns: int The sequence number.
def fibonacci [
    term: int # The sequence number to produce. Don't use large numbers as the
              # time complexity is exponential.
] {
    if $term <= 1 {
        # Base case.
        return $term;
    }
    # Recursive step.
    (fibonacci ($term - 1)) + (fibonacci ($term - 2))
}

Bash

#!/usr/bin/bash

# Calculate a Fibonacci sequence number from user input.

# Exit on errors and undefined variables.
set -eu

################################################################################
# Calculate a Fibonacci sequence number.
# Arguments:
#     $1: int The sequence number to produce. Don't use large numbers as
#         the time complexity is exponential.
# Outputs:
#     int The sequence number.
################################################################################
fibonacci() {
    declare -ir term=$1
    # Base case.
    if (( term <= 1 )); then
        echo $term
        return
    fi
    # Recursive step.
    echo $(( $(fibonacci $((term - 1)) ) + $(fibonacci $((term - 2)) ) ))
}

fibonacci $1