数据结构——递归

c++版（清华邓俊辉版） 整理书本习题，啊啊啊，习题集还没到，就只能做书上的题。 loving to learn, loving to share.

1.什么是递归算法

递归算法就是直接或间接调用自身。递归细分还可以分为线性递归，二分递归等。 个人理解就是，“大题小做”，将大问题拆分成若干个相似的小问题，大篇幅的减少代码，同时提高代码的可读性。

2.递归算法的优缺点

优点：

1.思维简单 2. 代码简洁

缺点：

1.调用自身，效率低，时间慢

2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。->效率

3.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性能

递归倒置字符数组(常规版）

#include"stdafx.h" #include<iostream> #include<cstring> //strlen() using namespace std; char str[1000]; int i, j = 1; void inverse(int len, char s[]) //导倒置字符数组 { if (len == 1) return; else if (len>1) { swap(s[i++], s[strlen(str) - (j++)]); //倒置首尾字符 cout << s << endl; //输出每次操作后的的数组 len -= 2; //减去每次交换后的个数 inverse(len, s); //递归 } } int main() { int len; cout << "请输入数组长度和数组：" << endl; cin >> len >> str; inverse(len, str); cout << str << endl; return 0; }

递归倒置字符数组—迭代版

#include<iostream> using namespace std; void reverse(int* A, int lo, int hi)//定义函数 { while (lo < hi) { swap(A[lo++], A[hi--]);//交换两个位置，lo依次加1，hi依次减1 } } void reverse(int* A, int n) { reverse(A, 0, n - 1); } int main() { int a[] = { 1,2,3,4,5,6,7,8,9,10 }; cout << "the reversed array is :"; for (int i = 0; i < sizeof(a) / sizeof(int); i++) { cout << a[i] << " "; } system("pause"); return 0; }

数组求和—二分版

#include<iostream> using namespace std; const int N = 1000; int a[N]; int sum(int A[], int lo, int hi) { if (lo == hi) return A[lo]; int mi = (lo + hi) >> 1;//>>1相当于除以2 return sum(A, lo, mi) + sum(A, mi + 1, hi);//相当于左边一半+右边一半，依次递归，数组区间由最初的n项逐渐缩减为1项 } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } cout << sum(a, 0, n - 1) << endl; return 0; }

菲波那切数列

题目描述：

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。 现在我们要求数列的第n项。

#include "stdafx.h" #include<iostream> using namespace std; int fib(int n) { return (n < 2) ? n : (fib(n - 1) + fib(n - 2)); } int main() { int n; cout << "请输入数字：" << endl; cin >> n; cout << fib(n) << endl; return 0; }

okk啦，第一篇博客，以后多多更新。顺便也可以督促自己学习数据结构。有啥错误，欢迎大家留言。