C++ 递归简介
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++ 递归简介,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1674字,纯文字阅读大概需要3分钟。
内容图文
一、递归实现的效率
如果不能采用很好的方法,递归实现相较于用迭代实现相同功能的效率更差,计算机可能会多次进行冗余的计算调用。所以需要观察能否用更巧妙的方式构造递归函数,此处待补充方法。
二、检测回文
检查一个字符串是否是一个回文可以采用如下方法:
- 检查其首字符和最后一个字符是否相同
- 检查删除首字符和最后一个字符之后产生的字串是否是一个回文
若满足则是回文
低效函数版本:
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);
}
}
五、总结
如果简单情况能工作,并且递归分解是正确的,那么子调用会正常工作。否则,问题一定出在递归分解公式中。
内容总结
以上是互联网集市为您收集整理的C++ 递归简介全部内容,希望文章能够帮你解决C++ 递归简介所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。