递归算法经典题目(递归算法例题)
设计递归算法
基本思想是先用必要条件找，然后再遍历一遍验证是否满足条件，不用递归很容易。
因为你限制了要用递归，那么看上去只能这样了：
若a在A中占据一半以上，那么把A分成A1，A2两部分之后，a在其中至少一个子列中也占据一半以上。
利用这一性质，递归地在A1,A2中寻找候选元素，然后遍历数组以验证这两个候选元素(如果存在的话)是否满足条件。
根据归纳假设，在A1,A2中寻找候选元素的时间复杂度是O(n)，再对A遍历至多两遍，复杂度仍然是O(n)。
求经典的递归算法以及案例（可用C#、PHP、JAVA其中一种语言来写）!
我用C#来写（注意，更多的请直接到我的个人博客，点击， ，收看） 【例1】有甲、乙、丙、丁四人，从甲开始到丁，一个比一个大1岁，已知丁10岁，问甲几岁？【分析】这是递归法的一道非常典型的题目——因为我们可以很显然知道：假设要计算甲的年龄，那么必须直到乙的年龄；同样，算乙的必须直到丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（方便期间我们给他们编号——甲＝1，乙＝2，丙＝3，丁＝4），那么存在这一个F(X)函数，X表示某人的编号，其规律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10显然，直到X=4的时候是一个终止值，其余情况下都是返回F(X’)，F(X’’)……F(X’’……’)，且前者总是比后至大1，这也符合了X’和X总是呈现一定函数关系（设想一下，如果不是等差和等比，又怎么可能在一个递归函数中进行计算？要知道，函数本身就是一个公式表示，既然是公式，那么一定是一种函数关系Y=F(X)），此处显然X和X’的关系是X=X’+1。根据规律式，我们可以写出该递归函数：int AgeCal(int id)
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】计算n！【分析】虽然这道题目不像例1一样清晰明了告诉你使用“递归”法反推，但是我们有这样一个常识——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.显然n与n-1，n-2也是线性的递减数列（等差关系）。其规律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止别人直接输入0)编写其递归函数，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一组整数中的最大(小)值（整数是一个int[]数组，个数未知）。【分析】当数字只有两个的时候，我们可以使用和直接比较；但是当数字超过2个的时候（假设3个），那么我们可以使用一个预订的函数（比如Max(1,2)和3进行比较），由于1，2两个数比较的时候已经得到一个最大值，因此在回代到Max中又变成了两个数的比较。这样，我们可以发现一个规律：F(1,2,3,4……n)＝F(1,2,3,4……n-1)和n比较F(1,2,3,4……n-1)＝F(1,2,3,4……n-2)和n-1比较……F(1,2,3)=F(1,2)和3比较F(1,2)＝结果（并回代）相应的递归函数如下(C#)：Code
int Max(int[]numbers)
{
if(numbers.Length==2)
{
return (numbers[0]numbers[1]?numbers[0]:numbers[1]);
}
else
{
int[]tempnumbers=new int[numbers.Length-1];
for(int i=0;inumbers.Length-1;++i)
{
tempnumbers[i]=numbers[i];
}
return (Max(tempnumbers)numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]
}
}
一道单链表递归删除的算法题，请高手指点！
解答如下：
第一，你说的破坏原链表指的是什么呢？这样做理论上并没有改变原链表的特性，但是少了一些结点。
第二，在删除重复数节点L时并没有将其前趋节点的next指向所删除节点的next.所以你这样做会把链表断开。也就不能构成一个链表了。所以这么做是错误的。
第三、.void delsamenode(LinkList *L)中L前为何加，这个问题“”是不需要加的。
下面是调试通过的代码：
#include windows.h
#include string.h
#include malloc.h
#include stdio.h
struct linklist
{
int x;
struct linklist *next;
};
int flag=0; //定义一上标志，声明为全局变量。作为判断是否存在相同数
struct linklist *q ,*h; //q作为移动指针，h作为返回的头指针
int in(int x,struct linklist *l)
{
struct linklist *p,*t;
p=l;
while(p!=NULLp-x!=x)
{
p=p-next;
}
if (p==NULL)
{
return 0;
}
else
{
return 1;
}
}
struct linklist *del(struct linklist *l)
{
struct linklist *p;
if (l==NULL||l-next==NULL)
{
return h;
}
if (in(l-x,l-next))
{
p=l;
if (flag) //如果之前已经存在一个数，并且在后面没有和它相同的数了，
那么就将要 删除的这一个数的前一个数的指针指向它的后一数。
{
q-next=p-next;
l=l-next;
}
else //如果不存在这样一个数，则将l下移。
{
l=l-next;
}
free(p);
del(l);
}
else
{
++flag;
if (flag==1) //一旦出现一个后面不存在和它相同的数时，h指向这个数，
//且h作为头指针,只判断一次。
{
h=l;
}
q=l; //q还是指向l，进行下一次的指针移动。
del(l-next);
}
}
int main()
{
struct linklist *l,*p,*t;
int i;
t=p=l=(struct linklist *)malloc(sizeof(struct linklist));
for (i=0;i6;i++)
{
if (i==0)
{
scanf("%d",(t-x));
}
else
{
t=(struct linklist *)malloc(sizeof(struct linklist));
scanf("%d",(t-x));
p-next=t;
p=t;
}
}
p-next=NULL;
l=del(l);
while (l!=NULL)
{
printf("%d ",l-x);
l=l-next;
}
system("pause");
}
我进行了三种可能的输入测试，都没有问题：
第一种:1 2 3 4 5 6，输出还是 1 2 3 4 5 6
第二种:3 0 3 1 0 3，输出是 1 0 3
第三种:1 2 3 4 6 4,输出是 1 2 3 6 4
如果还有其它问题的话，找我！
一道C语言的题目，递归法
#include
#include
/*求n的
阶乘
，递归，
分母
部分
*
结束条件为：1的阶乘=1
*
递归时，一定要有结束条件
*/
int
factorial
(n)
{
if(n==1)
//递归结束条件，1的阶乘为1
return
1;
else
return
n*factorial(n-1);
//n的阶乘为n乘以(n-1)!
}
int
main()
{
int
n,x;
size_t
i;
//i为
无符号整数
double
re=0;
printf("input
n
and
x:");
scanf("%d%d",n,x);
//输入n和x的值
for(i=1;i=2*n-1;i+=2)
{
/*pow函数求的是x的i次方，分母为
i的
阶乘。本部分可以优化，因为i的阶乘算出来了，所以i+2的阶乘就是i的阶乘*(i+1)*(i+2)，不用重复来计算阶乘。自己可以试试*/
re
+=
pow(x,i)/factorial(i);
}
printf("\nn=%d\tx=%d\tresult=%f\n",n,x,re);//打印出
最后的结果
return
0;
}
C语言猴子吃桃递归法
一个猴子摘了一些桃子,它每天吃了其中的一半然后再多吃了一个,
直到第10天,它发现只有1个桃子了,问它第一天摘了多少个桃子?
猴子分N天吃完了桃子,要想求出第1天的桃子数,就先要求出第2天的桃子数,.......因此,有:
a1=(a2+1)*2;
a2=(a3+1)*2;
a3=(a4+1)*2;
......
a9=(a10+1)*2;
a10=1;
现在就知道了算法,我们可以用递归来求解:
int qiu(int a,int n)
{
if(n==1) a=1; //第10天就只剩1个了
else a=(a(n-1)+1)*2; //前一天总比后1天多一半加1
}
-------------------------------------
#includestdio.h
int qiu(int a,int n);
main(){
int zuih=1,tians=10;//最后一天的个数,天数
long sum;
sum=qiu(1,10);
printf("di yi tian you %ld ge.\n"):
}
int qiu(int a,int n)
{
if(n==1) a=1; //第10天就只剩1个了
else a=(a(n-1)+1)*2; //前一天总比后1天多一半加1
}