Почему мой вывод неверен в этой рекурсивной функции?

Question

Функция должна возвращать минимальный проход из числа x в число y, используя только (1+) или (2 *).например, с 8 до 19 минимальный проход равен «3», потому что (8 * 2 + 1 + 1 + 1 = 19), теперь мой код выводит другое число вместо 3, в чем моя проблема?

#include <stdio.h>
int f(int x, int y){

  if(x==y) 
    return 0;
  if(x>y)
    return -1;
  if(2*x < y){
    int max=f(2*x, y);
    return max+1;
  }
  else if(x+1<y){
    int max=f(x+1,y);
    return max+1;
  }
}

int main()
  {
    int idx=f(8,19);
    printf("%d", idx);

    return 0;
  }

Answer 1

В этом случае вы должны подумать, как ваша функция будет работать со своими переменными.Когда он получит последнюю итерацию:

...
else if( x+1 < y ) {
    int max = f( x+1, y );
    return x+1;
}
...

Киран здесь прав.С x = 8 и y = 19 (как вы упомянули выше) вы вспомните функцию с x = 18, которая будет возвращать неопределенное значение, потому что никто из ваших if не будет сопоставлен.

Возможное решение может быть:

int f( int x, int y ) {

    if( x < y ) {

        if( x * 2 < y ) return f( x * 2, y );
        else if( x + 1 <= y ) return 1 + f( x + 1, y );

    } else if( x == y ) return 0;
    else return -1;

}

Answer 2

Здесь две проблемы.

1.Когда x становится на 1 меньше, чем y, то условие if будет выполнено, и вы не вернете ничего, что является неопределенным поведением.

Следовательно, замените

else if(x+1<y){

с

else {

2.Вы не должны добавлять 1+max в случае if(2*x < y), чтобы получить правильный результат, так как вы хотите считать только число +1 выполнено.

, следовательно, измените

int max=f(2*x, y); return max+1;

К

int max=f(2*x, y); return max;

После добавления весь ваш код становится.

int f(int x, int y){

  if(x==y)
    return 0;
  if(x>y)
    return -1;
  if(2*x < y){
    int max=f(2*x, y);
    return max;
  }
  else {
    int max=f(x+1,y);
    return max+1;
  }
}