You are here:

C++/recusive functions

Advertisement


Question
To explain what I am trying to do let me describe an example math problem I want to be able to solve. You start with a set of integers from 1 to some number k. You want to add up numbers from this set until the sum equals some number n. For instance, if k = 3 and n = 5, one way to add up the numbers is 1 + 2 + 2. I want to be able to generate all possibilities of different ways to add up numbers from the set to get the desired sum. Plus, order counts so 1 + 2 + 2 is different than 2 + 1 + 2. Now with k = 3 and n = 5, you could simply write a function with 5 nested for loops each going from 1 to 3. But with n being unknown you wouldn't know how many for loops you would need. I have tried to write a recursive function to do this but it doesn't work because every time it calls itself it reinitializes the variable of the for loop. My recursive function only computes the first possibility which is 1 + 1 + 1.... Can you think of a way to do what I am trying to do? If you could give me a crude exapmle of code that would be very helpful. If it helps at all I am using Borland Builder 6.0 version of C++. Thank You Very Much.

Answer
Dear Gina,
Thankyou for you question. Well that is what
somewhat related to the topic of Permutation
combinations and you can find the algorithm for
it Advance discrete Mathematics.

Here is something that might help.   I took this algorithm from my discrete mathematics book:

// This procedure prints all the r-combination of n elements.
// for example, if n = 3, then the 2-combination of {1,2,3} are
// {1,2}, {1,3}, {2,3}. Also note that
//          P(n,r)
//    C(n,r) = ------
//          r!
// and
//    P(n,r) = n(n-1)(n-2) ... (n-r+1),  r <= n

procedure combination(r,n)
 for i := 1 to r do
   s[i] = i
 print s[1], ..., s[r]    // print the first r-combination
 for i := 2 to C(n,r) do
   begin
   m := r
   max_val := n
   while s[m] = max_val do
     // find the rightmost elemenet not at its maximum value
     begin
     m := m - 1
     max_val := max_val - 1
     end
   // the rightmost element is incremented
   s[m] := s[m] + 1
   // the rest of the elements are the successors of s[m]
   for j := m + 1 to r do:
     s[j] := s[j-1] + 1
   print s[1], ..., s[r]   // print the ith combination
   end
end combination

I'm not sure it will remove your "nested loops" problem though. Same procedure you can try to implement with the
Summing algorithms. I hope this will help you in someway.

Don't be afraid to ask any question. I will do my best
to clarify your concepts.

Regards
Professional

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Professional

Expertise

I can answer any question about functions,pointers,structures,object oriented programming basics of classes and data structures.My strong field is structured programming.

Experience

I have got 2 years experiece under C . I am able to answer about the structured concepts pointers to a little extent,OOP concepts. I have also experience in data Strucutres like Linked List, Stacks , Queues, Heaps, B Trees, Red Black Trees. I will try to satisfy with my knowledge. I am the Student of an expert here Martin, what i have learnt today, i just owe my every knowledge to him. He is the greatest.

©2016 About.com. All rights reserved.