recursive_functions

Modules

• ackermann
  • Ackermann examples
  • ackermann_list()
• fibonacci
  • Fibonacci examples
  • orderable_generator()
• cli
  • ackermann_cli
  • fibonacci_cli
  • Installed Apps

Overview

Recursive Functions Package

Package to explore efficient ways to implement recursive functions.

Ackermann function

Ackermann’s function is an example of a function that is computable but not primitively recursive. It quickly becomes computationally intractable for relatively small values of m.

Ackermann function is defined recursively by

ackermann(0,n) = n+1 for n >= 0

ackermann(m,0) = ackermann(m-1,1) for m >= 0

ackermann(m,n) = ackermann(m-1, ackermann(m,n-1)) for m, n > 0

Fibonacci sequences

The Fibonacci sequence is usually taught in grade school as the first recursive function that is not either an arithmetic or geometric progression.

The Fibonacci sequence is traditionally defined as

f₁ = 1

f₂ = 1

fₙ₊₂ = fₙ₊₁ + fₙ

Actually, the Fibonacci sequence can be extended in both directions.

..., 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 6, 13, ...