Solved

help needed to write this Simple code using recursion

Posted on 2004-09-01
20
2,266 Views
Last Modified: 2008-01-09
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
0
Comment
Question by:deepthiji
  • 8
  • 4
  • 3
  • +3
20 Comments
 
LVL 11

Expert Comment

by:avizit
ID: 11958858
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
 
LVL 11

Expert Comment

by:avizit
ID: 11958923
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
 
LVL 11

Expert Comment

by:avizit
ID: 11958986
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
 
LVL 11

Expert Comment

by:avizit
ID: 11959056
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
 
LVL 9

Assisted Solution

by:ankuratvb
ankuratvb earned 50 total points
ID: 11960098
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
 
LVL 9

Expert Comment

by:ankuratvb
ID: 11960146
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
 
LVL 45

Expert Comment

by:sunnycoder
ID: 11960688
>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
 
LVL 11

Expert Comment

by:avizit
ID: 11960726
>>> >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
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 100 total points
ID: 11960740
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
 
LVL 3

Author Comment

by:deepthiji
ID: 11974500
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 9

Expert Comment

by:jhshukla
ID: 11975162
recursive expr:

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

Assisted Solution

by:jhshukla
jhshukla earned 100 total points
ID: 11975203
@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
 
LVL 11

Expert Comment

by:avizit
ID: 11975308
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
 
LVL 9

Expert Comment

by:jhshukla
ID: 11975996
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
 

Assisted Solution

by:lebuihung
lebuihung earned 100 total points
ID: 11983679
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
 
LVL 3

Author Comment

by:deepthiji
ID: 11984258
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
 
LVL 11

Expert Comment

by:avizit
ID: 11984341
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
 
LVL 3

Author Comment

by:deepthiji
ID: 11984356
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
 
LVL 11

Accepted Solution

by:
avizit earned 150 total points
ID: 11984387
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
 
LVL 3

Author Comment

by:deepthiji
ID: 11984909
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

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now