#!/usr/bin/Rscript number_of_grid_routes_dynamic <- function(n) { m <- matrix(0, n+1, n+1) m[n+1,] <- 1 m[,n+1] <- 1 for(x in n:1) for(y in n:1) m[x,y] <- m[x+1,y] + m[x,y+1] return(m[1,1]) } number_of_grid_routes_recursive <- function(x,y=x) { if(!x*y) return(1) return(number_of_grid_routes_recursive(x-1,y) + number_of_grid_routes_recursive(x,y-1)) } measure_runtime <- function(seq, FUN) { sapply(seq, function(x) system.time(print(FUN(x)))["elapsed"]) } par(mfrow=c(2,2)) cat("recursive:\n") timing_rec <- measure_runtime(5:11, number_of_grid_routes_recursive) print(timing_rec) plot(x=5:11, y=timing_rec, xlab="grid size", ylab="runtime (seconds)", main="runtimes of recursive function", type="l") plot(x=5:11, y=timing_rec, xlab="grid size", ylab="runtime (seconds)", main="runtimes of recursive function (log)", type="l", log="y") cat("\ndynamic:\n") timing_dyn <- measure_runtime(seq(100, 600, 100), number_of_grid_routes_dynamic) print(timing_dyn) plot(x=seq(100, 600, 100), y=timing_dyn, xlab="grid size", ylab="runtime (seconds)", main="runtimes of dynamic function", type="l") plot(x=seq(100, 600, 100), y=sqrt(timing_dyn), xlab="grid size", ylab="square root of runtime", main="runtimes of dynamic function (sqrt)", type="l")