compiler-errors - 用于编译项目的示例程序中的堆栈溢出错误

Question

我正在编写一个示例程序来测试工具语言的编译器。 Here您可以找到该语言的一些文档。我的程序代码如下:

program CountChange {
 println(new countChangeApp().initCoins().countChange(300));
}

class countChangeApp{
 var array: Int[];

 def initCoins() :countChangeApp = {
  array = new Int[7];
  array[0] = 5;
  array[1] = 10;
  array[2] = 20;
  array[3] = 50;
  array[4] = 100;
  array[5] = 200;
  array[6] = 500;

  return this;
 }

 def countChange(money:Int):Int = {
  return this.computeCountChange(money,array);
 }

 def computeCountChange(money: Int,coins :Int[]): Int = { 
    var answer : Int;
    if (money < 0 || coins.length == 0) answer = 0;
    else if (money == 0) answer = 1;
    else answer = this.computeCountChange(money-coins[0],coins) + this.computeCountChange(money,this.tail(coins));
    return answer;
 }

 def tail(array: Int[]): Int[] = {
  var tail : Int[];
  var i : Int;

  if(0 < array.length){
   tail = new Int[array.length - 1];
   i = 0;
   while(i < array.length - 2){
    tail[i] = array[i+1];
    i = i+1;
   }
  }else{
   tail = new Int[array.length];
  }
  return tail;
     }

}

因此，基本上，这些程序计算出的大小为5,10,20,50,100,200和500的硬币的找零方式有300种。

我还对底部的尾部功能进行了彻底的测试，因此我们不必担心。

问题是，当我执行它时(遵循 this指令)，我得到了一个讨厌的StackOverflowError形式:

Exception in thread "main" java.lang.StackOverflowError
    at countChangeApp.computeCountChange(countchange.tool:29)

最后一行重复多次。我的猜测是，也许我为阵列保留了太多的内存。有人看到问题出在哪里吗？

Answer 1

My guess is that maybe I'm reserving too mach memory for the arrays.

从错误消息来看，您的语言正在JVM上运行。 JVM从不将数组存储在堆栈上，因此大型数组不会导致堆栈溢出。

tail = new Int[array.length - 1];
i = 0;
while(i < array.length - 2){
 tail[i] = array[i+1];
 i = i+1;
}

您正在创建n-1个元素的数组，但只向其中写入n-2个元素。因此，最后一个元素将为0。

就您的找零计数逻辑而言，这意味着您拥有0值硬币。这意味着一旦到达零值硬币，当您执行 money-coins[0]时，您将获得完全相同的金额，从而导致无限递归。除非进行尾部递归优化(因为函数不是尾部递归，否则无论如何在这里都不会应用)，无限递归总是导致堆栈溢出。