Like Tree1Likes
  • 1 Post By anduril462

Understanding recursion by parts difficulty

This is a discussion on Understanding recursion by parts difficulty within the C Programming forums, part of the General Programming Boards category; Code: float vecSum(int N, float *X) { if (N > 1) { int nL = N/2, nR = N-nL; float ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    2

    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

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    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.
    Last edited by anduril462; 12-14-2012 at 06:49 PM.
    stahta01 likes this.

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,622
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion with matrix parts
    By onako in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2010, 06:44 AM
  2. Understanding recursion - Pls help
    By jill123 in forum C Programming
    Replies: 3
    Last Post: 09-22-2009, 01:11 PM
  3. Need help with understanding a recursion function
    By CS_Student8337 in forum C Programming
    Replies: 7
    Last Post: 02-10-2009, 05:52 AM
  4. Understanding recursion
    By caduardo21 in forum C Programming
    Replies: 4
    Last Post: 08-19-2005, 06:06 PM
  5. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 03:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21