Benchmarking Recursion Speed in R, Python, and Julia

R

# Define recursion function for fibonacci sequence
fib <- function(n) {
  if (n == 0) return (0)
  if (n <= 2) return (1)
  return (fib(n - 1) + fib(n - 2))
}

# Define range of sequence to explore, 1 through 40
Ns = 0:40

# Estimate the time taken for each run
Ts = sapply(Ns, \(n) system.time(fib(n))[3])

# Plot the results
plot(Ns, Ts, type = "l", 
     xlab = "N", ylab = "time (s)", 
     col = "blue",
     main = "Recursive calculation of Fibonacci numbers (R)")

# Total time
print(paste0("Total time was ", sum(Ts), " seconds in R."))

## [1] "Total time was 150.873 seconds in R."

Python

import matplotlib.pyplot as plt
from timeit import timeit

# Define recursion function for fibonacci sequence
def fib(n):
  if (n == 0):
    return 0
  elif (n <= 2):
    return 1
  else:
    return (fib(n - 1) + fib(n - 2))

# Define range of sequence to explore, 1 through 40
Ns = range(0,41)

# Estimate the time taken for each run
Ts = [timeit(lambda: fib(x), number = 1) for x in Ns]

# Plot the results
plt.plot(Ns, Ts, marker = "")
plt.xlabel("N")
plt.ylabel("time (s)")
plt.title("Recursive calculation of Fibonacci numbers (Python)")
plt.show()

# Total time
print(f"Total time was {sum(Ts)} seconds in Python.")

## Total time was 24.07692269596737 seconds in Python.

Julia

using Plots;

# Define recursion function for fibonacci sequence
fib = function(n)
  if n == 0
    return 0
  elseif n <= 2
    return 1
  else
    return fib(n - 1) + fib(n - 2)
  end  
end;

# Define range of sequence to explore, 1 through 40
Ns = 0:40;

# Estimate the time taken for each run
Ts = [@elapsed fib(x) for x in Ns];

# Plot the results
plot(Ns, Ts, 
     xlabel = "N", ylabel = "time (s)", 
     title = "Recursive calculation of Fibonacci numbers (Julia)")

# Total time
print("Total time was $(sum(Ts)) seconds in Julia")

## Total time was 10.863438192 seconds in Julia

Summary

Calculating the first 40 elements of the Fibonacci sequence using a recursive algorithm took about 152, 24, and 11 seconds, for R, Python, and Julia, respectively. Overall pretty fast, and pretty significant differences among the languages. Notably, we didn’t account for start up time, time to check syntax, time to set up the environment, and other overheard. The R code was easily written in base R without the need for any additional packages. The Python environment was notably the slowest to set up and required installing matplotlib into a virtual environment that would run within Rstudio, which was used to render this document. The Julia example required installing and loading the Plots library, but this was already done as the same local environment I use was called by Rstudio without any additional configuration. Which language do you reach for first? When in Rome…