本文共 1417 字，大约阅读时间需要 4 分钟。

一、递归实现的效率

如果不能采用很好的方法，递归实现相较于用迭代实现相同功能的效率更差，计算机可能会多次进行冗余的计算调用。所以需要观察能否用更巧妙的方式构造递归函数，此处待补充方法。

二、检测回文

检查一个字符串是否是一个回文可以采用如下方法：

1. 检查其首字符和最后一个字符是否相同
2. 检查删除首字符和最后一个字符之后产生的字串是否是一个回文

若满足则是回文

低效函数版本：

bool isPalindrome(string str) {
   	int len = str.length();	if (len <= 1) {
   		return true;	}	else {
   		return str[0] == str[len - 1] && isPalindrome(str.substr(1, len - 2));	}}

通过 1.只计算参数的长度一次 2.不在每次调用中都生成一个字串 这两方面改进得到优化版函数：

bool isPalindrome(string str) {
   	return isSubstringPalindrom(str, 0, str.length() - 1);		//包装器函数}bool isSubstringPalindrom(string str, int p1, int p2) {
   	if (p1 >= p2) {
   		return true;	}	else {
   		return str[p1] == str[p2] && isSubstringPalindrom(str, p1 + 1, p2 - 1);	}}

三、二分查找算法

直接给出算法代码：

int findInsortedVector(string key, vector
   
    & vec) {
   		//包装器函数	return binarySearch(key, vec, 0, vec.size() - 1);}int binarySearch(string key, vector
    
     & vec, int p1, int p2) {
   	if (p1 > p2) return -1;	int mid = (p1 + p2) / 2;	if (key == vec[mid]) return mid;	if (key < vec[mid]) {
   		return binarySearch(key, vec, p1, mid - 1);	}	else {
   		return binarySearch(key, vec, mid + 1, p2);	}}
    
   

四、间接递归

例如一个函数F调用了另一个函数G，反过来函数G调用函数F，F与G彼此相互调用，这种类型的递归称为间接递归。

bool isOdd(unsigned int n) {
   	return !isEven(n);}bool isEven(unsigned int n) {
   	if (0 == n) {
   		return false;	}	else {
   		return isOdd(n - 1);	}}

五、总结

如果简单情况能工作，并且递归分解是正确的，那么子调用会正常工作。否则，问题一定出在递归分解公式中。

转载地址：https://blog.csdn.net/m0_45689014/article/details/113405208 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！