每次用递归都感觉有点难，这个趁着恶补基础知识的时候，专门看了一遍递归，算法4的。
1.1 递归介绍
方法可以调用自己，例如：下面给出了bin_search的二分查找的一种实现。（算法4中使用的是Java，但是我是c++系的，就用c++实现，语言不重要）。我们就会经常使用递归，因为递归代码比相应的非递归代码更加简洁优雅、易懂。下面这种实现中的注释就言简意赅地说明了代码的作用。
int bin_search(int key, int *a, int left, int right)
{//递归第一条，总是包含一个return的语句if(left > right) return -1;int middle = left + (right - left)/2;if(key < a[middle]) bin_search(key, a, left, middle-1);\else if(key > a[middle]) bin_search(key, a, middle+1, right);else return middle;
}
编写递归代码时最重要的有以下三点。
- 递归总有一个最简单的情况——方法的第一条语句总是一个包含return的条件语句。
- 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在上面代码中，第四个参数和第三个参数的差值一直在缩小。
- 递归调用的父问题和尝试解决的子问题不应该有交集。在上面代码中，两个子问题各自操作的数组部分是不同的。
违背其中任意一条都可能得到错误的结果或低效的代码，而坚持这些原则能写出清晰，正确且容易评估性能的程序。使用递归的另一个原因是我们可以使用数学模型来估计程序的性能。这个要在后面讲。
1.2 练习
看了递归的总结了之后，要做做练习题，控固一些递归的知识点，所以就做算法4，第一节的练习题。
1.1.16 给出exR1(6)的返回值
string exR1(int n)
{if(n < 0) return "";return exR1(n - 3) + n + exR1(n - 2) + n;
}int main()
{cout << "递归代码学习" << endl;string str = exR1(6);cout << str << endl;return 0;
}
c++好像不知道string加法，不过就这样吧，我们不执行了，直接推结果。
这里已经把递归的流程分析，递归分析不用慌，一层一层分析，知道返回的时候，就有结果了，这道题的答案是：311361142246。
1.1.17 找出一下递归函数的问题
string exR2(int n)
{string s = exR2(n -3)+ n + exR2(n -2)+ n;if(n < 0) return "";return s;
}
这一个是违反了递归的第一条性质，也就是第一条不包含return语句，这样导致递归函数一直递归，知道把栈搞溢出。
1.1.18 请看一下递归函数
int mustery(int a, int b)
{if(b == 0) return 0;if(b % 2 == 0) return mustery(a+a, b/2);return mustery(a+a, b/2) + a;
}
mustery(2, 25)和mustery(3, 11)的返回值是多少
这个递归比较简单，只要一个方向递归，像第一题两个方向递归才难。
1.1.19 在计算机上运行一下程序
long F(int N)
{if(N==0) return 0;if(N==1) return 1;return F(N-1)+F(N-2);
}
计算这段程序在一个小时之内能够得到的F(N)结果的最大N值是多少？这个有谁知道，可以讲解一波，我也不清楚。
开发F(N)的一个更好的实现，用数组保存已经计算过的值。
long F2(int N, long *value)
{//static long *value = new long[N];if(N == 0){value[0] = 0;value[1] = 1;return 0;}if(N == 1){value[0] = 0;value[1] = 1;return 1;}//printf("N %ld %ld %ld\n", N, value[N-1]+value[N-2]);value[N-1] = F2(N-1, value);return value[N-1]+value[N-2];
}
递归函数还是一贯都是开始是return，因为我们要从0,1开始，所以0,1需要做特殊处理，然后从2开始的话，我们就递归算出每个数组的值，然后利用已经保存好的数组的值，然后在相加，就得到了想要的结果。
1.1.20 编写一个递归的静态方法计算ln(N!)的值
unsigned long jieceng(int N)
{if(N == 1 || N == 0) {return 1;}return jieceng(N-1)*N;
}
这是阶乘的答案
