Thread: Help with Recursion.

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    Help with Recursion.

    I am not sure I fully understand recursion. I understand that you need a base case that will terminate the code and that recursive call needs to get simpler. I am trying to write a recursive function that will determine whether an inputted number is prime or not. I keep getting a stack overflow error when I input a number. I beleive a stack overflow means that the base condition is never checked or something. If you can look at my code and give me advise on what I am doing wrong I would greatly appreciate it. At this point I am not conscerned with program efficiency so much. I am just starting out. Thanks again.

    Code:
    bool checkprime(int nv) {
    	
    	int k =2;
    	if(nv ==2 || k>nv/2) //Base Case ???
    		return true;
    	
    	if(nv%k ==0)
    		return false;
    	else{
    		k++;
    	     return checkprime(nv); //Recursive call
    	}
    
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > return checkprime(nv); //Recursive call
    Well, you missed your own observation - making the answer simpler.
    This is exactly the same as what was input, so obviously nothing happens except consumption of stack space.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Code:
    bool checkprime(int kv,int nv) {
    
    	if(nv ==2 || kv<=2)
    		return true;
    	
    	if(nv%kv ==0)
    		return false;
    	else
    		return checkprime(kv--,nv);
    	
    
    }
    I changed it so that the functions has two arguements. I still get the stack flow. I am making it simpler by reducing kv by one each recursive call. In main, i set k = n/2, where n is the number to be checked and called the function as follows checkprime(k,n). Why is it that even though the function parameter changed it still does nothing? Afterall n has to remain constant because thats the number being checked. K which represents the divisors has to be dynamic, it must change to determine primality. Any help appreicated.
    Last edited by blindman858; 05-07-2005 at 01:52 PM.

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    >>return checkprime(kv--,nv);<<

    Try "return checkprime(--kv,nv);"

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Quote Originally Posted by PJYelton
    >>return checkprime(kv--,nv);<<

    Try "return checkprime(--kv,nv);"
    omg lol now it works. So i am guessing it kv-- assigns kv first and then decrement where as --kv decrements then assigns?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How about using kv-1 and stop trying to outsmart yourself
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Quote Originally Posted by Salem
    How about using kv-1 and stop trying to outsmart yourself
    WTF is ur problem man. I am trying to learn. If you dont want to help newbies then dont bother responding. Go satisfy your ego somewhere else instead of trying to hinder someone elses growth.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Sod the insults, I couldn't give a rats ass whether you listen or not.
    You fell down the same hole twice in a row - there's nothing else to add.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    oh i am sorry i am not as smart as you. I shall pray to god that I become only a fraction as smart as you oh intelligent one. Please show mercy on this retarded insignificant mortal. I took your advise the first time and fixed that aspect of the code. The second time around was a matter of understanding syntax.
    Last edited by blindman858; 05-07-2005 at 03:22 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM