473,327 Members | 1,952 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

this program using recursion is not working

this is the question:: Problem 2: Find the Numbers, (K Narayan Kumar, CMI)
This is a rather simple problem to describe. You will be given three numbers S, P and k. Your task is to find if there are integers n1, n2,...,nk such that n1 + n2 +...+ nk = S, n1 * n2 * ... * nk = P. If such integers exist, print them out. If no such sequence of integers exist, then print "NO".
For example if S=11, P=48 and k=3 then 3, 4 and 4 is a solution. On the other hand, if S=11, P=100 and k=3, there is no solution and you should print "NO".
Input format
A single line with three integers S, P and k.
Output format
</>
A single word "NO" or a seqence of k integers n1, n2,..., nk on a single line. (The ni's must add up to S and their product must be P).
Test data
You may assume that 1 = k = 4, 1 = S = 1000 and 1 = P = 1000.
Example
We now illustrate the input and output formats using some examples.
Sample input 1:
11 48 3
Sample output 1:
3 4 4
Sample input 2:
11 100 3
Sample output 2:
NO





here is my program::
/*NOT WORKING----program to find the numbers using recursion*/
Expand|Select|Wrap|Line Numbers
  1. #include<stdio.h>
  2. int main()
  3. {
  4.     int s,p,a=0,b=0,c=0,match=0;
  5.     printf("\nEnter Sum & Product: ");
  6.     scanf("%d %d",&s,&p);
  7.     recursive (s,p,&a,&b,&c,1,&match);
  8.             if (match==1)
  9.                 printf("\nThe numbers are %d %d %d",a,b,c);
  10.             else
  11.                 printf("\nNumbers are not found.");
  12.     return 0;
  13. }
  14.  recursive (int s,int p,int *a,int *b,int *c,int level,int *match)
  15. {
  16.    int i=0;
  17.    printf("\nlevel=%d\t\ta=%d,b=%d,c=%d",level,*a,*b,*c);
  18.     if (level==3)
  19.       {
  20.           if (s==p)
  21.             {
  22.                 *c=s;
  23.                 *match=1;
  24.             }
  25.         return;
  26.       }
  27.  
  28.      if (*match==1)
  29.         {
  30.              return;
  31.         }
  32.  
  33.          //printf("\ndebug");
  34.     for (i=2;i<p/2;i++)
  35.         if (p%i==0)
  36.             {
  37.               //printf("\ncase level=%d\t\ti=%d,p=%d",level,i,p);
  38.                if (level==2)
  39.                  *b=i;
  40.                  if (level==1)
  41.                         *a=i;
  42.                 p=p/i;
  43.                 s=s-i;
  44.                 //printf("\nlevel=%d\t\t,p=%d,s=%d",level,p,s);
  45.                 recursive (s,p,a,b,c,level+1,match);
  46.             }
  47.         if (i>=s)
  48.             return;
  49. }
May 19 '13 #1
6 1962
Nepomuk
3,112 Expert 2GB
One problem I can see right away is that you're not scanning for k (which should be the third number given) and you therefore don't use it in the calculation. From what I understand, k should be the number of numbers used for the product and sum, so it's relevant.
Instead, you pass 3 variables exactly (a, b and c). The right way to do this would be to either use an array or (to go "full recursion") pass no variables at all but rather have the recursive function have one local variable which it prints.
May 19 '13 #2
whodgson
542 512MB
What Nepomuk says is not quite right. 'k' is not required to find the factors of P using tail recursion. For example 48 yields factors 2 2 2 2 3 which sums to eleven as required. k=3 says combine the first two and second two factors to produce 3 4 4 which again sums to eleven.
Here is some code which find factors which may assist in finding your own errors.

Expand|Select|Wrap|Line Numbers
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. cout<<"This program factors a number\n";
  8. int n ,sum=0;  //the number to factor
  9. while(n)
  10.   {
  11.     cout<<"\nEnter an integer (-1 to quit) ";
  12.     cin>>n;
  13.     if(n==-1)return 1;
  14.     cout<<"The factors of "<<n<<" are ";
  15.     int lastFactor = 2;
  16.        while( lastFactor < n )
  17.          {
  18.                 if( n % lastFactor == 0 )
  19.              {       cout << lastFactor << ' ';
  20.                      n /= lastFactor;
  21.  
  22.              } else
  23.  
  24.                ++lastFactor;//tail recursion
  25.  
  26.          }
  27.     if( n != 1 )
  28.     cout << n;
  29.  
  30.  
  31.   }
  32.  
  33.  
  34. cout<<endl;
  35.  
  36. cin.get();
  37. return 0;
  38. }
/*This program factors a number

Enter an integer (-1 to quit) 48
The factors of 48 are 2 2 2 2 3
Enter an integer (-1 to quit) -1

Process returned 1 (0x1) execution time : 12.672 s
Press any key to continue.
May 21 '13 #3
Nepomuk
3,112 Expert 2GB
Uhm whodgson... We seem to have very different ideas about what recursion is - for one thing, your solution only has one function (the main function) which doesn't call itself but rather uses loops to find a solution. That is what I would call an iterative solution. How exactly that is supposed to be tail recursive I don't know...

Also, I didn't say that k necessarily had to be passed to the recursive function (though with the solution I had in mind it would be); I said it was relevant. For that reason, it HAS TO at least be scanned and used in some way. Passing exactly three variables for the output means, that the solution would have a fixed k=3 which is not what the question asks for.
May 21 '13 #4
whodgson
542 512MB
From Nepomuk's last post.
"it HAS TO at least be scanned and used in some way."
Why?... if it is not required to establish the value of P or S it must be redundant or similar.
By the way tail_recursiveness is explained (defined) in the reference you provided which is said to be allied to the iterative concept and only a special case of the function which calls itself.
May 22 '13 #5
Nepomuk
3,112 Expert 2GB
Why?... if it is not required to establish the value of P or S it must be redundant or similar.
From the original post:
You will be given three numbers S, P and k. Your task is to find if there are integers n1, n2,...,nk such that n1 + n2 +...+ nk = S, n1 * n2 * ... * nk = P.
So, we want exactly k numbers as a result. How do you want to do that if you don't even know what k is?
By the way tail_recursiveness is explained (defined) in the reference you provided which is said to be allied to the iterative concept and only a special case of the function which calls itself.
Actually, no. It sais:
Tail-recursive functions are functions in which all recursive calls are tail calls…
Now, tail calls can be used in the iterative paradigm. But tail recursion is the combination of tail calls and recursion. And pretty early in the recursion article it sais:
Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code.
If you had ever used one of the languages mentioned (e.g. Haskell) you would really understand the difference - if you want to learn functional programming I can only recommend it. But that's beside the point here.
The task here is clearly to write a recursive program (as stated by the title) and the op is asking what is wrong with his code. So I personally will be getting back to that problem.
May 22 '13 #6
Oralloy
985 Expert 512MB
Aniruddha123,

As Nepomuk observed, you aren't reading the value of k in your code, so you do not know how many factors to resolve your sum and product into. This is the first thing you should fix.

Secondly, your function recursive does not take k as an input. It seems that the parameter level takes the place of k, but it is forced to the value three (3) in your main.

Thirdly, it looks like the internal structure of your function strictly looks to a depth of three (3). Which is not what the specification was. So, regardless of your top-level problems, you will need to work out a better recursive algorithm, once you get the top-level details sorted out.

Regards,
Oralloy
May 22 '13 #7

Sign in to post your reply or Sign up for a free account.

Similar topics

5
by: jbutler67 | last post by:
Does anyone have C++ source code for a Tic Tac Toe game where recursion is used? I am just learning C++ and have been trying to write a program where the user plays against the computer. The...
10
by: free2cric | last post by:
Hi, FOllowing is a program which is written by someone else. Its output is a wonderful poem. I dont understand how it works really. can anyone tell. thanks cric #include <stdio.h> main(int...
6
by: PengYu.UT | last post by:
Hi, I couldn't see what is wrong with the following program. Would you please help me? Thanks, Peng g++-3.4 -MM -g main.cc .dep
5
Rooro
by: Rooro | last post by:
For the List class, add a Boolean-valued function that determines whether the data items in the linked list are arranged in ascending order. How can i do this using recursion
0
by: sadeceben | last post by:
the aim is to obtain a particular number using a subset of given values and four arithmetic operations. Note that you are allowed to use each given value at most once. For example, suppose that you...
13
by: Raman | last post by:
Hi All, Could any one tell me How to concatenate two strings using recursion. And also how to trim a string using recursion.(in C, offcourse) Regards, Raman Chalotra
1
by: faize | last post by:
I want to Write a _real time_ perl program that will take the output of tcpdump in ASCII format. Every second this program will output to screen the average number of packets as well as the average...
1
by: mitchy102 | last post by:
//FILE: StkFigMn.cpp //DRAW A STICK FIGURE (Main function only) #include <iostream> using namespace std; //Functions used... //DRAW A CIRCLE void draw_circle ();
1
by: jobie | last post by:
i am currently reading Francis Glassborow's You can do it .i tried building this program using vs2008 // first program typed in by // on #include "playpen.h" #include <iostream> int...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.