Recursion and tail recursion

Jump to bottom Edit New page

HeatoN edited this page Jan 14, 2015 · 1 revision

Normal Recursion

def factorial(n: Int): Int =
  if (n == 0) 1 else n * factorial(n - 1)

compile to

public int factorial(int n) {
    return n == 0 ? 1 : n * this.factorial(n - 1);
}

Tail Recursion

@tailrec
def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

compile to

public int gcd(int a, int b) {
    while (b != 0) {
        int n = b;
        b = a % b;
        a = n;
    }
    return a;
}