• C

# help needed to write this Simple code using recursion

hi experts,

i wrote the below code.. its for getting prime factors of any number. Now i wanted to write the same program using recursion..
Could any one direct me how to write this using recursion. Please dont write the code, just give me directions to write it..
thanks in advance for the help
Also when i send a code before in EE ,,one expert told me i have to right "int main" instead of "void main". Could anyone tell me what is the correct syntax, i think i have to return a value if i write "int main",, right? but i am not returnning any value, so what should i do?

Also one expert told me always increse the count of loop rather than decreasing.. In the below code i decreased the count here..
//flag=1;
for(j=i-1;j>1;j--)  //
is there any way i increase the count (instead of j-- can i use j++ by changing something here)
I am a novice and please explain things in a simple way

#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,n,k,h,flag;
clrscr();
printf ("Enter the number");
scanf ("%d",&n);
for(i=2;i<=n;i++)
{
flag=1;
for(j=i-1;j>1;j--)
{
k=i%j;
if(k==0)
{
flag=0;
break;
}
}
if(flag==1)
{
while(n!=0)
{
h=n%i;
if(h==0)
{
n=n/i;
printf ("\n%d,",i);
}
else
break;
}
}
}
getch();
}

thans.
deep
LVL 3
Asked:
###### Who is Participating?

Commented:
recursion  good to understand the program in cases where the algorithm is very lucidly explained in recursion that in iteration

for example a recursive program for Fibonacci numbers  is

simply

int fib( int n ) {
if ( n < 2 ) return n;
else
return fib(n-1) + fib(n-2);
}

while for iterative its

int fib( int n ) {
int k, f1, f2;
if ( n < 2 ) return n;
else {
f1 = f2 = 1;
for(k=2;k<n;k++) {
f = f1 + f2;
f2 = f1;
f1 = f;
}
return f;
}

you can easily see that the iterative one is smewhat harder to understand ..

BUt if you are programming for a low memory machine .. the recursive method will have many function calls especially for biger numbers and hence will fill up the stack very fast

but the iterative one doesnt have any function calls

0

Commented:
1) from http://www.delorie.com/djgpp/v2faq/faq22_25.html
Q: Why does everybody tell me that void main is bad?

Q: If void main is incorrect, how come the compiler lets it compile?

A: The ANSI/ISO C Standard specifies that the main function be declared in one of the following two ways:

int main (void);

or

int main (int argc, char **argv);

In both cases the return type is an int, and your main function should therefore either return an int or call the library function exit, when the program ends. The C++ standard includes a similar requirements for C++ programs.

Since the runtime environment assumes that main returns an int, declaring main with any other return type, including void, invites trouble. The compiler might compile such a program, since the ANSI Standard doesn't require it to fail, but the behavior of such a program is, in the Standard's parlance, "undefined" (read: anything can happen). That is why GCC will print a warning in these cases if you use the -Wall switch.

To summarize, using void main is unsafe and can potentially do evil things to your program. It is best to avoid it.

Note that the C++ standard, in contrast to the C standard, explicitly prohibits void main(), and explicitly says that if the controls reaches the end of main without encountering a return statement, the effect is that of executing return 0;. When compiling a C++ program, GCC automatically generates the code to return zero from the main function, in case the programmer leaves that out.

--------------------
of you are not returning a value , you can simply return 0 and discard the return value. BUt it is customary to return 0 to denote successand return a non-zero value to denote failure

0

Commented:
hmm to use recursion

you have to write a function find_factor (unsigned a )

which  can call itself

the working is like this

it find a factor and then calls itself with the factors it found to find further factors of itself , for a prime number the function has to stop

it should be something like this

say you call the function with input 30

so it should call like this

find_factor(30)

in the function you find that its divisible by 2 .. so you have the factor 2 and 15 , so now you call the same function again with 2 and 15

find_factor(2)   which should return back 2 since its a prime and further factorization is not possible   (1)

find_factor(15)
should now find that its 3 X 5
so now should call

find_factor(3) -> which should return back 3  (2)
and
find_factor(5) -> which should return back 5  (3)

so yuo have the 3 factors 2, 3, 5.

0

Commented:
and btw in your program in the for loop

for(i=2;i<=n;i++)

you reallly need to do only till  i < = int(sqrt(n))

so you can just have

int k;
k = (int) sqrt(n);

for(i=2;i<=k;i++)

cos for values k > sqrt(n)    , the n/k  is less than k and hence must have already been found if k is a factor

for example

for 100

you need do that only till 10 cos  say for 20 , you have 100/20 = 5 , but 5 must have alreday been found when you had i = 5
0

Commented:
In recursive functions its important that your function has a stopping criteria. else your function might keep calling itself forever.

for us the stopping criteria occurs when the input is a prime in that case we stop and dont make any further calls to itself.
0

Commented:
As for the void main(),see:
http://www.eskimo.com/~scs/C-faq/q11.12.html

main() returns the value to the calling environment which usually is the OS.
Now,if you're working in dos,it discards the return value,but for OS's like linux,a return value of 0 indicates successful execution and non-zero a failed execution.
0

Commented:
For doing the factoring using recursion:
See:
http://www.dcs.ed.ac.uk/home/stg/pub/R/recursion.html

It outlines the steps required.
0

Commented:
>Also one expert told me always increse the count of loop rather than decreasing
Its the same either way ... As long as logic is correct, it does not matter

>one expert told me i have to right "int main" instead of "void main
Very well answered above

>Could any one direct me how to write this using recursion. Please dont write the code, just give me directions to write it..
Think what you require for a recursive solution
1. A base case where the function value is defined and further calls are not required.
2. Some criteria to recurse, such that each recursion level takes you closer to base criteria

Your target is to find all prime factors os a number.

Think what will be the base case, i.e. when will you require no further processing?

A little thinking will reveal that is the number you are trying to factorize is itself prime, then you do not have to do anything at all. The number and integer 1 are the factors that you are looking for.

Now let us look for processing to do and recursion criteria. What should you do to a number such that you are able to derive prime factors and get closer to a prime number residue?

If a number "k" has n prime factors, if you find one prime factor "j" and repeat the process for "k/j" then you will have only n-1 more prime factors to find. In other words, find one prime factor for the number and then recurse with remaining quotient.

cheers
sunnycoder
0

Commented:
>>> >Also one expert told me always increse the count of loop rather than decreasing
>>>Its the same either way ... As long as logic is correct, it does not matter

True , but I find loops which count up easier to understand or say even more readable.. But guess its just a matter of personal taste.
anyway it was not I who had suggested the idea to deepthiji in the first place :)

0

Commented:
Abhijit,
I never intended to blame you or anyone else ... Apologies if I sounded that way ... :)

I agree that it is more of personal style or taste than anything else
0

Author Commented:
sorry for the delay guys,, was really busy preparing my thesis.. have to defend it this month>)
I am still trying to do the above using recursion(i did couple of simple programs using recursion)..its been two hours now.. I will get back after some time..
thanks for all
0

Commented:
recursive expr:

PrimeFactors(number) = PrimeFactor(Factor1) x PrimeFactor(Factor2);
0

Commented:
@avizit
did you mean this:
number = 30
find_factor(number) -> 2
number /= 2
find_factor(number) -> 3
number /= 3
find_factor(number) -> 5
number /= 5
number is 1. STOP!

0

Commented:
jshukla i meant this

number = 30

factor(30)

( (int)sqrt(30) = 5 , so you need to check for primes only upto 5 )

start from 2 ,

2 is a factor . so call the function recursively with 2 and 30/2

factor(2) and factor(15)

factor(2) prints 2 and returns.

factor(15)
calls factor(3) and factor(15/3)
both of which immediately returns after printing 3 and 5 respectively

0

Commented:
well you could do the sqrt check in find_factor and

the function should only test odd numbers (except 2), like so:
do somthing for i=2
...
for(i=3;i<=k;i +=2)
0

Commented:
Explaination: basically, the idiea is same as urs
1. find prime number ( from 2-> our number)
2. check to c it is a factor of our number
3. if yes, call recursive function to continue our work from ( our number ) / factor only.
if no, keep going as usual.

Hope it will help.

/******* code *************/

#include<stdio.h>

void printFactor(int);
int isPrime(int);

int main()
{
int i,j,n,k,h,flag;

printf ("Enter the number");
scanf ("%d",&n);

printFactor(n);

return 1;
}

int isPrime(int number)
{
int i;
for(i=2;i<number;i++)
{
if(number%i==0)
return 0;
}
return 1;
}

void printFactor(int number)
{
int i;
for(i=number;i>=2;i--)
{
if(isPrime(i)==1) /* it is a prime */
{
int h=number%i;
if(h==0)
{
printf ("\n%d,",i);
printFactor(number/i); /* recursivefunction */
return ; /* get out of function */
}
}

}

}

0

Author Commented:
thnanks a lot guys,, I was trying to write this code and i couldnt suceed, offcourse i did not spend much time on it since i had to do some urgent work(thesis as i mentioned earlier)..

I just started learnning C and i would like to know how hard  the above code is when compared to the real life programs...I havent learn pointers(i know just the basics of pointers) and arrays yet,, these are the difficult part in C i guess... i just wanted to know how hard the above program is if you rate that in a scale of 1- 10.....
I wanted to rate myself becuase i had hard time with the above program,, i just wanted to check am i a Dumb Ass>) or not....
i am learnning this stuff NOT to get an IT job,my field is mechanical.... my aim is to become a Hacker(pls dont laugh)....
since you all helped me i will split the points.
thans

0

Commented:
okay since you are just learning C , i guess i will just put a few reasons why you should avoid recursion vis a vis iterative method

1. recusrion results in a function call and hence your stack grows quite fast and hence you can easily have a stack overflow.

2. aborting a recursive procedure is painful . ..you have to gro thorugh all the levels of recursion you already had

3. lots of fucntion call overhead .. which arent present in a iterative method

having said that sometimes recursion is nice too

1. some algororithms are very easy to express in a recursive way.

there are many other pros and const of recursion .. i just named what came to me just now.
0

Author Commented:
hii avizit,,,
i am learnning C by myself and the book which i follow says that use recursion as much as possible, so i thought using recursion everywhere is good(everywhere=where loops needed), i was even trying to rewrite all my programs using recursion which i wrote before using loops...
so are you saying its not s good programming practice..?
0

Author Commented:
oooooohh,
avizit, you know what, after this above program i was going to try fibonacci seriers using recursion,,,you already wrote the code for that lol
anyways its ok., thanks for the code..
thanks for the comments tooo
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Already a member? Login.

All Courses

From novice to tech pro — start learning today.