C++ 递归简介

参考链接： C++递归

一、递归实现的效率 

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

二、检测回文 

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

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

若满足则是回文 

低效函数版本： 

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<string>& vec) {        //包装器函数

    return binarySearch(key, vec, 0, vec.size() - 1);

}

int binarySearch(string key, vector<string>& 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);

    }

}

五、总结 

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