相关疑难解决方法(0)

我喜欢递归,但在Java,你在某个时刻遇到了死胡同.例如,我有一个大约100K迭代的递归不起作用的情况(StackOverflowError).糟糕的是,我不得不为这个运行时堆栈限制原因切换到恼人的"命令性循环".

我想知道其他(特别是功能性)语言如何在运行时绕过堆栈溢出？我想特别是函数式语言运行时更好地处理这个问题,因为递归是核心概念......

有人有一些信息或外部资源吗？

看看这个Scala代码:

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

此代码将导致无限循环.由于尾递归优化,我没有得到StackOverflowError.

用jad反编译我得到了这个Java代码:

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

在循环的最后一行,该方法调用自身,因此我不理解尾调用位置.谁可以解释这个？

我写了3个函数来计算a-element出现在a-list中的次数.我尝试了各种输入并对其进行了分析,但我仍然不知道哪种功能在堆栈使用效率和时间效率方面最佳.请帮帮我.

;; Using an accumulator
    (defn count-instances1 [a-list an-element]
      (letfn [(count-aux [list-aux acc]
                         (cond
                           (empty? list-aux) acc
                           :else (if (= (first list-aux) an-element)  
                                   (count-aux (rest list-aux) (inc acc))
                                   (count-aux (rest list-aux) acc))))]
        (count-aux a-list 0)))

;; Normal counting 
    (defn count-instances2 [a-list an-element]
     (cond
       (empty? a-list) 0
       :else
          (if (= (first a-list) an-element )
              (+ 1 (count-instances2 (rest a-list) an-element))
              (count-instances2 (rest a-list) an-element))))

;; using loop. does this help at all?
   (defn count-instances3 [a-list an-element]
        (loop [mylist a-list acount 0] …

我刚刚阅读了关于scala实现泛型专业化的内容,它确实引起了我的注意,他们通过这个功能提高了速度.我想知道其他功能有哪些语言针对java vm实现,实际上使它们比java更好？我知道生成的代码越远离java,其性能就越低.所以我真的很想知道语言可以实现哪些其他功能来实现更好的java性能.

请不要回答这个问题,谈论scala在java之上的非常好的功能,我正在严格谈论性能.

如果您的建议仍未实施,请回答!

谢谢!

据我所知,由于函数调用的开销,递归函数通常效率低于等效的非递归函数.但是,我最近遇到了一本教科书,说Java(和C#)并不是必需的.

它没有说明原因,但我认为这可能是因为Java编译器以某种方式优化了递归函数.

有谁知道为什么会这样的细节？

我编码了3个因子算法:

1. 首先,我希望Stack Overflow失败.没问题.
2. 其次,我尝试尾部重用调用,将先前的算法从递归转换为迭代.它不起作用,但我不明白为什么.
3. 第三,我使用trampoline()方法,并按照我的预期正常工作.

def factorial

factorial = { BigInteger n ->
    if (n == 1) return 1
    n * factorial(n - 1)
}
factorial(1000)  // Stack Overflow

factorial = { Integer n, BigInteger acc = 1 ->
    if (n == 1) return acc
    factorial(n - 1, n * acc)
}
factorial(1000)  // Stack Overflow, why???

factorial = { Integer n, BigInteger acc = 1 ->
     if (n == 1) return acc
     factorial.trampoline(n …

当我使用has/use方法有很多(超过一百个)参数时,它在计算性能方面是否无效？

我并不是说在可维护性方面有效,而只是在"原始"计算性能方面:)

我有一个大学实验室的问题;

编写一个简短的程序,输出通过使用字符'c','a','r','b','o'和'n'形成的所有可能的字符串.

这似乎是一个常见的面试问题,并有详细记录.

所以我使用递归方法用Java编写它并不太难,何时或为什么你会选择不使用递归？最简单的方法是什么？

我开始编写一个计数器,它会倒计数到6,然后输出将引用char并打印字符串.

谢谢,

你总是可以构建一个递归函数来消除尾部调用吗？如果没有,那么限制堆栈大小的其他策略是什么？

例如:(灵感来自Break或shortcircuit Scala中的折叠)

// Depth-first search of labyrinth, with large depth > stacklimit
def search ( labyrinth: SearchDomain,
             path: List[SolutionNode],
             goal: DesiredResult ) = {

  if ( path.head == goal ) return path

  candidates: List[SolutionNode] = labyrinth.childNodes(path)

  candidates.find { c =>
    Nil != search( labyrinth, c :: path, goal ) // potential boom!
  } match {
    case Some(c) => c :: path
    case None => Nil
  }
}

我们的目标不是挑选这个特定的功能,而是将其用作学习限制堆栈大小的技术.

UPDATE

我从中得到的结论是:

如果问题域是递归可能会达到堆栈大小的限制:

将代码重写为scala-compiler-version-of-tailcall-optimizable.这可以通过新的(2.8)@scala.annotation.tailrec注释来辅助/验证.

如果这不可行,请将其重写为使用迭代循环结构.

我也感觉到这种重写(任何一种情况)都需要一定的技能/才能/智慧/练习.

抱歉，我的问题可能很愚蠢，我是 Java 新手。

有没有一种方法可以在Java中进行无限递归，例如：

public void sillyMethod()
{
    System.out.println(i);
    i++;
    sillyMethod();

}

它抛出 StackOverflowError，但我真的想无休止地运行它。有什么办法可以做到吗？

谢谢！

只是玩延续。目标是创建将接收另一个函数作为参数和执行量的函数，并返回将应用参数给定次数的函数。

实现看起来很明显

def n_times[T](func:T=>T,count:Int):T=>T = {
  @tailrec
  def n_times_cont(cnt:Int, continuation:T=>T):T=>T= cnt match {
        case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
        case 1 => continuation
        case _ => n_times_cont(cnt-1,i=>continuation(func(i)))
      }
  n_times_cont(count, func)
}

def inc (x:Int) = x+1

    val res1 = n_times(inc,1000)(1)  // Works OK, returns 1001

val res = n_times(inc,10000000)(1) // FAILS

但没有问题 - 这段代码失败并出现 StackOverflow 错误。为什么这里没有尾部调用优化？

我使用 Scala 插件在 Eclipse 中运行它，它在 Task_Mult$$anonfun$1.apply(Task_Mult.scala: scala.runtime.BoxesRunTime.boxToInteger(Unknown Source) 处的线程“main”java.lang.StackOverflowError 中返回异常： 25) 在 Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

附注

F# 代码几乎是直接翻译，运行没有任何问题

let …

在我的代码中,该方法将调用自身(递归).我们知道,深度方法调用会导致堆栈溢出.那么,当存在大量数据时,是否会发生堆栈溢出？

我的QuickSort代码:(排序类的内部类)

private static class QuickSortor extends Sortor {

    protected <E> void sort(E[] a, boolean isAsc) {
        quickSort(a, 0, a.length - 1, isAsc);
    }

    private <E> void quickSort(E[] a, int left, int right, boolean isAsc) {
        if (left >= right)
            return;
        int middle = left;
        Comparable<E> cmp = (Comparable<E>) a[left];
        for (int i = left + 1; i <= right; i++) {
            int result = cmp.compareTo(a[i]);
            if (!isAsc)
                result = -result;
            if (result >= 0)
                swap(a, ++middle, i);
        }
        swap(a, …