迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
递归其实就是利用系统堆栈，实现函数自身调用，或者是相互调用的过程。在通往边界的过程中，都会把单步地址保存下来，再接照先进后出进行运算。递归的数据传送也类似。
递归的运算方法，决定了它的效率较低，因为数据要不断地进出栈。在应用递归时，只要输入的n值稍大，程序求解就比较困难。因而从计算效率来说，递推往往要髙于递归。
递推免除了数据进出栈的过程，也就是说,不需要函数不断地的向边界值靠拢，而直接从边界出发，逐步推出函数值， 直观明了。
在有些情况下，递归可以转化为效率较髙的递推。但是递归作为重要的基础等法，它的作用不可替代。
迭代：利用变量的原值推算出变量的一个新值，如果递归是自己调用自己的话，迭代就是A不停的调用B。
递推：它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复。
递归与递推区别：递归的步骤中包含递推，如一个规模为n的问题，递归首先通过回溯将问题回溯到n-1，n-2……，然后再通过递推从1的结果一直递推到n。
递归与迭代的区别：递归中一定有迭代，但是迭代中不一定有递归，大部分可以相互转换。能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。
可以这么理解，递推和迭代都是正向的将一个复杂问题分解为小问题，一步一步得出结果；而递归是逆向的，多了一步回溯的过程。
每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。
recursion simply called itself with a different argument.
递归的执行顺序：
调用：递归函数前的代码；
回推：递归函数后的代码；
一些较流行的程序语言允许过程的递归调用。递归调用就是过程调用本身。递归实现的是：当过程每一次执行后，都能返回到最近一次调用它的过程中。这样各调用点之间形成一种后进先出关系，而栈结构正适合来存储这些调用点。
void dec2(unsigned long n)
{
int r;
r=n%2; //最后一位
if(n>=2)
dec2(n/2);//递归后进先出的特点很适合倒序计算；
putchar(r==0?'0':'1');
}
递归与递推
递推的关注点放在起始点条件而递归的关注点放在求解目标上
重在表现第i次与第i+1次的关系
void convert(int x)
{
if((x/2)==0)
cout<<x;
else
{
convert(x/2);
cout<<x%2;
}
}
“递归”源自于数学上的递推式和数学归纳法。
“递归”是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得；
(D)“递归”是由前n-1项计算第n项的一种方法。
fac(n);
n*fac(n-1);
n=n-1表达式会迭代n次
void preOrder(lptree root);
preOder(root->LChild);
root = root->LChild;
一直迭代，直到root==NULL;
1 循环
不断重复执行一段代码
2 迭代
变量不断自我更新；
3 递归
由编译器维护一个栈结构，函数不断递推（包括参数迭代入栈），函数不断回归（包括参数迭代出栈，顺序相反）；程序如果要用循环代替递归，就需要自己来创建和维护一个或多个栈。
RBT比Hash适用范围更广，因为：
1：RBT可以查找范围（比如3与5之间的数据），而Hash只能进行等值查找
2：RBT的最差查找时间是O(LogN)，而Hash的最差查找时间是O(N)
3：RBT的平均查找时间受数据变化的影响很小，而Hash的平均查找时间受数据变化的影响很大。
4：使用Hash需要使用大量的数据进行测试，以调整hash函数，减少冲突。
如果你不想在设计hash函数上花费精力的话，使用hash还不如使用map。其实Hash更适用于在相对固定的数据集中进行查找，这时可以精心设计一个冲突足够小的hash函数。
递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。
对于单向递归和尾递归，可以用迭代的方式来消除递归，否则，需要借助栈。
如果一个函数在其函数体内直接或间接地调用了自己，该函数就称为递归函数，它通常将一个大型复杂的问题一层层地转化为一个与原问题相似的但规模较小的问题求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码。
当调用一个函数时，系统内部发生了一系列的动作。
(1)开辟函数的栈空间
(2)将当前运行状态压栈
(3)将返回地址(调用函数的地方)压栈
(4)在栈内分配参数空间，传递参数信息
(5)执行被调用函数，如果有局部变量，则在栈内分配空间
当函数运行结束时，系统内部又一系列的动作，这些恰巧与调用函数时的动作顺序相反。
(1)释放栈内局部变量空间
(2)释放栈内参数空间
(3)退栈，得到返回地址，程序跳转到调用函数处等待继续执行
(4)退栈，得到程序运行状态，恢复调用函数前的状态。
(5)释放该函数的栈空间
int fib(int n) {
if (n == 0 || n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
Again, we emphasize that while this function is neat, concise, and easy to understand, it is not efficient.
For example, consider the calculation of F(5).
F(5)
= F(4) + F(3)
= F(3) + F(2) + F(3)
= F(2) + F(1) + F(2) + F(3)
= F(1) + F(0) + F(1) + F(2) + F(3)
= 1 + 1 + 1 + F(1) + F(0) + F(3)
= 1 + 1 + 1 + 1 + 1 + F(2) + F(1)
= 1 + 1 + 1 + 1 + 1 + F(1) + F(0) + F(1)
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 8
void decToBin(int n)
{
if (n > 0)
{
decToBin(n / 2);
printf("%d ", n % 2);
}
}
The call decToBin(13) will print 1101.
decToBin(13)
decToBin(6)
print(13 % 2)
decToBin(3)
print(6 % 2)
print(13 % 2)
decToBin(1)
print(3 % 2)
print(6 % 2)
print(13 % 2)
decToBin(0) = do nothing
print(1 % 2) = 1
print(3 % 2) = 1
print(6 % 2) = 0
print(13 % 2) = 1
本页共90段，2847个字符，5696 Byte(字节)