Как работает линейная рекурсия?

Question

Я написал программу java для добавления элементов в массив с использованием Linear Recursion. Полученный результат не соответствует ожиданиям. Может ли кто-нибудь указать, что не так с этой программой?

public class TestSum { 

    public int count = 0; 


    public int sum(int[] a){ 

     count++; 

     if(a.length == count){ 
      return a[count -1]; 
     } 

     return sum(a) + a[count -1] ; 
    } 

    public static void main(String[] args) { 

     int[] a = {1,2,3}; 

     int val = new TestSum().sum(a); 
     System.out.println(val); 
    } 

} 

Я ожидаю выход как 6, но полученный . Что не так?

Странно, если я изменяю порядок добавления, то есть return a[count -1] + sum(a);, тогда он дает выходные данные как .

Answer 1

В целом, рекурсивные программы, которые не являются повторителями (т. Е. Полагаются на внешнее состояние), являются подозрительными. В вашем конкретном случае count будет меняться между вызовами sum, что затрудняет отслеживание поведения и, в конечном итоге, приводит к ошибке, которую вы наблюдаете.

Вы должны пройти индекс наряду с массивом, чтобы заставить его работать:

// The actual implementation passes the starting index 
private static int sum(int[] a, int start){ 
    if(a.length == start){ 
     return 0; 
    } 
    return sum(a, start+1) + a[start]; 
} 
// Make sure the method can be called with an array argument alone 
public static int sum(int[] a) { 
    return sum(a, 0); 
} 

В отличие от реализации, которая увеличивает счетчик внешних по отношению к способу, эта реализация может быть вызвана одновременно на несколько потоков, не нарушая.