c - 为什么我的递归函数的输出是错误的？

Question

该函数需要仅使用 (1+) 或 (2*) 返回从数字 x 到数字 y 的最小传递次数。例如，从8到19，最小pass是“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

这里有两个问题。

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;
  }
}