# Thread: problem in recursion function

1. ## 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. 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

3. 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.

4. I think you have the wrong stopping condition.

Code:
`if(n>1)`
Tim S.

5. 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

6. 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

7. 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. @ 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. So it would seem you are exceeding the time limit allowed by Ideone.com.

10. Why would it be a recursive function? You're not calling the function inside the function..

11. Yes he does, look at line 10-12 (post #8).

12. Ye just noticed it, never mind.

13. Originally Posted by stahta01
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.