标签: tail-recursion

我想知道是否有一些通用方法来转换"正常"递归foo(...) + foo(...)作为最后一次调用尾递归.

例如(scala):

def pascal(c: Int, r: Int): Int = {
 if (c == 0 || c == r) 1
 else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

函数式语言的一般解决方案,用于将递归函数转换为尾部调用等效函数:

一种简单的方法是将非尾递归函数包装在Trampolinemonad中.

def pascalM(c: Int, r: Int): Trampoline[Int] = {
 if (c == 0 || c == r) Trampoline.done(1)
 else for {
     a <- Trampoline.suspend(pascal(c - 1, r - 1))
     b <- Trampoline.suspend(pascal(c, r - 1))
   } yield a + b
} …

我写了以下函数:

let str2lst str =
    let rec f s acc =
      match s with
        | "" -> acc
        | _  -> f (s.Substring 1) (s.[0]::acc)
    f str []

如何知道F#编译器是否将其转换为循环？有没有办法在不使用Reflector的情况下找出答案(我没有使用Reflector的经验而且我不知道C#)？

编辑:另外,是否可以在不使用内部函数的情况下编写尾递归函数,或者循环是否需要驻留？

另外,F#std lib中是否有一个函数可以多次运行给定函数,每次都将最后一个输出作为输入？让我说我有一个字符串,我想在字符串上运行一个函数然后再次在结果字符串上运行它等等...

我想知道是否有一个根本原因将F#中的递归深度限制在10000左右,理想情况下如何避免该限制.我认为编写使用O(n)堆栈空间的代码是完全合理的,如果不同意的人可以解释他们为什么这样做,我将不胜感激.非常感谢.我在下面解释我的想法.

我没有看到有任何理由不允许堆栈增长,直到整个可用内存耗尽.这意味着无限递归需要更长时间才能注意到,但并不是说我们不能编写消耗无限内存的程序.我知道可以使用continuation和尾递归将堆栈使用减少到O(1),但我并不特别看到我必须一直这样做是有益的.我也没有看到如何知道函数何时需要处理"大"输入(通过8位微控制器的标准).

我认为这与必须例如使用累积参数以避免二次时间行为有根本的不同.虽然这也涉及担心实现细节,并且不需要为"小"输入完成,但它也是非常不同的,因为编译器本身不能轻易地删除问题.进一步的不同之处在于,稍微复杂的O(n)代码如果天真地写入则是O(n ^ 2)比简单,缓慢,易于阅读的版本更有用.相比之下,延续式代码与相应的天真版本具有完全相同的内存复杂性,但只使用不同类型的内存.这是编译器在这个时代不应该让我担心的事情吗？

虽然我"更喜欢"理论上的原因,为什么不可能有一个深层叠加,我们也可以讨论实际方面.在我看来,堆栈是一种比堆更有效的管理内存的方式,因为它不需要垃圾收集并且很容易被释放？我不确定我是否能看到允许深堆栈的成本.不可否认,操作系统需要留出足够的虚拟空间来包含您可能希望在整个程序中为每个线程堆栈一次使用的所有内存.但那是什么呢.通过这样做,或者硬件制造商不能轻易地将该限制增加到64位,这并不是说我们可能会用尽当前常见的48位限制？

F#没有那么具体.我希望在C#中也适用同样的限制,并且没有看到它在那里更加必要,尽管在以命令式方式编程时,实际上显然不那么痛苦.

非常感谢任何回复/评论.

编辑:我写了以下答案的摘要.

在算法简介中, p169它讨论了使用尾递归Quicksort.

本章前面的原始Quicksort算法是(伪代码)

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

使用尾递归的优化版本如下

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

在哪里Partition根据枢轴对阵列进行排序.

不同之处在于第二种算法只调用Quicksort一次来对LHS进行排序.

有人可以向我解释为什么第一个算法可能导致堆栈溢出,而第二个算法不会？或者我误解了这本书.

虽然我知道尾部递归优化是非Pythonic的,但我想到了一个快速入侵这里的问题,一旦我准备发布就删除了.

由于1000个堆栈限制,深度递归算法在Python中不可用.但有时通过解决方案对初步想法很有帮助.由于函数是Python中的第一类,我使用返回有效函数和下一个值.然后循环调用该进程,直到完成单个调用.我敢肯定这不是新的.

我发现有趣的是,我期望来回传递函数的额外开销使得这比正常递归慢.在我的粗略测试期间,我发现它需要30-50%的正常递归时间.(允许LONG递归的额外好处.)

这是我正在运行的代码:

from contextlib import contextmanager
import time

# Timing code from StackOverflow most likely.
@contextmanager
def time_block(label):
    start = time.clock()
    try:
        yield
    finally:
        end = time.clock()
        print ('{} : {}'.format(label, end - start))


# Purely Recursive Function
def find_zero(num):
    if num == 0:
        return num
    return find_zero(num - 1)


# Function that returns tuple of [method], [call value]
def find_zero_tail(num):
    if num == 0:
        return None, num
    return find_zero_tail, num - 1


# Iterative recurser
def tail_optimize(method, …

一般来说,我在查找如何在"内部"monad中编写tailrecursive函数时遇到问题.这是一个简单的例子:

这是我写的一个小示例应用程序,以更好地理解Scala中的FP.首先,提示用户进入由7名玩家组成的团队.此函数以递归方式读取输入:

import cats.effect.{ExitCode, IO, IOApp}
import cats.implicits._

case class Player (name: String)
case class Team (players: List[Player])

/**
  * Reads a team of 7 players from the command line.
  * @return
  */
def readTeam: IO[Team] = {
  def go(team: Team): IO[Team] = { // here I'd like to add @tailrec
    if(team.players.size >= 7){
      IO(println("Enough players!!")) >>= (_ => IO(team))
    } else {
      for {
        player <- readPlayer
        team   <- go(Team(team.players :+ player))
      } yield team
    }
  }
  go(Team(Nil))
} …

有时它很简单(如果自调用是最后一个语句,它是尾递归),但仍有一些案例让我感到困惑.一位教授告诉我"如果在自我调用之后没有执行指令,那就是尾递归".这些例子怎么样(忽略它们没有多大意义的事实):

a)这个应该是尾递归的,看看自调用是最后一个语句,并且在它之后没有任何东西可以执行.

function foo(n)
{
    if(n == 0)
        return 0;
    else
        return foo(n-2);
}

b)但是这个怎么样？它应该是一个尾调用,因为如果条件为真,除了它之外什么都不会执行,但它不是最后一个语句？

function foo(n)
{
    if(n != 0)
        return foo(n-2);
    else
        return 0;
}

c)这个怎么样？在这两种情况下,自我调用将是最后执行的事情:

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}

Rich Hickey和其他人已经提到Clojure不会从即将推出invokeDynamic的JVM 7或8计划中获得显着改进,但是会看到尾递归的性能提升.

尾递归是否会对其产生影响

(fn [...] (recur ...))

要么

(loop [...] (recur ...))

我不希望它们得到任何更快,因为编译器可能已经生成循环结构.

在clojure中,我想编写一个尾递归函数,为后续调用记忆其中间结果.

[编辑:这个问题已被重写gcd,而不是使用factorial.]

记忆gcd(最大公约数)可以像这样实现:

(def gcd (memoize (fn [a b] 
   (if (zero? b) 
       a 
       (recur b (mod a b)))) 

在此实现中,不会为后续调用记忆中间结果.例如,为了计算,称为中间结果.但是,没有存储在memoized函数的缓存中,因为递归点是未被记忆的匿名函数.gcd(9,6)gcd(6,3)gcd(6,3)recur

因此,如果在打电话后gcd(9,6),我们打电话说gcd(6,3)我们不会从备忘录中受益.

我能想到的唯一解决方案是使用普通的递归(明确地调用gcd而不是recur),但是我们不会从尾部调用优化中受益.

底线

有没有办法实现两者:

1. 尾调用优化
2. 为后续调用记录中间结果

备注

1. 这个问题类似于Combine memoization和tail-recursion.但那里的所有答案都与之相关F#.在这里,我正在寻找答案clojure.
2. 这个问题已经被"欢乐的Clojure"(第12.4章)留给了读者.您可以在http://bit.ly/HkQrio查阅该书的相关页面.

我对Scala很新,所以请原谅我的无知!我正在尝试迭代以最大值为界的整数对.例如,如果最大值为5,则迭代应返回:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

我选择尝试并以递归方式将其作为Stream返回:

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

没有tailrec注释,代码可以工作:

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), …