递归二分查找函数

Question

int binarySearch(int a[], int low, int high, int x) 
{ 
    if (high >= low) { 
        int mid = low + (high - low) / 2; 
  
        if (a[mid] == x) 
            return mid; 
  
        if (a[mid] > x) 
            return binarySearch(a, low, mid - 1, x); 
  
        return binarySearch(a, mid + 1, high, x); 
    } 

    return -1; 
}

上面的二分搜索算法是尾递归的吗？为什么？如果没有，那为什么不呢？

Answer 1

答案是是，它是尾递归。除了立即直接返回这些结果外，它不会对其每次递归调用的结果执行任何操作。

这意味着您可以将其替换为一个循环，该循环将在循环时更新 low 和 high 变量，直到满足停止条件。 a 和 x 变量现在保持不变，因此它们在基于循环的版本中也不会更改。

Answer 2

一般来说，答案取决于尾递归的含义。您的意思是 formal definition 还是“我的编译器会在没有递归 call 的情况下实现它”？编译器可能会识别在技术上不是递归的递归模式，并且仍然将它们滚动到循环中。

在你的情况下，仅通过 looking at the assembly 就很容易检查，这确实表明不存在 call 并且递归已变成许多跳转。

binarySearch(int*, int, int, int):
.L9:
        cmp     esi, edx
        jg      .L7
.L2:
        mov     eax, edx
        sub     eax, esi
        sar     eax
        add     eax, esi
        movsx   r8, eax
        cmp     DWORD PTR [rdi+r8*4], ecx
        je      .L1
        jle     .L4
        lea     edx, [rax-1]
        cmp     edx, esi
        jge     .L2
.L7:
        mov     eax, -1
.L1:
        ret
.L4:
        lea     esi, [rax+1]
        jmp     .L9

递归二分查找函数

Recursive Binary Search Function

c++

recursion

tail-recursion

function

binary-search