Scala Learning(3): Tail Recursion定义

发布时间：2020-12-13 20:45:33 所属栏目：PHP教程来源：网络整理

导读：关于尾递归，使用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 (

关于尾递归，使用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)
-> 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)
-> if (4 == 0) 1 else 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

尾递归定义

1个简单精炼的定义：

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函数里，写1个函数，接收n和累计的乘积值，便可变成尾递归。

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

全文完 :)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!