user001 user001 - 11 months ago 57
Java Question

How does Linear Recursion work?

I have written a java program to add elements in an array using Linear Recursion. The output obtained is not as expected. Can anyone point what is wrong with this program?

public class TestSum {

public int count = 0;

public int sum(int[] a){


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


I am expecting the output as 6 but obtained is 9. What is wrong?

Strangely if I change the order of addition i.e.
return a[count -1] + sum(a);
then it gives output as 6.

Answer Source

Generally, recursive programs that are not re-entrant (i.e. relying on external state) are suspicious. In your particular case count will change between invocations of sum, making the behavior hard to trace, and ultimately resulting in the error that you observe.

You should pass the index along with the array to make it work:

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

Unlike an implementation that increments the count external to the method, this implementation can be called concurrently on multiple threads without breaking.