Recursively finding a sum of perfect squares in a list

Question

I'm trying to recursively find a sum of perfect squares in a dynamically allocated list. For some reason, my function keeps overlooking the first element.

*A is the pointer to the first element of the array. n is the number of elements, meaning they are in range from 0 to n-1. When n is less than or equal to zero, n-1 isn't a valid index so I'm returning 0 to the sum of perfect squares.

int sum(int *A, int n)
{
    int i, num = 0;

    if (n <= 0)
        return num;

    for (i = 0; i < A[n - 1]; i++) {
        if (i*i == A[n - 1]) {
            num = A[n - 1];
        }
    }
    return num + sum(A, n - 1);
}

Why does the first element always get overlooked? It works for all the other elements in the list.

EDIT: I've tried calling the function again and it seems that only number 1 got overlooked. That was fixed by modifying the for loop condition, so the solution would be:

int sum(int *A, int n)
{
    int i, num = 0;

    if (n <= 0)
        return num;

    for (i = 0; i <= A[n - 1]; i++) {
        if (i*i == A[n - 1]) {
            num = A[n - 1];
        }
    }
    return num + sum(A, n - 1);
}

Answer 1

For starters as the array pointed to by A is not changed the pointer should be declared with the qualifier const.

Sizes of objects in C are estimated by using the type size_t. So the second parameter should be declared as having the type size_t.

Also the sum of perfect squares can be larger than an object of the type int can accomodate. So it is better to use the type long long int as the return type.

And if I am not mistaken 0 is not a perfect square. Though it is not very important nevertheless the loop can start with 1 instead of 0..

I can suggest the following solution.

#include <stdio.h>

long long int sum( const int *a, size_t n )
{
    int perfect_square = 0;

    if ( n )
    {
        int i = 1;

        while ( i * i < a[n-1] ) i++;

        if ( a[n-1] == i * i ) perfect_square = a[n-1];
    }

    return n == 0 ? perfect_square : perfect_square + sum( a, n -1 );
}


int main(void) 
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    const size_t N = sizeof( a ) / sizeof( *a );

    printf( "The sum of perfect squares is %lld\n", sum( a, N ) );

    return 0;
}

The program output is

The sum of perfect squares is 14