Scala Learning(3): Tail Recursion定义

关于尾递归 ，使用Scala的两个例子展示尾递归的定义和简单实现。

例子比较

求最大公约数的函数

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

计算的展开是尾递归的，

gcd(14, 21)-> if (21 == 0) 14 else gcd(21, 14 % 21)-> if (false) 14 else gcd(21, 14 % 21)-> gcd(21, 14 % 21)-> gcd(21, 14)-> if (14 == 0) 21 else gcd(14, 21 % 14)-> gcd(14, 7)-> gcd(7, 0)-> if (0 == 0) 7 else gcd(0, 7 % 0)-> 7

求阶乘的函数

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

计算的展开是非尾递归的,

factorial(4)-> * factorial(4 – 1)-> 4 * factorial(3)-> 4 * (3 * factorial(2))-> 4 * (3 * (2 * factorial(1)))-> 4 * (3 * (2 * (1 * factorial(0)))-> 4 * (3 * (2 * (1 * 1)))-> 120尾递归定义

一个简单精炼的定义：

If a function calls itself as its last action, the function`s stack frame can be reused. This is called tail recursion.

gcd函数在else分支后面调用的是自己，而factorial函数在else分支里，，调用自己之后还乘以了n，所以不是尾递归。

改写

在factorial函数里，写一个函数，接收n以及累计的乘积值，即可变成尾递归。

def factorial(n: Int): Int = { def tailIter(product: Int, n: Int): Int = {if (n == 0) productelse tailIter(product*n, n-1) } tailIter(1, n)}

全文完 🙂

怠惰是贫穷的制造厂。