C语言递归回文判断的终止机制与短路求值问题解析

问题背景 #

我在学习递归原理时，使用了如下一段判断字符串是否为回文的C语言代码：

#include <stdio.h>
#include <string.h>
#define SIZE 80

bool palindrome( const char * const sPtr ); // 函数声明
bool palindromeKernel(const char * const sPtr, size_t l, size_t r);

int main( void ) {
   char sentence[ SIZE ]; 
   puts( "Enter a line of text:" );

   fgets( sentence, SIZE, stdin );

   puts( "\nIs the line palindrome?" );

   if ( palindrome( sentence )) printf("yes");
   else printf("no");
   putchar('\n');
} 

bool palindrome( const char * const sPtr ){
   size_t len = strlen(sPtr);
   return(palindromeKernel(sPtr, 0, len-2)); 
}

bool palindromeKernel(const char * const sPtr, size_t l, size_t r){
   puts("1");
   if (l >= r) return true;
   return ((sPtr[l] == sPtr[r]) && palindromeKernel(sPtr, l+1, r-1));
}

我在palindromeKernel函数中添加了puts("1")语句追踪函数调用时机：

• 输入标准回文字符串mrowlatemymetalworm时，运行结果符合预期，函数共调用10次，最终输出yes：

Enter a line of text:
mrowlatemymetalworm

Is the line palindrome?
1
1
1
1
1
1
1
1
1
1
yes

• 但输入修改了第二个字符的非回文字符串mtowlatemymetalworm时，函数仅被调用2次就返回了no，递归在返回false时直接停止了自调用，不清楚该现象的成因：

Enter a line of text:
mtowlatemymetalworm

Is the line palindrome?
1
1
no

补充疑问 #

如果将palindromeKernel最后返回语句中&&两侧的表达式顺序调换，写成如下形式：

return (palindromeKernel(sPtr, l+1, r-1) && (sPtr[l]==sPtr[r]));

程序依然可以输出正确结果，无法理解该条件判断内部递归函数的运行逻辑。

问题解答 #

1. 为什么非回文场景下递归仅调用2次就停止 #

这是C语言中逻辑与运算符&&的短路求值特性导致的：

• 对表达式A && B，程序会先计算左侧A的值，如果A的结果为false，整个与表达式的结果已经确定为false，程序不会再计算右侧B的内容。
• 原代码中返回语句先判断当前左右指针对应的字符是否相等：第一次进入palindromeKernel时l=0、r指向字符串最后一个有效字符（len-2是为了跳过fgets读入的末尾换行符），两个位置的字符都是m，相等，因此左侧表达式为true，程序才会执行右侧的递归调用，进入l=1、r=r-1的第二层调用。
• 第二层调用中，修改后的第二个字符为t，和对称位置的字符不相等，此时左侧sPtr[l] == sPtr[r]结果为false，右侧的递归调用根本不会被执行，函数直接返回false，沿着调用链一路传回主函数，因此只会打印2次1就结束运行。

2. 为什么调换&&两侧表达式顺序后程序依然能正常运行 #

核心原因有两个：

• 逻辑与运算满足交换律：命题「当前左右字符相等 且 内层子串是回文」和命题「内层子串是回文 且 当前左右字符相等」的真假值完全等价——两个条件必须同时满足，整个字符串才是回文；只要任意一个条件不满足，结果就为false，因此最终判断结果不会出错。
• 调换顺序后只是改变了短路触发的时机，不会改变最终布尔结果：调换顺序后程序会先递归调用内层判断，一直走到l >= r的基线条件（此时单个字符/空串必然是回文，返回true），再往回逐层判断当前层的左右字符是否相等。如果某层字符不相等，同样会触发短路，直接返回false。
  这种写法和原写法的唯一区别是递归调用次数不同：比如输入的第二个字符错误的非回文串，调换顺序后会递归到最内层才开始判断字符相等性，会打印10次1才返回no，但最终判断结果和原写法完全一致。

内容的提问来源于stack exchange，提问作者france883