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!
3
-
2We are going to solve your homework for you.aggsol– aggsol2013-06-06 13:16:40 +00:00Commented Jun 6, 2013 at 13:16
-
it's a weird kind of homework: asking for a recursive sum on an array, where it's definitely slower than the simpler iteration, and not asking to find a value in a sorted tree (or array), where recursion would shine ? ... in other words, why asking to use recursion on something where it should not be used, and not on something where it should? ...Olivier Dulac– Olivier Dulac2013-06-06 13:48:22 +00:00Commented Jun 6, 2013 at 13:48
-
@OlivierDulac, if the intent is to just learn recursion, then probably any exercise is as good as any other. I would hope at some point they are taught when to consider recursion as per your comment.paxdiablo– paxdiablo2013-06-06 13:50:24 +00:00Commented Jun 6, 2013 at 13:50
Add a comment
|
6 Answers
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.
5 Comments
Grijesh Chauhan
do you have any tool to draw this tree ?
paxdiablo
@GrijeshChauhan, no, all "sweat of the brow", I'm afraid. I did it manually. Although I don't doubt you could modify the pseudo-code (after conversion to a real language) to generate such output.
Grijesh Chauhan
Yes..btw if you need to draw a complicate diagram you can use asciiflow I like acsii art.
Hut8
Emacs has
artist-mode and picture-mode that can draw things sort of like that. Good job, though!paxdiablo
@GrijeshChauhan, excellent find. Actually, I may implement something similar locally in case that website ever disappears, but I've bookmarked it for now.
This will be a Divide and conquer algorithm:
- Create a function that will take below arguments:
- array
- start index
- end index
- 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
- 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
Comments
There is an algorithm for sorting which uses a similar prinicple for partioning to sort http://www.algolist.net/Algorithms/Sorting/Quicksort
Comments
Recursive function relates highly to the divide-and-conquer technique.
Two aspects you should concern is
- How to divide the large problem into smaller easy-solving problems;
- 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.
answered Jun 6, 2013 at 13:09
Summer_More_More_Tea
13.6k12 gold badges54 silver badges87 bronze badges
Comments
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);
}
}
