CODEWITHSUNDEEP
carrays
user2227862
user2227862

Reputation: 605

A recursive function that finds the sum of an array in c

I have to find a recursive function that finds the sum of an array by repeatedly partitioning it into 2 almost equal parts?

What should be my approach ? How should i do this?

I do not ask for a code!just a hint or direction to approach this problem!

Upvotes: 1

Views: 498

Answers (6)

paxdiablo
paxdiablo

Reputation: 881303

That's reasonably easy. Every recursive algorithm on a data set should be defined in terms of the same algorithm (a) on a simpler data set, and with a terminating condition.

In this case, the terminating condition is a data set of size 1 where you just return the value, otherwise each level of recursion is simply performing the same task on both halves then adding the two results together together.

That would be something like the following pseudo-code:

def sumof (array, start, end):
    if start == end:
        return array[start]
    midpoint = (start + end) / 2
    return sumof (array, start,        midpoint) +
           sumof (array, midpoint + 1, end     )

Now all you have to do is convert that to your language of choice and debug any potential problems at the edge cases.

Let's see how that works on the numbers 10 through 16 in a zero-indexed, seven-element array. If you run that algorithm through your head, or on paper if you haven't yet become more machine than man like I have :-), you'll get something like this:

Level 0, call sumof (array, 0, 6):
    Level 1, call sumof (array, 0, 3)
    +---Level 2, call sumof (array, 0, 1)
    |   +---Level 3, call sumof (array, 0, 0), returns 10
    |   |---Level 3, call sumof (array, 1, 1), returns 11
    |   Add together to get 21
    |   Level 2, call sumof (array, 2, 3)
    |   +---Level 3, call sumof (array, 2, 2), returns 12
    |   |---Level 3, call sumof (array, 3, 3), returns 13
    |---Add together to get 25
+---Add together to get 46
|   Level 1, call sumof (array, 4, 6)
|       Level 2, call sumof (array, 4, 5)
|       +---Level 3, call sumof (array, 4, 4), returns 14
|       |---Level 3, call sumof (array, 5, 5), returns 15
|   +---Add together to get 29
|   |---Level 2, call sumof (array, 6, 6), returns 16
|---Add together to get 45
|
Add together to get 91

(a) This isn't always the case, sometimes the actual algorithm changes as well but it's rarer to see that.

Upvotes: 6

Deepu
Deepu

Reputation: 7610

Call the followingfunction in C, If the size of the original array is N, Initially call the function as,

sum=rec_sum(0,N-1);

The function is shown below, 

int rec_sum(int array[],start,end)
{
   if(start==end)
   {
     return array[start];
   }
   else
   {  
       return rec_sum(array,start,(start+end)/2) + rec_sum(array,(start+end)/2+1,end);
   }
}

Upvotes: 0

James Hallen
James Hallen

Reputation: 5014

There is an algorithm for sorting which uses a similar prinicple for partioning to sort http://www.algolist.net/Algorithms/Sorting/Quicksort

Upvotes: 1

Adam Siemion
Adam Siemion

Reputation: 16029

This will be a Divide and conquer algorithm:

  1. Create a function that will take below arguments:
    • array
    • start index
    • end index
  2. When the start index is equal to the end index the function should return the value from the array at position the start (or end) index
  3. Otherwise it should return the sum of two calls of the same function with below arguments:
    • array, start index, (start + end) index/2
    • array, (start + end) index/2+1, end index

Upvotes: 1

Summer_More_More_Tea
Summer_More_More_Tea

Reputation: 13356

Recursive function relates highly to the divide-and-conquer technique. Two aspects you should concern is

  1. How to divide the large problem into smaller easy-solving problems;
  2. How to merge the solution to all the small problems as a solution to the original larger problem.

Of course you can partition the array into two similar-sized problem. The next step is how to merge the results. Let us see your efforts :p.

Upvotes: 0

LZR
LZR

Reputation: 958

This is a "Divide and conquer" approach. See more here

Upvotes: 2

Related Questions