Expert: vijayan - 1/21/2009

Question
Hi,

I have created a Recursive and NonRecursive algorithm for calculating the
sum of integers.  I've looked at the basic framework of how a Divide and
Conquer Algorithm is supposed to work, but I just don't understand the logic
of using this technique within my code (specifically for the Recursive
function).  Any ideas or pseudocode would be very helpful!

Thanks,

Xin

http://paste2.org/p/133085

Answer
The basic idea behind a recursive function is that you can solve a problem by breaking it into smaller pieces, solving each of those smaller pieces by breaking them up into even smaller pieces, and so on.

The two basic parts of a recursive function are:

1. the base case - without a base case, your recursive function will never terminate. For sum of elements in an array, startIndex == endIndex is the base case. in this case, there is only one element and Array[startIndex] is the sum.

2. the recursive part - this part implements the concept that you can 'solve the biggger problem' by solving a smaller problem. if I tell you that I have a function f() that can compute the sum of elements in an array from positions 0 to 100 and then ask you to compute the sum of numbers from 0 to 101, you could easily write the expression f() + Array[101] to give me the correct answer.

here are a couple of links which give a detailed explanation of recursive functions:
http://www.cs.princeton.edu/~lworthin/126/precepts/recursion.html
http://en.wikipedia.org/wiki/Recursion_(computer_science)

i apologize for the delay in answering your question. i was hospitalized.