Understanding recursion by parts difficulty

Code:

---

float vecSum(int N, float *X)
{
if (N > 1)
{
int nL = N/2, nR = N-nL;
float sumL, sumR;
sumL = vecsum(nL, X);
sumR = vecsum(nR, X+nL);
return(sumL+sumR);
}
else if (N == 1)
return(*X); /* sum 1 elt is elt */
/* else if (N == 0) */
return(0.0); /* sum of 0 elts is 0 */
}

---

any explanation of how exactly the sumL and sumR and storing the correct info in order to actually add the sum of vector X would be appreciated

Properly indented could would be much easier to read (it makes it easier for us to help you). This is also a great time to mention just how useful adding a few printf's and writing a small program to test this can be.

Code:

---

#include <stdio.h>


void indent(int how_much)
{
    int i;
    for (i = 0; i < how_much; i++)
        printf("  ");
}


float vecSum(int N, float *X, int indt)
{
    int i;
    indent(indt);
    printf("N = %d, arr = ", N);
    for (i = 0; i < N; i++)
        printf("%5.2f ", X[i]);
    putchar('\n');
    if (N > 1)
    {
        int nL = N/2, nR = N-nL;
        indent(indt);
        printf("nL = %d, nR = %d\n", nL, nR);
        float sumL, sumR;
        indent(indt);
        printf("Calling vecSum on left half of array\n");
        sumL = vecSum(nL, X, indt + 1);
        indent(indt);
        printf("Calling vecSum on right half of array\n");
        sumR = vecSum(nR, X+nL, indt + 1);
        indent(indt);
        printf("sumL = %5.2f, sumR = %5.2f, total = %5.2f\n", sumL, sumR, sumL + sumR);
        return(sumL+sumR);
    }
    else if (N == 1) {
        indent(indt);
        printf("only one element, returning %5.2f\n", *X);
        return(*X); /* sum 1 elt is elt */
    }
    /* else if (N == 0) */
    return(0.0); /* sum of 0 elts is 0 */
}


int main(void)
{
    float arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vecSum(5, arr, 0);
    return 0;
}

---

Play around with that, change the size and/or elements of arr. See if that helps make sense of what is happening.

EDIT: Added some indentation to make the stages of recursion clearer.

Well it's trying to do the same thing as this:

Code:

---

void vecsum2 (int N, float *X, float *sum)
{
    if (N > 1)
    {
        vecsum2 (N/2, X, sum);

        vecsum2 (N - N/2, X + N/2, sum); /* tail recursion */
    }
    else if (N == 1)
    {
        *sum += *X;
    }
    /* else nothing */
}

---

Maybe that's easier to watch in a debugger? Most of the actual work is done by the tail recursion, and the earlier call just makes sure that we call that enough times. If you can, watch how X moves around, it explains quite a bit about how and why this is working.