防止堆棧溢出，而在序列

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序列來計算2378421387489th元素，它在StackOverflow的失敗。我如何避免這種情況？

Answer 1

超過heapsize時會發生溢出錯誤（當子函數調用的次數很多時，這通常在遞歸程序中看到）。 個人我會避免使用遞歸。

嘗試將遞歸代碼更改爲循環並重新運行。

Answer 2

您應該添加一些先決條件檢查：

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); 
}