编程需要迭代思维，迭代也是一种程序渐进式开发的方法。解决问题不但需要推理能力，还需要逆向思维的能力。另外，递归也是绝大多数编程语言支持的一种很重要的语法机制。因为一些大规模的问题总是由一些小规模的问题组成，且有时小规模问题的解与整个问题的解几乎一模一样，如快速排序，二分查找。

1 计算最大约数的迭代思维

理解各个写法的细微区别，可以更好地理解迭代思维。

gcd(int a,int b)

1.1 迭代的三个量，a, b, r = a%b。以r是否为0为循环结束条件，返回r的前一个迭代量b。

int gcd(int a,int b) //用辗转相除法，求两数的最大公约数{    while(int r = a%b)    {        a = b;        b = r;    }    return b;}

1.2 迭代的三个量，a, b, r = a%b。以b是否为0为循环结束条件，返回b的前一个迭代量a。

int gcd_2(int a,int b) //用辗转相除法，求两数的最大公约数{    while(b>0)    {        int r=a%b;        a=b;        b=r;    }    return a;}

1.3 递归因为有递归栈和函数帧的辅助，无须临时变量。

int gcd_3(int a,int b){    return b==0 ? a : gcd(b,a%b);}

递归的数据都保存在栈的函数帧上。且参数构成了迭代关系：

a = b;b = a%b;

且因为是值传递，相互不影响。

2 计算斐波那契数列的迭代思想

了解各个写法的细微区别。

2.1

迭代表达式是a=b; b= a+b; 但后式中的a必须是更新前的a，所以先用临时变量存一下：

int fib(int n){    int a,b;    a = b = 1;    for(int i=2;i<n;i++)    {        int t = a;        a = b;        b = t + b; // t也就是更新前的a    }    return b;}

2.2

迭代表达式是a=b; b= a+b; 但后式中的a必须是更新前的a，直接用一个临时变量存储，c= a + b; 则迭代表达式变为：c=a+b;a=b;b=c;：

int fib_2(int n){    int a,b;    a = b = 1;    for(int i=2;i<n;i++)    {        int c = a + b;        a = b;        b = c;    }    return b;}

2.3

也可以变更为下式：

int fib_3(int n){    int a,b,c;    a = b = c = 1;    for(int i=1;i<n;i++)    {        a = b;        b = c;        c = a + b;    }    return b;}

2.4 递归写法

递归写法因有栈帧辅助，不需要临时变量

int fib(int n){    if(n<3)        return 1;    return fib(n-2)+fib(n-1);}

void big_2(int arr[],int arrSize,int* first,int* second){    if(arr[0]<arr[1])   // 初始化两个值    {        *first = arr[1];        *second = arr[0];    }    else    {        *first = arr[0];        *second = arr[1];    }    for(int i=0;i<arrSize;i++)    {        if(*first<arr[i])        {            *second = *first; // 榜眼被状元取代，状元变榜眼            *first = arr[i];      // 状元被取代        }        else if(*second<arr[i] && *first != arr[i])            *second = arr[i];    }}

花果山上五猴，一日采摘桃子若干。因天色已晚，相约明日再分。

一猴夜不能寐，起来先尝一桃，再自行将桃分为5份，恰巧均分，并无余数(下同)，取走1份。

其后又有一猴夜不能寐，也来先尝一桃，然后将桃分为5份，取走1份。

5猴都如是行之。

次日清晨，5猴醒来，见桃子仍是一堆，且正好均分，欢天喜地。

问五猴至少采摘桃子多少才能如此进行。

保守估计：2^5*5+6

最高数量：5^5

假设最初有-4个桃子，一只猴子扔了一个桃子，变成了-5个桃子。然后它拿走了-5的1/5，也就是-1个桃子，于是剩下的桃子又变成了-4个。后面的猴子重复前面的操作，每次都是扔掉-1个，自己拿走-1个，所以刚好抵消，这个操作可以无限地进行下去。用数学术语说，-4是这个体系的一个不动点。

迭代表达式：dd = (dd-1) - (dd-1)/5;

迭代的前提是dd%5 == 1，要迭代五次来判断是否能被5整除。

int peaches(){    int ps = 1;restart:    int dd = ps;    int tt = ps;    for(int i=0;i<5;i++)    {        if(dd%5 != 1)        {            ps++;            goto restart;        }        dd = (dd-1) - (dd-1)/5;    }    if(dd%5 == 0)        return tt;  // 3121}

递归：

int divided(int n, int m)  // {    if(n/5==0 || n%5!=1)        return 0;    if(m==1)         return 1;    return divided(n-n/5-1, m-1); // 类型转换n=n-(n-1)/5-1,等同于n=n-n/5-1    //return divided(n-(n-1)/5-1, m-1);}int peaches(){    int n;    int m = 5;    for(n = 1; ; n++)        if(peach(n,m))        {            return n;            break;        }}

#include <iostream>using namespace std;const double pi=3.1415926;double mysin(double x);double myabs(double x);int main( ){    cout<<"sin(π/2)的值为"<<mysin(pi/2)<<endl;    cout<<"sin(56°)的值为"<<mysin((56.0/180)*pi)<<endl;    while(1);    return 0;}//下面定义mysin函数，求sin值double mysin(double x){    double sum=x,x_pow=x,item;    int n=1,fact=1,sign=1;     //定义变量时赋初值，已经将第一项考虑到累加和sum中    do    {        fact=fact*(n+1)*(n+2);  //fact用于表示阶乘，在公式中作分母        x_pow*=x*x;             //x_pow是分子中用于表示阶乘，在公式中作分母        sign=-sign;             //确定即将要累加的这一项的符号        item =x_pow/fact*sign;  //计算出要累加的项        sum+=item;              //将该项累加上去        n+=2;    }while(myabs(item)>1e-6);    return sum;}//下面定义myabs函数double myabs(double x){    return ((x>=0)?x:-x);}

一只小猴子一天摘了许多桃子，第一天吃了一半，然后忍不住又吃了一个；第二天又吃了一半，再加上一个；后面每天都是这样吃。到第10天的时候，小猴子发现只有一个桃子了。问小猴子第一天共摘了多少个桃子。

递推之逆推：

int monkey(int days){    int ps = 1;    for(;days>1;days--)    {        ps = ps*2+2;    }    return ps;  // 10 1534}

也可以写成：

#include<stdio.h>int main(){    int day=9,x1=0,x2=1;    for(;day>0;day--)    {        x1=(x2+1)*2;        x2=x1;    }    printf("%d\n",x1);}

也可以写成递归形式：

#include "stdio.h"int sumPeach(int day){    if (day == 10)        return 1;    else    return 2 * sumPeach(day + 1) + 2;}int main(){    int sum;    sum=sumPeach(1);    printf("%d\n",sum);}

7 链表操作

bool ListInsert(LinkList *&head,int i,ElemType e){    int j=0;    LinkList *pMove=head,*pNew;    while (j<i-1 && pMove!=NULL) //查找第i-1个结点    {        j++;        pMove=pMove->next; // 移动    }    if (pMove==NULL)            //未找到位序为i-1的结点        return false;    else            //找到位序为i-1的结点*p    {        pNew=(LinkList *)malloc(sizeof(LinkList));//创建新结点*s        pNew->data=e;        pNew->next=pMove->next;                        //将*s插入到*p之后        pMove->next=pNew;   // 连接        return true;    }}

7 二分查找

int binarySearch(vector<int>& nums, int target){    if(nums.size() == 0)        return -1;    int left = 0, right = nums.size() - 1;    while(left <= right){        int mid = left + ((right - left) >> 1);        if(nums[mid] == target){ return mid; }            // 解空间变为 [mid+1, right]        else if(nums[mid] < target)            left = mid + 1;        // 解空间变为 [left, mid - 1]               else            right = mid - 1;    }    return -1;}

8 快速排序

#include<stdio.h>//快速排序递归实现void quicksort(int data[],int first,int last){    int i, j, t, base;    if (first>last)        return;    base=data[first];               /*用首元素作为基数*/    i=first;    j=last;    while(i!=j)                     /*重复下面的过程，直到i和j相遇*/    {        while(data[j]>=base && i<j)  /*j从右向左，找到小于基数的元素*/            j--;        while(data[i]<=base && i<j)  /*i从左向右，找到大于基数的元素*/            i++;        /*当i和j没有相遇有时候，交换两个数*/        if(i<j)        {            t=data[i];            data[i]=data[j];            data[j]=t;        }    }    data[first]=data[i];        /*将i,j相遇处的值保存在基数位置*/    data[i]=base;               /*将基数保存在其应该的位置*/    quicksort(data,first,i-1);  /*用同样的策略，递归处理左边的部分*/    quicksort(data,i+1,last);   /*用同样的策略，递归处理右边的部分*/}int main( ){    int data[10] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};    quicksort(data, 0,9);    int i;    for(i=0; i<10; i++)        printf("%d ", data[i]);    printf("\n");    return 0;}

－End－