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. As for Bash, I found it pointless to continue measuring after the 5-hour mark.
Language | Compiler/Interpreter | Flags | Time |
---|---|---|---|
C | gcc | -O3 -Ofast | 0sec 266ms |
C++ | g++ | -O3 -Ofast | 0sec 267ms |
Rust | rustc | -C opt-level=3 | 0sec 433ms |
Java | javac/java | None | 0sec 715ms |
JavaScript | node | None | 1sec 185ms |
Lua | lua | None | 9sec 152ms |
Python | python3 | None | 15sec 831ms |
Bash | bash | None | 5hr+ |
Implementations
C
/**
* @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);
}
}
}
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()
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