scala 如何在尾递归函数中添加内联函数

rqqzpn5f  于 12个月前  发布在  Scala
关注(0)|答案(2)|浏览(94)

假设我有下面的tail递归函数:

@tailrec final def f1(i: Int, j: Int): Int = {
    if (i < j) f1(i + 1, j)
    else if (i < j * 2) f1(i + 2, j)
    else i
}

有没有一种方法,我可以推广加法部分,同时保持函数作为一个尾部递归?我试着修改它如下:

@tailrec final def f2(i: Int, j: Int): Int = {
    def add(c: Int): Int = f2(i + c, j)
    if (i < j) add(1)
    else if (i < j * 2) add(2)
    else i
}

但我得到以下错误:
无法优化@tailrec注解的方法f2:它包含一个不在尾部位置的递归调用else if(i < j * 2)add(2)

oyjwcjzk

oyjwcjzk1#

@tailrec在这里不起作用,因为你调用的是一个不同的函数,add,而不是原来的函数(尽管我们知道它只是调用原来的函数),所以我认为这在Scala 2中是不可能的。
由于你的目标似乎是消除在函数调用中重复常量的需要-这是你希望对这样一个内部函数做的所有事情,你希望使tail递归-你可以:
1.使内部函数的尾部递归,并使用外部作用域中的常量值:

final def f3(i: Int, j: Int): Int = {
  @tailrec
  def add(i: Int): Int = 
    if (i < j)          add(i + 1)
    else if (i < j * 2) add(i + 2)
    else                i
  add(i)
}

1.[nasty]由于尾递归函数编译为while循环,只需手动编写while循环,可变变量和所有内容(留给读者练习)。

kuuvgm7e

kuuvgm7e2#

在Scala 2和Scala 3中,你可以随时对代码进行蹦床,以消除任何方法调用,即使是那些根本不在尾部位置的方法调用,无论它们的隐私/公开性或终结性/非终结性:

import scala.util.control.TailCalls.{TailRec,tailcall,done}
def f2(i: Int, j: Int): Int = {
  def add(c: Int): TailRec[Int] = tailcall(fun(i + c, j))
  def fun(i: Int, j: Int): TailRec[Int] = {
    if (i < j) add(1)
    else if (i < j * 2) add(2)
    else done(i)
  }
  fun(i, j).result
}

相关问题