通过递归c++检查回文

Question

bool palindrome(char arr[],int size){
    if(size<=1){
        return true;
    }
    if(*(arr)==*(arr+size-1)){
        bool small_ans=palindrome(arr+1,size-2);
        return small_ans;
    }
    return false;
}

这个检查回文的代码有多高效?？

Answer 1

有编译器优化称为尾尾递归。

在您非常简单的案例中，编译器发现有可能使用此优化。因此，它悄悄地将代码转换为迭代版本：

https://godbolt.org/z/rsjaYhde6

palindrome(char*, int):
        cmp     esi, 1
        jle     .L4
        movsx   rax, esi
        sub     esi, 2
        shr     esi
        lea     rax, [rdi-1+rax]
        lea     edx, [rsi+1]
        add     rdx, rdi
        jmp     .L3
.L8:
        add     rdi, 1
        sub     rax, 1
        cmp     rdi, rdx
        je      .L4
.L3:
        movzx   ecx, BYTE PTR [rax]
        cmp     BYTE PTR [rdi], cl
        je      .L8
        xor     eax, eax
        ret
.L4:
        mov     eax, 1
        ret

注意：

• 实际上使用递归的代码中不需要call指令。
• 标签.L8负责替换递归的循环。

请记住，有"以此类推“，这样编译器就可以以更快的方式通过您的代码。

Answer 2

通常，递归解决方案通常比迭代更优雅，但通常需要更多的CPU时间和内存空间。CPU必须将数据放到堆栈上，每次递归。

特别是在这种情况下，迭代在时间和内存方面似乎更有效。

试着做这样的事：

bool palindrome(char arr[], int size)
{
    for (int i = 0; i < size; ++i) {
        if (arr[i] != arr[size-1-i])
            return false;
    }
    return true;
}