学习笔记，递归函数

1.递归和非递归分别实现求第n个斐波那契数。

非递归：
int main()
{
	int i = 1;
	int j = 1;
	int n = 7;
	for (int k =1;k<=(n/2);k++)
	{
		i = i + j;
		j = i + j;
	}
	printf("第%d个斐波那契数为",n);
	if (n % 2 == 1)
		printf("%dn", i);
	else
		printf("%dn", j);

	return 0;
}

递归：
int Fbnq(int n)
{
	if (n > 2)
		return Fbnq(n - 1) + Fbnq(n - 2);
	else
		return 1;
}

int main()
{
	int ret = 0;
	int n = 7;
	ret = Fbnq(n);
	printf("%d", ret);

	return 0;
}

2.编写一个函数实现n^k，使用递归实现

//计算n^k
int function1(int n, int k)
{
	int ret = 1;
	int i = 1;
	for (i = 1; i <= k; i++)
	{
		ret *= n;
	}
	return ret;
}
int function2(int n, int k)
{
	int ret = n;
	if (k > 1)
		ret = n * function2(n, k - 1);
		return ret;
}
int main()
{
	int ret1 = 0;
	int ret2 = 0;
	int n = 0;
	int k = 0;
	printf("请输入n和k：");
	scanf("%d%d", &n, &k);
	//非递归
	ret1 = function1(n, k);
	//递归
	ret2 = function2(n, k);
	printf("%d %d", ret1, ret2);
	return 0;
}

 3、 编写一个函数 reverse_string(char * string)（递归实现）
实现：将参数字符串中的字符反向排列。
要求：不能使用C函数库中的字符串操作函数。

具体步骤：

//求字符串长度
//第一步  把left上的元素备份到tmp
//第二步  把right上的元素拿到left上
//            先不要把tmp中放到right上，先放一个''
//第三步 递归，把中间的元素再拿去逆序
//最后     再把tmp中的元素放在right上

4、#include
int my_strlen(char* str)//计算字符串长度三种方法：计数器、指针减指针、递归
{
	int count = 0;
	while (*str != '')
	{
		count++;
		str++;
	}
	return count;
}
void reverse_string(char arr[])
{
	int left = 0;
	int right = my_strlen(arr) - 1;//求字符串长度
	int tmp = arr[left];           //第一步 把left上的元素备份到tmp
	arr[left] = arr[right];        //第二步 把right上的元素拿到left上
	arr[right] = '';             //       先不要把tmp中放到right上，先放一个''
	if(my_strlen(arr+1)>=2)
		reverse_string(arr + 1);   //第三步 递归，把中间的元素再拿去逆序
	arr[right] = tmp;              //最后   再把tmp中的元素放在right上
}
int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);
	printf("%sn", arr);
	return 0;
}