Recursive Function returning 0 in C

Question

I am trying to implement an interpolation method called Lagrange interpolation, using a particular method called Neville's method.

My problem is that the function is returning 0, and I am not certain as to why.

It is a recursive method that eventually should return an estimation of the output given an input based on data it has interpolated from.

The value P_0,1,2,...,n-1,n calls P_1,2,...,n-1,n and P_0,1,2,...n-1. P_1,2,...,n-1,n calls P_2,...,n-1,n and P_1,2,...,n-1. When it gets down to P_0, P_1, ... or P_n, it is calling f(x_0), f(x_1), ... or f(x_n), which are known beforehand as it is part of the interpolated data.

Before I show the code for the recursive function, I should mention that the interpolated data is a 2d array, first column are input values (x) and second column are output values (y). It is simply a randomly sorted 2d array with x and y both being equal.

I also created a function that grabs a slice of the array, given the beginning and ending indices, and returns as another 2d array. This is to assist in the interpolating function.

Shown below:

int **index_array(int **array, int beg, int stop)
{
    int i, **new_array, new_array_length;

    new_array_length = stop - beg + 1;

    new_array = malloc(sizeof(int *) * (new_array_length));

    for (i = 0; i < new_array_length; i++)
    {
        new_array[i] = malloc(sizeof(int)*2);
    }

    for (i = 0; i < new_array_length; i++)
    {
        new_array[i][0] = array[beg + i][0];
        new_array[i][1] = array[beg + i][1];
    }

    return new_array;
}

Here is the interpolating function:

int Lagrange_Neville(int **array, int n, int x)
{

    int i;

    if (n == 1)
    {
        return array[0][1];
    }

    return 1/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));
}

My main():

int main(void)
{

    srand(time(NULL));

    int **array, **new_array, n, beg, end, x;

    n = 10;
    beg = 5;
    end = n-1;
    x = 5;

    array = createArray(n);

    printf("First array:\n");
    print_array(array, n);

    new_array = index_array(array, beg, end);

    printf("New array from indices %d to %d of the old array:\n", beg, end);
    print_array(new_array, end-beg+1);

    printf("Output of lagrange interpolating estimated at x = %d\n", x);
    printf("%d\n", Lagrange_Neville(array, n, x));

    return 0;
}

And my output:

First array:
2 2
5 5
7 7
9 9
12 12
13 13
16 16
17 17
20 20
21 21

New array from indices 5 to 9 of the old array:
13 13
16 16
17 17
20 20
21 21

Output of lagrange interpolating estimated at x = 5
0

I appreciate any help.

Answer 1

The zero is coming from the first term in what the function returns:

1/(array[n-1][0] - array[0][0])

You're performing integer division of 1 by a number larger than one. Since the mathematical result is less than 1, and since the fractional part of the number gets truncated, you end up with 0.

You need to do floating point math here by making at least one operand a double. You should probably return a double from your function as well.

double Lagrange_Neville(int **array, int n, int x)
{

    int i;

    if (n == 1)
    {
        return array[0][1];
    }

        //   v---- constant of type double
    return 1.0/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));
}

Answer 2

The first thing that jumps out is that your Lagrange_Neville() function is declared as returning int, and you're using integer division here:

return 1/(array[n-1][0] - array[0][0]) * ((x - array[0][0])*Lagrange_Neville(index_array(array, 1, n-1), n-1, x)-(x-array[n-1][0])*Lagrange_Neville(index_array(array, 0, n-2), n-1, x));

Because array is declared as containing integers, and 1 is obviously an integer, you're going to get an integer result in that first division, which likely gives 0. You can change the division to give a float result by using 1.0 for the numerator in place of 1, but since the function returns int you'll still get an answer that's converted to that type, which may not be what you want. Try declaring the function so that it returns a floating point type instead.