You are here:

- Home
- Computing/Technology
- C/C++
- C++
- divide and Conquer Algorithm

Advertisement

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

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.

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

about 15 years or so**Education/Credentials**

post graduate engineer