blob: 5488aeacf7f176675456bbba3259bac91ce61d78 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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))
}
}
|
