控制可能到达递归函数中非 void fct 的结尾

Question

我知道这个错误的原因和原因。主要是 bc if 里面的 return。但是我想修复流程，使其 error/warning 免费。

我在末尾添加了无关紧要的 return，并尽我所能修改流程，但没有成功。

int modifiedbinsearch_low(int* arr, int low, int high , int key){   
    if(low==high) return high ; 

    int mid = low + (high-low) /2;

    if(key >  arr[mid] ) { modifiedbinsearch_low(arr,mid + 1 , high,key);  } 
    else  { modifiedbinsearch_low(arr,low,mid,key);  }  
}

int modifiedbinsearch_high(int* arr, int low, int high , int key){   
    if(low==high) return high ; 

    int mid = low + (high-low) /2;

    if(key <  arr[mid] ) { modifiedbinsearch_high(arr,low,mid,key);  } 
    else  { modifiedbinsearch_high(arr,mid+1,high,key);  } 

} 

int low = modifiedbinsearch_low( ...)
int high = modifiedbinsearch_high( ...)

Answer 1

我们遇到这类错误的问题通常是因为函数需要一个 return 值，但实际上是 none。在我的例子中，没有 return 如果第一个 if 逻辑块 失败从而给我错误。

如果使用递归遇到此问题，请在递归函数内部调用自身时将 return 添加到递归函数中。

这里是@drescherjm在评论中给出的解决方案；

int modifiedbinsearch_low(int* arr, int low, int high , int key){   
    if(low==high) return high ; 

    int mid = low + (high-low) /2;

    if(key >  arr[mid] ) { 
          return modifiedbinsearch_low(arr,mid + 1 , high,key);
    }   
    else  { 
          return modifiedbinsearch_low(arr,low,mid,key);  }  
    }

int modifiedbinsearch_high(int* arr, int low, int high , int key){   
    if(low==high) return high ; 

    int mid = low + (high-low) /2;

    if(key <  arr[mid] ) { 
          return modifiedbinsearch_high(arr,low,mid,key);  
    } 
    else  { 
          return modifiedbinsearch_high(arr,mid+1,high,key);  } 
    }

Answer 2

这两个函数return当控制到达if语句时什么都没有

if(key >  arr[mid] ) { modifiedbinsearch_low(arr,mid + 1 , high,key);  } 
else  { modifiedbinsearch_low(arr,low,mid,key);  }

和

if(key <  arr[mid] ) { modifiedbinsearch_high(arr,low,mid,key);  } 
else  { modifiedbinsearch_high(arr,mid+1,high,key);  }

顺便说一句，这两个函数都有多余的参数。例如，按以下方式声明函数 modifiedbinsearch_low 就足够了

int * modifiedbinsearch_low( int* arr, size_t n , int key);

这类似于标准算法 std::lower_bound 和 std::upper_bound 函数应该 return 指针而不是 int 类型的值。

如果像调用函数一样

auto first = modifiedbinsearch_low( arr, n, key );
auto last = modifiedbinsearch_high( arr, n, key );

则 first-last 对确定范围 [first, last)，其中具有值键的元素存储在数组中。

我将按照下面的演示程序所示的方式声明和定义函数

#include <iostream>
#include <iterator>

int main()
{
    int a[] = { 1, 2, 2, 2, 3 };

    auto first = modifiedbinsearch_low( a, std::size( a ), 2 );
    auto last = modifiedbinsearch_high( a, std::size( a ), 2 );

    for (; first != last; ++first)
    {
        std::cout << *first << ' ';
    }
    std::cout << '\n';
}

程序输出为

2 2 2

如果您希望该函数 return 索引而不是指针，那么它们可以按以下方式显示，如下一个演示程序所示。

#include <iostream>
#include <iterator>

size_t modifiedbinsearch_low( const int a[], size_t n, int key )
{
    if (n == 0)
    {
        return n;
    }
    else if (a[n / 2] < key)
    {
        return n / 2 + 1 + modifiedbinsearch_low( a + n / 2 + 1, n - n / 2 - 1, key );
    }
    else
    {
        return modifiedbinsearch_low( a, n / 2, key );
    }
}

size_t modifiedbinsearch_high( const int a[], size_t n, int key )
{
    if (n == 0)
    {
        return n;
    }
    else if (key < a[n / 2])
    {
        return modifiedbinsearch_high( a, n / 2, key );
    }
    else
    {
        return n / 2 + 1 + modifiedbinsearch_high( a + n / 2 + 1, n - n / 2 - 1, key );
    }
}

int main()
{
    int a[] = { 1, 2, 2, 2, 3 };

    auto first = modifiedbinsearch_low( a, std::size( a ), 2 );
    auto last = modifiedbinsearch_high( a, std::size( a ), 2 );

    for (; first != last; ++first)
    {
        std::cout << a[first] << ' ';
    }
    std::cout << '\n';
}

程序输出同上图

2 2 2

如果你的编译器不支持函数 std::size 那么这个表达式 std::size( a ) 你可以重写成 sizeof( a ) / sizeof( *a ).

控制可能到达递归函数中非 void fct 的结尾

Control may reach end of non-void fct in recursive function

c++

algorithm

recursion

return

function-definition