标签: tail-recursion

我有一个关于Clojure的问题:我正在尝试通过项目Euler来学习语言,我不明白幕后发生了什么:以下代码旨在使用返回所有素数列表lim.我认为它应该是堆空间中的O(n)因为我列出了所有数字lim,然后逐个过滤它们,同时将第一个数字移动到新的列表.(我知道我实际上每个都会重新制作新的列表,但我认为它们不会占用更多的内存？)无论如何,我正在运行这个

(defn getAllPrimes [lim] 
  (defn getPrimes [primes numlist]
    (if (not-empty numlist) ;base case;
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
           (filter
        (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
        (rest numlist)))
      primes)); return the primes
  (getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be …

我最近一直在玩OCaml,并立即做了我最喜欢的事情来检查VM /编译器的开发情况,并写了一个递归程序:

let rec f i =
    Printf.eprintf "i = %d\n" i;
    f(i+1);;

let () =
    f 0;;

该程序按预期运行,但是,递归永远不会中断,事实上,我让这个程序运行了几次(大约30分钟),将stderr重定向到File,以避免堵塞我的终端.检查完文件后,当我注意到文件大约是7*GB*大时,我感到很震惊!

怎么会这样？OCaml没有任何递归限制吗？

我正在阅读关于尾递归的这篇文章.

我将复制发布的解决方案:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

我想知道,如果结果取决于几个递归函数调用呢？例如:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
       }
    return f(a -1) + f( a - 1 );   
}

上面的代码会被编译器优化吗？

我看了三个美丽的Quicksorts谈话,并且正在忙着赶快行动.我在python中的实现与c非常相似(选择pivot,围绕它进行分区并在越来越大的分区上递归).我认为这不是pythonic.

所以这是在python中使用list comprehension的实现.

def qsort(list):
    if list == []: 
        return []
    pivot = list[0]
    l = qsort([x for x in list[1:] if x < pivot])
    u = qsort([x for x in list[1:] if x >= pivot])
    return l + [pivot] + u

让我们调用递归方法qoortR.现在我注意到qsortR比大型(r)列表的qsort运行慢得多.实际上"cmp中超出了最大递归深度",即使对于递归方法也是1000个elems.我在sys.setrecursionlimit中重置.

一些数字:

list-compr 1000 elems 0.491770029068
recursion 1000 elems 2.24620914459
list-compr 2000 elems 0.992327928543
recursion 2000 elems 7.72630095482

所有代码都在这里.

我有一些问题:

• 为什么列表理解这么快？
• 对python中递归限制的一些启示.我首先将它设置为100000,在什么情况下我应该小心？
  • ('优化尾递归'究竟是什么意思,它是如何完成的？)
• 试图对我的笔记本电脑的1000000个元素进行排序(使用递归方法).如果我想要排序这么多元素,我该怎么办？什么样的优化是可能的？

我曾尝试在GCC 4.4.5在Linux在Mac OSX(4.2.1的Xcode)和下面的代码和gcc-LLVM 此.以下是相关功能的来源和生成的反汇编.(补充:编译gcc -O2 main.c)

#include <stdio.h>
__attribute__((noinline))
static void g(long num)
{
        long m, n;
        printf("%p %ld\n", &m, n);
        return g(num-1);
}
__attribute__((noinline))
static void h(long num)
{
        long m, n;
        printf("%ld %ld\n", m, n);
        return h(num-1);
}
__attribute__((noinline))
static void f(long * num)
{
        scanf("%ld", num);
        g(*num);
        h(*num);        
        return f(num);
}
int main(void)
{
        printf("int:%lu long:%lu unsigned:%lu\n", sizeof(int), sizeof(long), sizeof(unsigned));
        long num;
        f(&num);                 
        return 0;
}

08048430 <g>:
8048430:    55                   push   %ebp
8048431:    89 …

我想检查前一个的条件,if condition以确定下一个if condition是否要执行.每个人都if condition可以返回一个值.

编辑:对不起,我之前提供的例子有些奇怪... :(这是我真实的例子,我想简化if-then-else为goingToMove

goingToMove p routes points w h = 
                        if canMove p points
                            -- the point can be moved in the map 
                            then let r = routes ++ [p]
                                     l = remainList p points
                                in move p r l w h
                            -- the point cannot be moved in the maps
                            else []

move p routes points w h = 
            if (length routes) == 2 
                then routes
                else …

我有一个递归函数,耗尽调用堆栈是我遇到的问题.我知道我可以使用带有setTimeout的流,promises,但我想编写触发尾调用优化的代码.到目前为止,只有Webkit似乎已经实现了尾调用优化(TCO).除了知道理论之外,有没有办法检查我的代码是否会触发TCO,无论是使用devtools还是检查Webkit编译器的输出？

我在F#中有这个代码,它找到了最小的正数,它可以被1到20之间的所有数字整除.它需要10秒才能完成.

let isDivisableByAll num (divisors: int[]) = Array.forall (fun div -> num % div = 0) divisors

let minNumDividedBy (divisors: int[]) =  
    let rec minNumDividedByAll stopAt acc = 
        if acc >= stopAt then 0
        else if isDivisableByAll acc divisors then acc
        else minNumDividedByAll stopAt (acc + 1)
    minNumDividedByAll 400000000 1

minNumDividedBy [|1..20|]

所以,我认为我可以使它更优雅,因为我更喜欢更少的代码并写下以下内容.

let answer = { 1..400000000 } 
            |> Seq.tryFind (fun el -> isDivisableByAll el [|1..20|])

花了10分钟!我无法解释巨大的差异,因为序列是懒惰的.为了调查,我写了一个命令式循环.

let mutable i = 1
while i < 232792561 do
    if isDivisableByAll …

我尝试了解编程中的良好实践,并且我坚持这个问题.我知道在Java中,递归函数可能是"痛苦的屁股"(有时),我尝试尽可能多地实现该函数的尾部版本.是值得打扰这个还是我应该用老式的方式做什么？这两个函数之间有什么区别(在Kotlin中):

tailrec fun tail_fibonacci(n : BigInteger, fib1 : BigInteger = BigInteger.ZERO , fib2 : BigInteger = BigInteger.ONE) :
BigInteger {
    return when(n){
        BigInteger.ZERO -> fib1
        else -> tail_fibonacci(n.minus(BigInteger.ONE),fib1.plus(fib2),fib1)
    }
}

fun iterative_fibonacci(n: BigInteger) : BigInteger {
    var count : BigInteger = BigInteger.ONE
    var a : BigInteger = BigInteger.ZERO
    var b : BigInteger = BigInteger.ONE
    var c : BigInteger
    while(count < n){
        count += BigInteger.ONE
        c = a + b
        a = b
        b = c
    }
    return b
}

假设我有一个像这样的树数据结构：

trait Node { val name: String }
case class BranchNode(name: String, children: List[Node]) extends Node
case class LeafNode(name: String) extends Node

假设我还有一个映射叶子的函数：

def mapLeaves(root: Node, f: LeafNode => LeafNode): Node = root match {
  case ln: LeafNode => f(ln)
  case bn: BranchNode => BranchNode(bn.name, bn.children.map(ch => mapLeaves(ch, f)))
}

现在，我正在尝试使此函数尾部递归，但是很难弄清楚该怎么做。我已经读过这个答案，但仍然不知道使该二叉树解决方案适用于多路树。

您将如何重写mapLeaves以使其尾部递归？