Recursive sum of an array in C

Question

Hello I'm learning recursion in C and I am trying to find the sum of the elements.

This is my main:

int main()
{


    int arr[] = {1,2,3,4,5};
    int sum;
    sum = arr_sum(arr,4);
    printf("\nsum is:%d",sum);



    return 0;

}

And my recursive function:

//n is the last index of the array

int arr_sum( int arr[], int n )
{ // must be recursive

    int sum = 0;
    //base case:
    if (n < 0) {
        return sum;
    } else{
        sum = sum + arr[n];
    }
    //make problem smaller
    arr_sum(arr,n-1);
}

The output is:

sum is :0 

Solution 1

You could add a third argument, which is the running total calculated so far (start it as 0).

When you recursively call the function, pass the running total.

int arr_sum( int arr[], int n, int sum )
{ // must be recursive

    if (n < 0) {
         return sum;
    }

    sum += arr[n];

    return arr_sum(arr, --n, sum);
}

Alternatively, you change it to not require passing the sum variable like so.

int arr_sum( int arr[], int n )
{ // must be recursive

    if (n < 0) {
         return sum;
    }

    return arr[n] + arr_sum(arr, n - 1);
}

In this way, it is similar to finding a number in the Fibonacci sequence.

Solution 2

Try this for your recursive function:

int arr_sum( int arr[], int n ) { 
  if (n < 0) {
    //base case:
    return 0;
  } else{
    return arr[n] + arr_sum(arr, n-1);
  }
}

you need to add your n-th case to your n-1 case until you get to the base case.

Solution 3

Try this modified version of your program and work out on pen/paper the way it flows through. Hope it helps.

#include <stdio.h>

//n is the last index of the array
int
arr_sum(int arr[], int n )
{
    //base case:
    if (n == 0) {
        return arr[0];
    }

    return (arr[n] + arr_sum(arr,n-1));
}

int
main(void)
{
    int arr[] = {1,2,3,4,5};
    int sum;

    sum = arr_sum(arr,4);
    printf("\nsum is:%d\n",sum);

    return 0;
}

Solution 4

You are not returning any thing from else part.You also have return from that. like.

return arr_sum(arr,n-1)+arr[n];

so this call the function again and again until n will be zero.

you got my point?

View more solutions

Comments

[MeesterMarcus]

Ahh okay that makes sense. It is working now with sum outside. Is there a way I could do this recursively with only the parameters (int arr[], int n)?

[jogojapan]

@MarcusLorenzana　Why don't you look at the duplicate question? It's all there.

[MeesterMarcus]

That fixed it! Added a sum parameter and it is working now. Is there a way to do it with only those two parameters?

[Maximin]

@Marcus Lorenzana :If you found useful, tick it as correct. I didn't get you. Now itself you are using only those parameters.

[MeesterMarcus]

Oh thanks didn't notice that

[user3167101]

@MarcusLorenzana Yep, try this. The code I posted isn't the most elegant solution, but if you're having difficulty with recursion it may be easier to comprehend.

[imran]

do not declare sum outside your function. That is not proper recursion. You do not even need to have a variable named sum.

[MeesterMarcus]

Thanks! Just wondering because the sample exam has it in such a way.

[MeesterMarcus]

Got you, thanks. My function was returning to 0 each call

[Maximin]

@imran His requirement is to use only two parameters. Can u suggest me a better way than this?

[imran]

@Maximin see my answer, this could have easily been googled.

[Maximin]

yeah just saw among comments in this question. codepad.org/H2zIdLKt

[MeesterMarcus]

Thank you this works nicely as well

[MeesterMarcus]

I kind of just wanted to be nudged in the right direction so I could understand it more

[MeesterMarcus]

Thank you I guess I get confused at times the order of execution in memory with recursion but I understand this bit perfectly now