递归算法c语言实例（C语言递归算法）

本文目录

• C语言递归算法
• c语言 设计一个递归算法
• C语言 用递归方法求X的n次方
• c语言算n的阶乘的递归算法
• C语言迭代与递归比较（举例）
• c语言,求递归算法的技巧最好有经典例子！

C语言递归算法

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理其实简单一点来说就像数学里面的数列的通项公式：例如一个数列是2，4，6，8，10......很容易就可以得到通项公式是a+2 n是大于1的整数其实这就是一个递归的形式，只要你知道初始项的值，未知项和前几项之间的关系就可以知道整个数列。程序例子：比如你要得到第x项的值普通循环：for(int i=1; i《=n; i++) if (i == x) cout 《《 2*i; /*cout 相当于 c里面的printf,就是输出.*/递归：int a(int x) { if (x = 1) return 2; /* 第一项那肯定是2了，这个也是递归的终止条件！ */ else return a(x-1)+2; /* 函数自身调用自身是递归的一个特色 */比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2其实递归方法最接近自然，也是最好思考的一个方法，难点就是把对象建模成递归形式，但是好多问题本身就是以递归形式出现的。普通递归就是数据结构上的堆栈，先进后出。例如上面x=4,把a(4)放入栈底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出栈，a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8再比如楼上的阶乘例子，当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值，也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n》1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。我给出一种优化的递归算法---尾递归。从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.普通递归阶乘fac(x),就1个x而已，尾递归用2个参数fac(x,y),y存放阶乘值。所以谭老的程序就变成// zysable’s tail recursive algorithm of factorial.int fac(int x, int y) { if (x == 1) return y; else return fac(x-1, y*x);}int ff(int x) { if (x == 0) return 1; else return fac(x,1);}对于这个程序我们先看函数ff，函数ff其实是对fac的一个封装函数，纯粹是为了输入方便设计的，通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了，我通过走一遍当x=3时的值即为3!来说明一下。首先ff(3),x!=0,执行fac(3,1).第一次调用fac，x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到，y已经累计了一次阶乘值了，然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候，出栈的乘积，所以减少了出栈后的步骤，而且现在世界上很多程序员都在倡议用尾递归取消循环，因为有些在很多解释器上尾递归比迭代稍微效率一点.基本所有普通递归的问题都可以用尾递归来解决。一个问题以递归来解决重要的是你能抽象出问题的递归公式，只要递归公式有了，你就可以放心大胆的在程序中使用，另外一个重点就是递归的终止条件；其实这个终止条件也是包含在递归公式里面的，就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序，查看运行过程，有些时候你会发现你越看越不明白，只要递归公式转化成程序语言正确了，结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归，结果越弄越糊涂。如果想很清楚的了解递归，有种计算机语言叫scheme,完全递归的语言，因为没有循环语句和赋值语句。但是国内人知道的很少，大部分知道是的lisp。好了，就给你说到这里了，希望你能学好递归。PS:递归不要滥用，否则程序极其无效率，要用也用尾递归。by 一名在美国的中国程序员zysable。

c语言 设计一个递归算法

这哪是一个递归算法，这么多个： 给你设计其中一个：这是递归得到数组a【】的前k个元素的最大值 int max(int a,int k) { if(k==2)return(a》a?a:a); else return max(a,k-1)》a; } main() { int t, b={1,2,3,4,5,6,7,8}; t=max(b,8); printf(“%3d“,t); getch(); }

C语言 用递归方法求X的n次方

#include《stdio.h》

int power(int x,int n)

{

if(n==0)

return 1;

elseif(n%2==1)

return x*power(x,n-1);

else{

int y=power(x,n/2);

return y*y;

}

}

int main()

{

int a,b,c;

printf(“enter x and n:“);

setvbuf(stdout,NULL,_IONBF,0);

scanf(“%d%d“,&a,&b);

c=power(a,b);

printf(“结果为%d“,c);

return 0;

}

扩展资料

#include《stdio.h》

double power(double x,int n);

main()

{

double x;

int n;

printf(“Input x,n:“);

scanf(“%lf,%d“,&x,&n);

printf(“%.2lf“,power(x,n));

}

double power(double x,int n)

{

double a=1.0;

int i;

for(i=1;i《=n;i++)

a*=x;

return a;

}

参考资料：百度百科 - 递归调用

c语言算n的阶乘的递归算法

思路：递归求阶乘函数，如果输入的参数等于1则返回1，否则返回n乘以该函数下次递归。

参考代码：

C语言迭代与递归比较（举例）

我举个例子：①斐波那契数列：1，1，2，3，5，8，13，21，34......迭代：int Fib;}递归：int Fib(int n){ if(n==0||n==1)return 1; else return (Fib(n-1)+Fib(n-2));}

c语言,求递归算法的技巧最好有经典例子！

c语言中递归的最经典应用是求两个数的最小公约数，代码如下：int MinDivisor( int m, int n){ if(m%n==0) return n; else return MinDivisor(n, m%n);}