Resursion to add n by n elements in an array

Algorithm

 

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)

 

Comments

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 *