I have a program that is trying to find all factors of an integer given. It needs to be done in a recursion function. Right now i have code similar to just getting the prime factors of a integer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
unsignedint * find_factors_using_recursion(unsignedint x )
{
unsignedint * factor = newunsignedint[];//do i put x in here ?
for(unsignedint i = 2; i < x; ++i)
{
if(x % i == 0)
{
find_factors_using_recursion(x / i);
*factor = (factor[i] = i);
}
}
return factor;
delete [] factor;
}
When i cout the *factor = (factor[i] = i) it gives me the prime numbers of the integer passed into the function but when I return the pointer it only returns one of the prime numbers. I'm new to c++ if anyone could give me more detail of how to return pointers from functions that would be great with an example to go with it.
Line 4: You didn't specify size of an array, and it will create array of one (AFAIR) integer.
Line 11: you are never using reurn value, so any factors you find here will be lost;
Line 12: I don't understand your intentions here. Now it is equivalent to factor[0] = factor[i] = i;
Line 18: Will never execute, but if it will it would be bad: you return pointer to the array and destroy it immideatly. Imagine someone telling you: "There is candy for you in the living room", then you came and didn't find it. You ask: "Where is it?". He: "Id didn't need it so I trow it out".
I need help that is for sure, the return value should be a pointer to an array that is filled with all the factors from the recursion function. so how do i return the pointer that has the factors in it? Line 18 i thought that would happen i just didn't know where to put the code to delete the dynamic array.
The syntax for using the return value of a function is shown below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
int sum(int a, int b)
{
int theSum = a + b;
return theSum;
}
void myFunc()
{
int i = 1;
int j = 2;
int theSum = 0; // This is the variable that will be used to store the sum
theSum = sum(i, j); // This takes the return value of sum(i, j) and stores it in theSum
std::cout << "The sum is " << theSum << std::endl; // This prints the value of theSum, to show it's the value returned from the function, i.e. 3
}
Edit: As for deleting the array, the calling code will need to delete it after it's finished using it. You can use a smart pointer to make this happen automatically.
@MikeyBoy I appreciate the example, I understand how to do basic return functions, its the part where the recursion function loops to update the array to get all factors and return the pointer back to main. can you show me a recursion function that does that. I don't want you guys to do my homework just show me how it works with an different example a pointer to array and return pointer that has the values needed in the array. if you could put comments in to explain the array part of how it updates and how the base case would work. Thanks appreciate it so much! I want to learn the correct way.
@boomer8809: It's difficult to understand your question. It would be nice if you fix all bugs/problems MiiNiPaa reported above and then repost your code to let us better see your intentions.
Sorry I'm new to recursion and fairly new to pointers, I am trying to obtain all factors through a recursion function of a integer that i have set a value to it but will be randomly generated by the teacher and i will implement an .hpp file where the prototype will be put in. After I have found each factor I need to put it in an array which is global and point that back to main. Right now I am having trouble obtaining all factors of a number. I need to understand how to implement the algorithm with the mod operator. I understand the mod operator with (x % 2 == 0) and (x % 2 ==1) basically even and odd. I will work on the array and pointer after I get the correct factors outputing to the screen. I understand right now for factors I'm getting 12 6 3 1 how do you get 4 and 2?
Regardless of any algorithm you may think about to solve your problem, this code seems to do nothing useful:
1. You've defined an array_of_factors which, I think, should take the computed result. But you never assigned any value!
2. Line 28 seems to be for debugging?
3. The exit() statement in line 32 will terminate your process. Is this really intended here?
4. Your function makes some decisions - but never assigns any results. It ever returns the value 0 respectively terminates the process in some cases.
5. There's no output of any possible result.
To give you some help:
1. Think about a way to solve your problem. A first (and simple) idea may be to repeatedly test your input number against possible divisors. You may generate them by consecutivly increasing a counter. Your test result should finally be written into the result array.
2. Write down your algorithm step by step in natural language. Think about you would try to explain it a friend through a telephone.
3. Translate it into C:
3.1 Decisions you've made here could be translated into conditional statements in C (f.e. if-statement).
3.2 Something like "repeat until...", "as Long as..." or "do something while" may be translated into some C loop statement.
3.3 To test whether a number is divisable by another one you may find the modulus operator useful. F.e. 25 % 5 == 0 means 5 is a factor of 25!
Ok, especially step 4. may not result in some recursive program. But I'm sure, you will get some idea after finding any useful solution.
Thank you tcs I almost got it working! I was talking to a fellow classmate and he told me not to use a for loop for the divisors, which threw me off because that was the only way to increment the divisor counter . I guess I need to write some pseudocode before attempting to code the program. The teacher said something about using extern before unsigned int array_of_factors[100]; what will that do? and how can i check my program with random numbers which my teacher will do to grade my program.
Here is my code. Right now it wont store the the assigned value of x but will find all the other factors.
#include <iostream>
usingnamespace std;
unsignedint array_of_factors[100];
//function prototypes
unsignedint * find_factors_using_recursion (unsignedint );
int main()
{
int n = 15;
unsignedint * p = find_factors_using_recursion(n);
for( int i = 0; i < n ; i++)
{
if(p[i] == 0)
{
p[i];
}
else
{
cout << p[i] << endl;
}
}
return 0;
}
unsignedint * find_factors_using_recursion (unsignedint x )
{
unsignedint * factor = array_of_factors;// Asign a pointer to the array
(*factor = x);
//cout << *factor;
for (unsignedint i = 2; i <= x; i++)// counter for divisors
{
if(x == 0)
{
return NULL;
}
elseif (x % i == 0)// if not the NULL run recursion
{
factor[i] = i;
find_factors_using_recursion(x / i);
}
}
return factor;
}
it has something to do with factor[i] = i; if (i) replace i with (x) i get 15 but wont find the factor 5, vice versa if i have (i) it will find 5 but not 15. Also should I have the if statement for the NULL above the for loop? Thanks appreciate all the input!
1. The output between lines 18 to 28 may produce more or less noise. The array may contain random values. (May be some debugging environment, especially on Microsoft systems, erroneously initialize all elements to 0 so there will be no noise). The way you use your array requires it to be initialized to some useful values first before being used as factors container. F.e. you may initialize all array elements to 0. See more about your array at 5.
2. Even if the output loop between (line 18-28) may work fine it could be done simpler. Why do you write those conditional statement starting at line 20? The statement at line 22 is completely obsolete. It does nothing else than time consuming. Compilers and optimizers may even remove it from code generation.
3. Well done! Returning 0 on success in main() is best practice!
4. Line 40. Why do you surround the assignment with braces? Its not wrong but obsolete.
5. I strongly recommend you to think about your array_of_factors.
5.1. The way you use it only allows factors up to the value of 99. Higher ones will crash the process.
5.2. In this way it's also useless to define the arrays element type as integer. bool would be enough because the array index is identical to a factor.
5.3. Each recursion will start filling your array at position 2 overwriting all results generated in previous levels.
Some hints:
1. Why loop up to the value of `x´ (line 44)? The integral part of sqrt(x) would be enough as upper bound. ("sqrt" is the square root). Think about this.
2. You may want to manage your array in some more well considered way:
Don't use the factor as index. Better use an also globally defined index starting at position 0. Increase it after every assignment. Pay attention on array boundaries!