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

How efficient is this code for checking palindrome ??

CodePudding user response：

There is compiler optimization called tailing recursion.

In your quite simple case compiler spotted that there is possibility to use this optimization. As a result it silently turn your code into iterative version:

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

Note:

• there is no call instruction needed in code which actually uses recursion
• label .L8 is responsible for a loop which replaced recursion

Remember there is "As-if rule" so compiler can transom your code in may ways to make it faster.

CodePudding user response：

In general, the recursive solution is often more elegant than iteration, but mostly needs more CPU time and memory space. The CPU has to put data on the stack every recursion.

Especially in this case, iteration seems more efficient in time and memory.

Try somthing like this:

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