Resursion to add n by n elements in an array



Algorithm sum(A,n)

    Input: A, an n by n array

    Output: The sum of elements in A


    if n=1 then return A[0][0]


    s  ← 0

    while i < n -1 do

        s ← s + A[i][n-1] + A[n-1][i]

     return  A[n-1][n-1] + s  + sum(A,n-1)



Runs in O(n) time.

We work the array from the outside to the inside until n = 1


Implementation Java






public static int sum(int A[][], int n)



    if(n == 1) return A[0][0];


    int s = 0;


    for(int i = 0; i < n – 1 ; i++)   s+= A[i][n-1] + A[n-1][i];


    return A[n-1][n-1] + s  + sum(A,n-1);



This entry was posted in Code samples. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *