Not able to understand this recursion

Question

The input is {4,7,3,6,7} and The output is:

[81]
[40, 41]
[21, 19, 22]
[11, 10, 9, 13]
[4, 7, 3, 6, 7]

The recursive program I have for this is below, where I have added some print statements to understand the recursion:

import java.util.Arrays;

public class triangle_array {
    public static void print(int a[])
    {
        if(a.length==0)
            return;
        int n=a.length;
        int newa[]=new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            newa[i]=a[i]+a[i+1];
        }
         System.out.println("here1") ;
        print(newa);
         System.out.println("here2") ;
        if(newa.length!=0)
        System.out.println(Arrays.toString(newa));
    }

    public static void main(String args[])
    {
        int a[]={4,7,3,6,7};
        print(a);
        System.out.println(Arrays.toString(a));
    }

}

I got the output as:

here1
here1
here1
here1
here1
here2
here2
[81]
here2
[40, 41]
here2
[21, 19, 22]
here2
[11, 10, 9, 13]
[4, 7, 3, 6, 7]

I am not able to completely understand this recursion, From the above here statements, I understand that the print methos is being called recursively first, and when the condition fails, it returns to outside of print and goes to the line and prints "here2" 2 times and it verifies for the length of newa which is zero, until this point I understood, but in the next iterations how does the length of newa increase and how does the below condition become true, for the println statement ?

Answer 1

What would help you to understand would be to remove all println statements and instead put just one System.out.println(Arrays.toString(newa)) at the very start of the print method. The triangle will be inverted and it will make more sense.

Answer 2

Your function begin by

if(a.length==0)
        return;

So the function clearly stop when a is empty, but in that case, it stops when succession of a decreasing finish by giving a 0-length a. So if your original array have 4 entry, the function will call itself 3 times. 5 entry will call 4 times. And so on. And as each call may recall itself, 5 entry will call the functin,n giving an array of 4 entry, wich will give an array of 3 entry, untill an array of a single entry.

int newa[]=new int[n-1];
for(int i=0;i<n-1;i++)
    {
        newa[i]=a[i]+a[i+1];
    }

this is the key: newa[] is one dimension less than a (n-1, and n is length of a). that's why on each line the array size increases by 1 (last called, first printed). This is the piece that provide each time an array smaller.

The for loop simply put on newa the sum of two neighbour value of a.

This is what it will give successively:

[4, 7, 3, 6, 7] 
[4+7, 7+3, 3+6, 6+7] --> [11, 10, 9, 13]
[11+10, 10+9, 9+13] --> [21, 19, 22]
[21+19, 19+22] --> [40, 41]
[40+41] --> [81]

The less sized array is displayed first because when you call the function, it will call itself until the smallest array possible. And the structure of print make that the last called is the first printed, as last called function will be the first to finish, the other call won't finish untill the level below doesn't have finished. That's why you thought a was increasing, you must read those kind of function in the reverse order.

Regarding your print in order to debug. The long amount of "here1" is caused by the fact you print this before the function prints it output. That's why you got a lot of here1. then each function call prints it output.

And finally, regarding the last condition:

 if(newa.length!=0)

When a is [81], newa will be an array of length 0, it's to ensure you can't print a 0-length array. So this condition is always true untill the last level.

Note that putting print(newa); under that condition and removing the first part that checks a isn't an array of 0 length won't change anything in the function

Answer 3

You need to think hard to understand it properly.

Since you don't understand how newa's size decreases,I'll explain that part. Firstly,print method is called from main.
Then, 1st print starts executing,and creates newa with length 4 and stops at print(newa) while the 2nd print starts.
Then, 2nd print starts executing,and creates newa with length 3 and stops at print(newa) while the 3rd print starts.
Then, 3rd print starts executing,and creates newa with length 2 and stops at print(newa) while the 4th print starts executing.
Then, 4th print starts executing,and creates newa with length 1 and stops at print(newa) while the 5th print starts executing.
Then, 5th print starts executing,and creates newa with length 0 and stops at print(newa) while the 6th print starts executing.
Then, 6th print starts executing, and stops at return; as length is 0 at this point.

The 5th print continues and as the length is 0,it will not print anything.
The 4th print continues and prints newa (length is 1)
The 3rd print continues and prints newa (length is 2)
The 2nd print continues and prints newa (length is 3)
The 1st print continues and prints newa (length is 4)

At last,main prints the whole array.

Answer 4

In general, if there are prints in a recursive method, all the prints that come before the recursive call will be printed in the order of increasing recursion depth, and all the prints that come after the recursive call will be printed in the reverse order.

public static void demoRecursion( int n, int depth ) {

    if ( n <= 0 ) {
        return;
    }

    System.out.println( "Before recursive call, depth " + depth );

    demoRecursion( n - 1, depth + 1 );

    System.out.println( "After recursive call, depth " + depth );

}

If you call this method using demoRecursion( 3, 1 ) you'll get:

Before recursive call, depth 1
Before recursive call, depth 2
Before recursive call, depth 3
After recursive call, depth 3
After recursive call, depth 2
After recursive call, depth 1

So it's not as if a was increasing in size. It's simply that at depth 1, you have a 5 item array, at depth 2, you have a 4 item array, at depth 3, you have 3 and so on.

So because of the reverse printing effect I demonstrated above, each depth`s array is printed after the array of the deeper level, which was shorter.

If you had printed the array before the recursive call, the prints would have been in decreasing order.

Answer 5

Basically the method is repeatedly making the array smaller by summing consecutive elements. For example:

4, 7, 3, 6, 7
|/ |/ |/ |/
11 10 9  13
|/ |/ |/
21 19 22
|/ |/
40 41
 |/
 81

The way it works is that on each call, it creates a new array that is one element smaller in size called newa, and each element newa[i] is calculated according to the formula newa[i] = a[i]+a[i+1]. Obviously we want to halt sometime, we don't want to keep recursing and get a StackOverFlowException, so we stop when the input array is empty. So, in psuedo-code, the whole thing is

print(a):
    if a is empty
        escape from function
    else
       create newa array of length a.length-1
       newa[i] = a[i]+a[i+1] //fill the smaller array
       print(newa) // print the smaller array

Answer 6

The length of newa doesn't increase, it always decreases by one. The shortest one gets printed first because the recursive call is before the instruction to print the array. So it says "create the new shorter array, but then recursively handle it (which involves printing) first, then print yourself".

By the way, the way this is structured is kind of weird. Rather than print newa at the end of the print method, I think it would make more sense to print a (without the if around it), and then you also wouldn't need to print in the main method.