C program using recursion need to get optimised and fixed

Question

I was solving a task that was - a user is entering 3 numbers, a, b, c. The goal is to find if you can get to c summing a and b. In each step is allowed to add a to b, and b to a. I need to find if that is possible with the entered numbers. The entered numbers are in the range between 0 and 10^18. Below is my code, done with recursion.

Example of solving the task for a=4 b=6 c=38:

1. a=4 b=10
2. a=14 b=10
3. a=14 b=24
4. a=38 b=24 print YES

My code below does its job well for low numbers but I think I'm loosing the battle with the bigger numbers... I added few comments to what part is doing what.

What I need help is, I need it to work better, and faster, and I don't know how to optimise it more.

//the function that I'm using
int task(long long int a, long long int b, long long int c, long long int d, int p) 
{ //a, b and c are long long integers that are submited by the user, d is the sum of
  //the unchanged a and b, and p is a flag
    if(!a && !b && c) return 0; //0+0 will never get to 1
    if(c==d) return 1; //if I get with c to d, it is confirmed yes, 
                       //did the math with a pen :)
    if(c<d || c<=0) // I thought this is a nice case to stop
    {
        return 0;
    }
    if(p==1)
    {
        if(a>c) return 0; //if the flag p is one, that means i changed a, 
                          //so compare a
    }
    if(p==2)
    {
        if(b>c) return 0; //if p is two, i changed b so compare b
    }
    if(c-d>0) return task(a+b, b, c-b, d, 1)||task(a, b+a, c-a, d, 2);  
            //recursion call with OR operator so every step is checked

}//one part is a=a+b b=b c=c-b, i decrement c so fewer steps are needed, 
 //the other part is when i add a to b

int main()
{
    long long int a,b,c;
    scanf("%I64d%I64d%I64d",&a,&b,&c); //scaning
    int p; //the flag for the first numbers
    if(a>b) p=1; //i dont know if i need this step at all xD
    else p=2; //but to make sure
    if((a==1 || b==1) && c) printf("YES"); //a=1 b=1 and c>=1 means i can get to c,
                                           //even with a+b+b+b..
    else if(a==c || b==c) printf("YES"); //if one of the numbers are already same 
                                         //with c, no need to check
    else if(task(a,b,c,a+b,p)) printf("YES"); //if the function returns 1, print YES
    else printf("NO"); //or print NO


    return 0;
}

Answer 1

Perhaps I am not understanding the problem correctly, but here are two different iterative approaches. Maybe this could help you along:

#include <stdio.h>

int old_task( long a, long b, long c )
{
   size_t iteration;
   long left = a, right = b;
   for( iteration = 0; ( left < c ) && ( right < c ); ++iteration )
   {
      printf( "NOT %ld: %ld, %ld < %ld\n", iteration, left, right, c );
      if( iteration % 2 )
         left += right;
      else
         right += left;
   }
   printf( "STOP %ld: %ld, %ld < %ld\n", iteration, left, right, c );
   return ( ( left == c ) || ( right == c ) ) ? 1 : 0;
}

int task( long a, long b, long c )
{
    long f;
    /*long i = 0;*/
    for( f = a; f < c; f+= a )
    {
        /*printf( "Checking: %li * %li + %li * %li == %li\n", a, ++i, b, ( c - f ) / b, c );*/
        if( ( c - f ) % b == 0 )
            return 1;
    }
    return 0;
}

int main()
{
   long a,b,c;
   scanf("%ld %ld %ld",&a,&b,&c); //scaning

   printf( "%s\n\n", task( a, b, c ) ? "YES" : "NO" );
   return 0;
}

Answer 2

I think it can be solved with linear algebra. Let's say you've got a = 3, b = 4 and c = 15. So what you're looking for is

3x + 4y = 15
x = (15-4y) / 3

So if you divide it with 3 it should have no remainder. And I think here comes linear algebra, because 15-4y should be 0 modulo 3.

It's just an idea.

Answer 3

My code below does its job well for low numbers

It doesn't. Try input 2 2 3. The most obvious error is:

In function 'main':
 warning: format '%I64d' expects type 'int *', but argument 2 has type 'long long int *'
 warning: format '%I64d' expects type 'int *', but argument 3 has type 'long long int *'
 warning: format '%I64d' expects type 'int *', but argument 4 has type 'long long int *'

To correct it, replace %I64d with %Ld.

but I think I'm loosing the battle with the bigger numbers...

Of course your recursive solution can make the stack overflow; for a program that demands less stack space, see this answer.