McCarthy 91 function in Ruby

m91.rb

## McCarthy 91 function http://en.wikipedia.org/wiki/McCarthy_91_function
# ==========================================================================
# The McCarthy 91 function is a recursive function,
# defined by the computer scientist John McCarthy
# as a test case for formal verification within
# computer science.
# ==========================================================================
# Definition:
#        | n - 10 , n > 100
# f(n) = |
#        | f(f(n+11)) , otherwise
# ==========================================================================
# m91: Int -> Int
def m91(n)
  if n > 100
    n - 10
  else
    m91 m91 n+11
  end
end

## =========================================================================
# f(89) = f(f(100)) = f(f(f(111)))
# = f(f(101)) = f(91) = f(f(102)) = f(92) = ...
# This is the pattern.
# Thus we could define a function H to conclude that
# H(n,m) = f(f(...f(n)...))
#             |.. m ..|
#          | n , m = 0    , when m = 0
# H(n,m) = | H(n-10, m-1) , when m > 0, n > 100
#          | H(n+11, m+1) , when m > 0, n <= 100
# we then derive...
# ==========================================================================
# h: Int x Int -> Int
def h(n, m)
  if m.zero?
    n
  elsif n > 100
    h n-10, m-1
  else
    h n+11, m+1
  end
end

## now we can use h to redefine m91 and make it tail-recursive

## tail-recursive m91
# m91: Int -> Int
def m91_tco(n)
  h n, 1
end