How to fix the execution of this recursion code?

Question

In this basic array problem, I need to add the sum or the value of the previous index of the array to the current index value using recursion.

For example, {5,3,1,2} becomes {5,8,9,11}.

Since the 0th index is the first index so it remains as it is.

I think my code is correct but instruction pointer is not flowing according to my dry run and the return statement (for the base condition) is not executing. Since I have my code in Java, after adding try-catch I'm getting output as expected. But adding try-catch is not the solution.

class kr1
{
    public static void main(String[] args) {
        int a[]= {5,1,3,9,5};
        a=addr (a,0,a.length);
        for (int i:a)
            System.out.print (i +" ");
    }

    static int[] addr(int a[],int i,int n)
    {
        if (i==0)
            addr(a,i+1,n);
        if (i==n-1)
        {
            a[i] = a[i]+a[i-1];
            return a ; //this return statement is not executing
        }
             //this below part is executing even if i has reached to n-1
        a[i] = a[i] + a[i-1];
        addr(a,i+1,n);
        return a;
    }
   }

Zhiyuan-Amos · Answer 1 · 2019-04-20T05:33:58.253

static int[] addr(int a[],int i,int n)
{
    if (i==0)
        addr(a,i+1,n); // buggy
    if (i==n-1)
    {
        a[i] = a[i]+a[i-1];
        return a;
    }

    // code executed after if (i==0) block returns
    a[i] = a[i] + a[i-1];
    addr(a,i+1,n);
    return a;
}

As there is no return a; inside the if (i==0) block, the subsequent code block will be executed. Since the value of i is 0, a[i-1] is equivalent to a[-1], which results in an ArrayOutOfBoundsException being thrown.

You can resolve this by:

Adding a return a; inside the if (i==0) block.
Having the main function to call this recursive function with i = 1. That way, you can remove the if (i==0) block.

Since Java arrays are pass-by-reference, you actually don't need to return the array.

class kr1
{
    public static void main(String[] args) {
        int a[]= {5,1,3,9,5};
        addr (a,0,a.length);
        for (int i:a)
            System.out.print (i +" ");
    }

    static void addr(int a[],int i,int n)
    {
        if (i==0)
            addr(a,i+1,n);
            return;
        if (i==n-1)
        {
            a[i] = a[i]+a[i-1];
            return;
        }
        a[i] = a[i] + a[i-1];
        addr(a,i+1,n);
    }
   }

That would make the code more readable.

that was a silly mistake done by me..and for method returning value part.. you are correct..i was initially using void..but when i was not getting the expected result..i was trying by returning the array — vrnvav97, Apr 20 '19 at 13:02

ggorlen · Answer 2 · 2022-08-02T15:59:43.993

The problem is the first conditional,

if (i==0)
    addr(a,i+1,n);

Here, addr is called recursively, but after the call returns, execution continues on down to the end of the function and the line a[i] = a[i] + a[i-1]; throws an AIOOBE at a[-1]. The fix is:

if (i==0)
    return addr(a,i+1,n);

which prevents the rest of the function from executing.

Having said that, I'd like to suggest the following simplification:

class Main {
    public static void main(String[] args) {
        var res = addr(new int[] {5, 1, 3, 9, 5}, 1);
        System.out.println(java.util.Arrays.toString(res));
    }

    static int[] addr(int a[], int i) {
        if (i < a.length) {
            a[i] += a[i-1];
            return addr(a, i + 1);
        }

        return a;
    }
}

Since this is an in-place algorithm, I suggest making it void:

class Main {
    public static void main(String[] args) {
        var a = new int[] {5, 1, 3, 9, 5};
        addr(a, 1);
        System.out.println(java.util.Arrays.toString(a));
    }

    static void addr(int a[], int i) {
        if (i < a.length) {
            a[i] += a[i-1];
            addr(a, i + 1);
        }
    }
}

Writing a wrapper that handles the easy-to-mess-up 1 index for the initial call is wise.

Taking a step back, the problem is actually a poor fit for recursion in languages that don't provide tail call optimization because the call stack grows linearly in proportion to the input. That means you'll overflow the stack for medium-sized arrays of a few thousand elements. The best approach is to use a loop.

score 0 · Answer 3 · answered Apr 20 '19 at 05:18

static int[] addr(int a[],int i,int n)
{
    if (i==0)
        return addr(a,i+1,n);
    if (i==n-1)
    {
        a[i] = a[i]+a[i-1];
        return a ; //this return statement is not executing
    }
    //this below part is executing even if i has reached to n-1
    a[i] = a[i] + a[i-1];
   return addr(a,i+1,n);
}

In recursion when recalling the function, you should return the value of the function call, you didn't do that. So I just added a return to the recalling functions and it worked. Also, check your algorithm, it fails when the length if the array is one, you could add a simple check to ensure that when the array size is 1 or zero the array is returned back and no manipulation is done to the array. Cheers.

You are right..my algorithm is wrong for array size either 1 or 0 :).. I will correct it — vrnvav97, Apr 20 '19 at 13:06

score 0 · Answer 4 · answered Apr 20 '19 at 05:27

0

just change this part of your code

if (i==0)
    addr(a,i+1,n);

to this one

if (i==0){
     addr(a,i+1,n);
     return a;
}

answered Apr 20 '19 at 05:27

Pythoscorpion

166
1
10

How to fix the execution of this recursion code?

4 Answers4