You are here:

C++/divide and Conquer Algorithm



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!



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:

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


All Answers

Answers by Expert:

Ask Experts




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

post graduate engineer

©2016 All rights reserved.