object Recursion {

  // Tail recursion - tail calls
  // the function calls itself (or another one) as last action
  // -> the function's stack frame can be reused!
  // -> this is as efficient as a loop
  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  // there is still the multiplication to be performed
  // -> the stack frame can't be reused
  def fact(n: Int): Int =
    if (n == 0) 1 else n * fact(n - 1)

  // tail recursive version of factorial
  def factr(n: Int): Int = {
    def factIter(acc: Int, n: Int): Int =
      if (n == 0) acc else factIter(acc * n, n - 1)
    factIter(1, n)
  }

  def run = {
    println("Recursion")
    println(gcd(21, 56))
    println(fact(4))
    println(factr(4))
  }

}