在按顺序计算项时防止堆栈溢出

Question

我有一个二进制序列，它遵循特定的逻辑，以0和开头

nth term = sequence of (n-1)th term + 0 + inverse(reverse(n-1)th term)

例如：

0
0 + 0 + 1
001 + 0 + 011
0010011 + 0 + 0011011

这里，我需要找出第k个序列的第n项。我的看法：

static int foo(long n, int k) { //n-th element (indexed from 0) in k-th sequence
    long length = (2 << k) - 1; //computes 2^(k+1)-1
    if(n == length/2) return 0;
    if(n < length/2) return foo(n, k-1);
    return 1 - foo(length - n - 1, k-1);
}

但如果我试图计算第50个序列中的2378421387489个元素，它在StackOverflow中失败了。我该如何避免这种情况？

Answer 1

您应该添加一些先决条件检查：

static int foo(long n, int k) { //n-th element (indexed from 0) in k-th sequence
    long length = (2 << k) - 1; //computes 2^(k+1)-1
    if(n > length) throw new IllegalArgumentException("Out of bounds");
    if(n == length/2) return 0;
    if(n < length/2) return foo(n, k-1);
    return 1 - foo(length - n - 1, k-1);
}

您的功能的正确实现是：

static int foo(long n, int k) { //n-th element (indexed from 0) in k-th sequence
    if(n==0 && k==0) return 0;
    long length = (1L << k) - 1;
    if(n < length) return foo(n, k-1);
    if(n == length) return 0;
    return 1 - foo(n-length-1, k-1);
}

Answer 2

超过堆大小时会发生溢出错误（子函数调用次数较多时，这在递归程序中常见）。就我个人而言，我会避免使用递归。

请尝试将递归代码更改为循环，然后重新运行。