Like Tree1Likes
  • 1 Post By rogster001

problem in recursion function

This is a discussion on problem in recursion function within the C Programming forums, part of the General Programming Boards category; Sphere Online Judge (SPOJ) - Problem COINS i have used recursive function to solve problem given in above link. but ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    4

    Arrow problem in recursion function

    Sphere Online Judge (SPOJ) - Problem COINS

    i have used recursive function to solve problem given in above link.
    but i am getting runtime error.
    plz.. tell me what is the problem.



    Code:
    long long int calc(long long int n)
    {
         long long int x,y,z,sum;
         
         if(n>1)
         {
         x=calc(n/2);
         y=calc(n/3);
         z=calc(n/4);
         sum =x+y+z;
         if(sum<n) 
         {
                   sum=n;          
         }    
         
         return sum;
         }
         
         else
         {
             return n;    
         }
         
    }

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    dont you think it would help to say what the runtime error is? there is more than one variety you know? And hey it might just give a clue as to what is wrong, before looking at the code, because, whaddya know.. its an error message, a message about an error
    stahta01 likes this.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  3. #3
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    Also fix up your indentation, just needs a bit more formatting,

    And get a haircut - just joking. :->

    i dont know why you have put ' return false; '
    in your function, it does not return a bool so for consistency i would have it return the equivalent value.

    Also for the sake of developing good habits and avoiding much future annoyance, zero your vars.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    2,765
    I think you have the wrong stopping condition.

    Code:
    if(n>1)
    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  5. #5
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,438
    thats almost certainly going to be it, overflows or somesuch innit, thing is does the user have a debugger? step step step = self-fixed for this one
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  6. #6
    Registered User
    Join Date
    Sep 2011
    Posts
    4
    12
    2
    50
    10000
    10000000
    100000000
    1000000000

    i have run above test cases. All the test cases are running fine except the last 2, showing time limit exceeded and signal(SIGXCPU). If I change the datatype to long int then second last test case is showing output. i can't find the logic behind this.

    i can't understand why it is showing error for a particular case when it falls within the range of long long int.

    i am using gcc-4.3.4 compiler
    Last edited by nitin28; 01-27-2012 at 04:44 AM.

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Where are you running the program? I tried the above and it worked here (took 1m 46s on this lowly c2d), but reading the link on SIGXCPU it seems it's an artificial limit set by the system.

  8. #8
    Registered User
    Join Date
    Sep 2011
    Posts
    4
    @ Subsonics

    I am running it on Ideone.com

    complete code:

    Code:
    #include<stdio.h>
    
    long long int calc(long long int n)
    {
         long long int x,y,z,sum;
         x=y=z=sum=0;
         
         if(n>1)
         {
         x=calc(n/2);
         y=calc(n/3);
         z=calc(n/4);
         sum =x+y+z;
         if(sum<n) 
         {
                   sum=n;          
         }    
         
         return sum;
         }
         
         else
         {
             return n;    
         }
         
    } 
    
    
    int main()
    {
    long long int sum,n;
    
    while(scanf("%lld",&n)!=EOF)
    {
             
                    
                    
                    sum=calc(n);
                    
                    printf("\n%lld",sum);
    }
    
    return 0;    
    }

  9. #9
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    So it would seem you are exceeding the time limit allowed by Ideone.com.

  10. #10
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    Why would it be a recursive function? You're not calling the function inside the function..

  11. #11
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Yes he does, look at line 10-12 (post #8).

  12. #12
    Registered User
    Join Date
    Jan 2012
    Posts
    69
    Ye just noticed it, never mind.

  13. #13
    Registered User
    Join Date
    May 2009
    Posts
    2,765
    Quote Originally Posted by stahta01 View Post
    I think you have the wrong stopping condition.

    Code:
    if(n>1)
    Tim S.
    FYI: If you change "1" to just below where the results change your code will run faster. The results change at 12; but, I have no idea if a smaller value also change. If 12 is the first value to change try using "11" instead of "1".

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function problem (recursion)
    By chaklader in forum C Programming
    Replies: 4
    Last Post: 05-28-2010, 12:48 AM
  2. Recursion Function Problem
    By nicz888 in forum C++ Programming
    Replies: 7
    Last Post: 11-28-2007, 09:48 AM
  3. help with recursion function
    By robasc in forum C++ Programming
    Replies: 12
    Last Post: 12-10-2006, 05:24 PM
  4. Function Recursion
    By iSlak in forum C++ Programming
    Replies: 4
    Last Post: 08-21-2005, 05:08 PM
  5. recursion function
    By jdr30 in forum C++ Programming
    Replies: 7
    Last Post: 06-05-2003, 11:58 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21