c语言函数递归算法 c语言函数递归

C语言递归算法？

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理

创新互联-专业网站定制、快速模板网站建设、高性价比温宿网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式温宿网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖温宿地区。费用合理售后完善，十载实体公司更值得信赖。

其实简单一点来说就像数学里面的数列的通项公式：

例如一个数列是2，4，6，8，10......

很容易就可以得到通项公式是a[n]=2*n n是大于0的整数

你肯定学过这个数列的另外一种表示方式就是： a[1]=2, a[n]=a[n-1]+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)!,当n1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。

我给出一种优化的递归算法---尾递归。

从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.

普通递归阶乘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语言函数递归调用？

第一级递归：n=483，i=n/10=48≠0

注意此时先递归调用convert(48)，待递归返回再输出当前n的个位数字n%10=3

第二级递归：n=48，i=n/10=4≠0

此时继续递归调用convert(4)，待递归返回再输出当前n的个位数字n%10=8

第三级递归：n=4，i=n/10=0

此时递归终止，先输出当前n的个位数字n%10=4

再返回上一级递归输出8，最后返回第一级递归输出3

因此最终输出为：4 8 3

c语言递归函数

递归函数：

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

函数介绍：

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。

其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

例子：

//代码1

void func()

{

//...

if(...)

func();

else

//...

}

条件：

一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：

1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；

2） 必须有一个终止处理或计算的准则。

梵塔的递归函数：

//C

void hanoi(int n,char x,char y,char z)

{

if(n==1)

move(x,1,z);

else

{

hanoi(n-1,x,z,y);

move(x,n,z);

hanoi(n-1,y,x,z);

}

}

用递归求表达式1-2+3-4……-100的和（注：C语言）

可以使用递归来实现对表达式 `1-2+3-4……-100` 求和。递归算法的基本思路是将一个大问题分解成多个相同或类似的小问题，然后将这些小问题按照一定规律组合成大问题的解。对于这道题，可以将表达式 `1-2+3-4……-100` 分解成两个子问题：

- 1-2+3-4……-98-99+100

- -99+100

然后对每个子问题递归求解即可。

具体的递归算法可以这样实现：

```c

int sum = 0; // 定义变量 sum 存储表达式的和

int calc(int n) { // 定义递归函数 calc，n 表示当前计算的数值

if (n == 1) {

return 1; // 表达式中只有一个数值 1，直接返回 1

}

if (n % 2 == 0) {

return -n + calc(n - 1); // 当前数值为偶数，则加上负号

} else {

return n + calc(n - 1); // 当前数值为奇数，则加上正号

}

}

int main() {

sum = calc(100); // 计算表达式的总和

printf("表达式的和为：%d

", sum);

return 0;

}

```

运行结果为：

```

表达式的和为：-50

```

其中，`calc(n)` 函数用于递归计算表达式前 n 个数的和。如果当前 n 为奇数，则返回 `n + calc(n - 1)`；如果当前 n 为偶数，则返回 `-n + calc(n - 1)`。最终的表达式和存储在变量 `sum` 中，通过 `printf` 函数输出。

需要注意的是，在实际的应用中，递归算法往往会带来额外的开销、增加内存负荷，所以需要根据具体问题的规模和复杂度来选择算法。对于本题，迭代算法也可以轻松实现，效率更高。