这篇文章给大家聊聊关于编程思想的迭代和递归，递归的正向和逆向推理，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站哦。

了解每种写作方式之间的细微差别，可以更好地理解迭代思维。

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(b0) { int r=a%b; a=b； b=r； } return a;}1.3 递归不需要临时变量，因为它有递归栈和函数帧的辅助。

int gcd_3(int a,int b){ 返回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;in;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;in;i++) { int c=a + b; a=b; b=c； }返回b;} 2.3

也可以改为下面的公式：

int fib_3(int n){ int a,b,c; a=b=c=1; for(int i=1;in;i++) { a=b; b=c； c=a + b; } return b;}2.4 递归写法

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

int fib(int n){ if(n3) 返回1;返回fib(n-2)+fib(n-1);}

3 求数组中的最大值和第二大值

void big_2(int arr[],int arrSize,int* 第一，int* 第二){ if(arr[0]arr[1]) //初始化两个值{ *first=arr[1]; *第二个=arr[0]; } else { *first=arr[0]; *第二个=arr [1]; } for(int i=0;iarrSize;i++) { if(*firstarr[i]) { *第二=*第一； //第二名被状元取代，状元变成第二名*first=arr[i |由于时间已晚，我们明天再见面。

猴子晚上睡不着觉。起身时，他先尝了一个桃子，然后把桃子分成了5份。正好平分，没有剩余（下同），所以他拿了1份。

后来，另一只晚上睡不着的猴子也来先尝了一个桃子，然后把桃子分成了5份，拿走了1份。

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次才能判断是否能被5整除。

int 桃子(){ int ps=1;restart: int dd=ps; int tt=ps； for(int i=0;i5;i++) { if(dd%5 !=1) { ps++;转到重新启动； } dd=(dd-1) – (dd-1)/5; if(dd%5==0) 返回tt; //3121} 递归：

int 除(int n, int m) //{ if(n/5==0 || n%5!=1) return 0;如果（m==1）返回1；返回除法(n-n/5-1 , m-1); //类型转换n=n-(n-1)/5-1，相当于n=n-n/5-1 //返回dived(n-(n-1)/5-1, m-1) ;}int 桃子(){ int n;整数米=5; for(n=1; n++) if(peach(n,m)) { 返回n;休息；

4 五猴分桃问题

#include iostreamusing 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;同时（1）； return 0;}//下面定义mysin函数，求sin值double mysin(double x){ double sum=x,x_pow=x,item; int n=1,事实=1,符号=1; //定义变量时赋予初始值，累计和中已考虑第一项do {fact=fact*(n +1)*(n+2); //fact用于表示阶乘，在公式x_pow*=x*x中作为分母； //x_pow用在分子中表示阶乘，在公式中用作分母sign=-sign； //确定要累加项的符号item=x_pow/fact*sign; //计算要累加的item sum+=item; //将该项添加到n+=2; } while(myabs(项目)1e-6); return sum;}//下面定义了myabs函数double myabs(double x){ return ((x=0)?x:-x);}

5 利用泰勒展开式求sin值

小猴子一天摘了很多桃子，我吃了一半第一天吃了一个，后来忍不住又吃了一个；第二天我又吃了一半，然后又吃了一份；之后我每天都这样吃。第十天，小猴子发现只有一个桃子。问小猴子第一天摘了多少个桃子。

递归的逆推导：

int 猴子(int 天){ int ps=1; for(;days1;days–) { ps=ps*2+2;返回ps； //10 1534} 也可以写成：

#includestdio.hint main(){ int day=9,x1=0,x2=1; for(;day0;day–) { x1=(x2+1)*2; x2=x1; } printf(‘% d\n’,x1);} 也可以写成递归形式：

#include ‘stdio.h’int sumPeach(int day){ if (day==10) return 1;否则返回2 * sumPeach(day + 1) + 2;}int main(){ int sum;总和=总和Peach(1); printf(‘%d\n’,sum);}7 链表操作

bool ListInsert(LinkList *head,int i,ElemType e){ int j=0; LinkList *pMove=head,*pNew; while (ji-1 pMove!=NULL) //查找第i-1个节点{ j++ ; pMove=pMove-下一个； //Move} if (pMove==NULL) //未找到位顺序为i-1的节点return false; else //找到位序为i-1的节点*p { pNew=(LinkList *)malloc(sizeof(LinkList));//创建新节点*s pNew-data=e; pNew-下一个=pMove-下一个； //在*p后面插入*s pMove-next=pNew; //连接返回true; }}7 二分查找

int binarySearch(vectorint nums, int target){ if(nums.size()==0) return -1; } int 左=0, 右=nums.size() – 1; while(左=右){ int mid=左+ ((右- 左) 1); if(nums[mid]==target){ 返回mid; } //解空间变为[mid+1, right] else if(nums[mid] target) left=mid + 1; //解空间变为[left, mid – 1] else right=mid – 1; } return -1;}8 快速排序

#includestdio.h//快速排序递归实现void fastsort(int data[],intfirst,intlast){ int i, j, t, base;如果（第一个最后一个）返回；基=数据[第一个]； /*使用第一个元素作为基数*/i=first; j=最后一个； while(i!=j) /*重复下面的过程，直到i和j相遇*/{ while(data[j]=base ij) /*j从右到左开始，找到比base小的元素数量*/j–; while(data[i]=base ij) /*i 从左到右，查找大于基数的元素*/i++; /*当i和j不满足的时候，交换两个数*/if(ij) { t=data[i];数据[i]=数据[j]；数据[j]=t； } } 数据[第一个]=数据[i]； /*保存i,j在基位置相遇的值*/data[i]=base; /*将基数保存在适当的位置*/fastsort(data,first,i-1); /*使用同样的策略，递归处理左边的部分*/fastsort(data,i+1,last); /*使用同样的策略递归处理右边的部分*/}int main(){ int data[10]={6, 1, 2, 7, 9, 3, 4, 5, 10, 8};快速排序（数据，0,9）；整数我； for(i=0; i10; i++) printf(‘%d ‘, data[ i]); printf(‘\n’);返回0；}