C语言中的递归函数写法

---

递归定义

  一个函数在它的函数体内直接或间接地调用自身称为函数的递归调用，而这种函数被称为递归函数。
  直接调用：是指函数直接调用自己。
  间接调用：是指函数在递归函数调用的下层再调用自己。
  
  例：直接调用，Function1()->调用Function1()
  间接调用，Function1()->调用Function2()->Function2()->调用Function1()

讲解

递归函数简单的理解就是在不停地调用自己，如果不懂请参照 “讲解” 。

其实递归函数在使用时只需要明确一点：我写这个函数是干嘛用的，比如在用递归写计算N！的C语言程序时，只需要明确我写的函数是用来计算当前传入参数N与它前面（N - 1）! 的乘积，写起来就会很简单。
而且要明确一点，那就是：递归调用的时候必须要有终止条件，也就是递归终点。否则程序就会一直递归，直到栈溢出。（不用纠结，深入学习后就会知道）

---

例子

一 、用递归算法计算 N 的阶乘。

#include<stdio.h>
int F( int n ) //递归函数 
{
	long sum; //
	if(n == 0 || n == 1) //递归终点。 
		return 1;
	else
	{
		sum = n * F( n - 1 );
	}
	return sum; //函数返回sum的值。 
}
int main()
{
	int n;
	scanf("%d", &n);  //输入n 
	printf("%d! = %d\n", n, F(n)); 
	
	return 0;
}

这是一个很简单的递归程序，但是包含递归的要素：

1. 递归函数参数的设置与变化，如 sum = n * F(n - 1) 中的 n-1。在别的题中，我们要去找到那个递推公式，然后合理设置参数，就能很快的写出递归函数。
2. 递归终点的设置，如 if(n == 0 || n == 1) return 1; 就是很标准的递归终点。在写递归函数时，我们必须先想好函数的递归终点，然后才能写递归函数。
3. 函数的返回值，如本道题中的 return sum; 再别的题目中，要注意考虑到所有的情况，稍微复杂一点题目就很容易漏掉某种情况，然后没有返回值。
   同时补充一点函数的知识，在定义函数的时候，原则上函数的类型就是返回值的类型，但是如果类型不一样，会强制类型转换为定义函数地类型的值然后返回。

---

二 、贪吃的猴子。
觉得上面的例子很简单，那么就让我们看一道稍微难一点的递归题。

有一只猴子，第一天摘了若干个桃子 ，当即吃了一半，但还觉得不过瘾 ，就又多吃了一个。第2天早上又将剩下的桃子吃掉一半，还是觉得不过瘾，就又多吃了两个。以后每天早上都吃了前一天剩下的一半加天数个（例如，第5天吃了前一天剩下的一般加5个）。到第n天早上再想吃的时候，就只剩下一个桃子了。

输入：

天数n

输出：

第一天的桃子个数

提述：要先建立递推公式。

首先，就像我之前说的，明确我们写的递归函数是用来干嘛的，然后写出递推公式，明确递归终点，再写出递归函数。这道题就解决了。
那么，我们写的递归函数是用来干嘛的？根据题意，猴子每天吃掉前一天的一半加上天数个桃子。
所以我们写的递归函数就是计算第n天时剩余的桃子个数。然后建立递推公式：第 n 天剩余的桃子个数 =2*( 第 n+1 天剩余桃子数+ n )。
递归终点就是最后一天剩余桃子数为 1。然后我们就可以开始写递归函数了。

#include<stdio.h>

int n;   //定义全局变量n，记录输入天数 

int Taozi( int day ) //递归函数。 
{
	int num;
	if( day == n )
	{
		return 1; //递归终点。 
	}
	else
	{
		num = 2 * ( Taozi( day + 1 ) + day ); //递推公式 
	}	 
	return num; //返回num的值 
}
int main()
{
	int num; //此处num是局部变量，与递归函数中的num 意义不同 
	scanf("%d", &n);  //输入全局变量n的值 
	num = Taozi( 1 ); //因为是从第一天开始算，传入的参数值为 1。 
	if(num > 1)
	printf("The monkey got %d peaches in first day.\n", num);
	else
	printf("The monkey got %d peach in first day.\n", num);
}

这题因为递推公式不同会有很多写法，不一一列举。 参考上面的提示，好好想一下这个过程，以便更好的理解递归的思想。接下来我会在列举几道递归的题，你们可以好好的琢磨一下这个过程。

---

三 、求数列的前n项和。
请使用递归算法求下列序列的前n项之和。
1 + 1/2 - 1/3 + 1/4 -1/5 …

输入：
n

输出：
序列的前n项和（精确到小数点之后第6位）

像之前一样，我们来分析一下这个问题：我们写递归函数是用来干嘛的？这题很显然，是用来计算 1 / n 与 1 / (n - 1)的和，为什么是 n - 1 不是n + 1 ？ 其实都是可以的，只是所得到的递推公式不一样，递归终点不一样。而这题我们从后往前加，递推公式很容易得到，递归终点也较简单。所以递归终点就是 1 。
注意：奇数项和偶数项的符号不一样，我们需要判断一下。

#include <stdio.h>
#include <stdlib.h>
double plus(int x) // 这是一个返回值为浮点数的函数，写在后面的话要进行函数申明。
{
	double sum = 0;
	if(x == 1)  // 递归终点
	{
		return 1;
	}
	else
	{
		if(x % 2 == 0)  //当为偶数项时，符号为正
			sum = 1.0 / x + plus(x - 1);
		else  //当为奇数项时，符号为负（首项除外）
			sum = -1.0 / x + plus(x -1);
	}
	return sum;
}
int main()
{
	double sum = 0;
	int n = 0;
	scanf("%d", &n);
	sum = plus(n);
	if(sum != 1)
		printf("%06lf\n", sum);
	else
		printf("1\n");
	return 0;
}

四 、子串反向
请编写一个递归函数 reverse(char str[], int start, int end ) ，该函数的功能是将串 str 中下标从 start 开始到 end 结束的字符颠倒顺序。假设 start 和 end 都在合理的取值范围。

例如：

执行前：str[]=“0123456”；start=1 ；end=4

执行后：str[]=“0432156”

要求在该函数中没有循环。

分析：这题和之前的有些不一样，是对字符串操作的，那我们如何建立递推公式呢？
我们想，要从start到end调换，那么我们可以从两头向中间依次进行对调，那么递归的终点就是当指针相交或相等的时候，返回。
这样我们就可以实现字符串的对调。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void reverse(char *str, int start, int end) 
{
	int t;
	for(t = 0; str[t] != '\0'; t++); //计算字符串的长度
	//也可以 t = strlen(str);
	char temp; //中间变量
	if(end > t) 
	//当给的end超过字符串长度时，end直接变为t-1，end是下标所以减一
		end = t - 1;
	if(end <= start)
	{
		return; //递归终点
	}
	else
	{
		temp = str[start];
		str[start] = str[end];
		str[end] = temp;  //交换字符
		reverse(str, start + 1, end - 1); //递归调用
	}
	return;
}
int main( )
{	char str[100];
	int start, end;
	gets(str);
	scanf("%d %d", &start, &end);
	reverse( str, start, end );
	printf("%s\n", str);
	return 0;
}

这道题虽然和上面的不一样，但是所用的递归思想是一样的，写递归函数的方式也相同。只不过没有了参数。

五 、回文字符串。
有一种特殊形式的字符串，其正反序相同，被称为“回文字符串”。例如LeveL就是一个回文字符串。

输入：
字符串

输出：
Yes或者No

说明：
如输出Yes，说明输入的字符串是一个回文字符串
输出No，说明输入的字符串不是一个回文字符串
请使用递归算法实现。

这道题相比上面的那道题还要简单一点，如果看了上面的题你有所收获的话，那么这道题一定不在话下。
那我们来看看吧，这道题是一道判断题，判断是否为回文串。操作和上面那题基本类似，就是比较首位往中间相对应的字符是否相同。但是递归终点我们可以用另一种表示方法，就是当我们所判断的子字符串的长度为 0 或 1 时，结束递归。具体我们看代码。

#include<stdio.h>
#include<string.h>
int Huiwen( char *p , int n ) // n是代表字符串长度的参数
{
	if(n == 1 || n == 0)
		return 1;
	else
	{
		if( *p == *(p + n - 1) ) //判断对应位置的字符是否相同
		{
			return Huiwen( p + 1, n - 2 ); 
	//这里返回的是下一次调用的返回值，这样只有当所有对应字符相同时才返回 1。
		}
		else
			return 0;
	}
}
int main()
{
	char arr[10000] = {0};
	int n;
	gets( arr );
	n = strlen( arr );
	if( Huiwen( arr, n) )
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}

看完是不是觉得递归的写法多种多样？是的，不同的参数设置，不同的递推公式，不同的递归终点都会让写出来的递归程序不一样。但是里面所含的递归思想是一样的。明确那几点，写出一个递归程序其实很简单。
但是不要看到题就想用递归做，所有的递归算法都可以用非递归算法写出，多想想们也许会有不一样的解题方法。
递归其实并不难，就那几步而已！