C语言P3外传函数递归训练

• 函数的递归
• • 什么是递归
  • 递归的主要思想
  • 递归的两个必要条件
  • 递归与迭代的关系与选择
  • • 递归与迭代共同解斐波那契数列
  • 递归相关练习题
  • • 1.不创建临时变量求出字符串长度
    • 2.递归实现n的阶乘
    • 3.递归实现逆序字符串
    • 4.递归实现n的k次方（有优化版本已更新）
    • 5.青蛙跳台阶问题
    • 6.汉诺塔问题

关于递归其实很简单，函数在定义的时候间接或者直接调用自身，这就是递归。
递归可以吧复杂的大型问题，转化成简单的小型问题解决，层层抽丝一样的感觉。

递归的主要思想就是把大事化小

1.递归必须有明确的结束条件，满足该条件，递归就不再继续进行了。（要注意死递归的出现大部分情况都是递归结束条件不够明确）
2.每次递归都必须逐渐接近那个结束条件

这里涉及到一个新名词，迭代。
迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。（ 通俗的讲，迭代就是上一次计算的结果作为下一次计算的初始值。）

为了更好的理解迭代我们来看例题：求第n个斐波那契数列
思路是：如果是第三个及以上的斐波那契数就递归，他前两个数字之和。

//递归法求斐波那契数列
#include

int Fib(int n)
{
	if (n == 0)
	{
		return 0;
	}
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return Fib(n - 1) + Fib(n - 2);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int fibnum = Fib(n);
	printf("%d", fibnum);
	return 0;
}

要注意，在不考虑溢出的情况下我们计算第40个斐波那契数列，程序就需要等待好一会才能计算完毕，这效率显然不行，我们下面来看迭代法。

//迭代法求斐波那契数列
#include

int main()
{
	int n = 0;
	int a = 1;
	int b = 1;
	int c = 1;
	scanf("%d", &n);
	if (n == 0)
	{
		printf("0n");
	}
	else if (n <= 2)
	{
		printf("%d", c);
	}
	else 
	{
		while (n>2)
		{
			c = a + b;
			a = b;
			b = c;
			n--;
		}
		printf("%d", c);
	}
	return 0;
}

其实就是模拟实现strlen
思路就是每次进入函数判断这个字符是不是’’如果是就说明没有字符了，就可以return 0；如果不是就说明还有字符就需要继续递归。

上代码：

//递归求字符串长度
#include

int my_strlen(char* str)
{
	if (*str == '')
	{
		return 0;
	}
	else
	{
		return 1 + my_strlen(str + 1);
	}
}

int main()
{
	char arr[] = "Hello KissKernel!!!";
	int num = my_strlen(arr);

	printf("%d", num);

	return 0;
}

实现n的阶乘很简单，就是判断n是不是1，是的话就return 1；不是就继续递归n-1；

//递归实现n的阶乘
#include

int Fac(int n)
{
	if (n == 1)
		return 1;
	else
	{
		return n * Fac(n - 1);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int facnum = Fac(n);
	printf("%dn", facnum);

	return 0;
}

这里说的逆序是，将一个数组中的字符逆序，不是逆序打印哦
思路就是，用一个头指针和尾指针锁定字符串区间，每次递归交换两个指针的内容，直到头指针大于等于尾指针结束递归。

//递归实现逆序字符串
#include
#include
void reverse(char* first)
{
	int sz = strlen(first);
	static int n = 1;
	char* end = first + sz - n;
	if (first < end)
	{
		n++;
		reverse(first + 1);
	}
	char tmp = *first;
	*first = *end;
	*end = tmp;
}

int main()
{
	char arr[] = "Hello KissKernel!!!";
	printf("%sn", arr);//逆序前
	reverse(arr);
	printf("%sn", arr);//逆序后
	return 0;
}

这里设置的静态n是为了记录尾指针向前移动的数据，当然还有一种方法是进入函数直接逆序，将头字符保存起来，将尾字符置为’’,递归结束后在将头字符赋给尾字符；
代码如下：

//递归实现逆序字符串
#include
#include
void reverse(char* first)
{
	int sz = strlen(first);
	char* end = first + sz - 1;
	char tmp = *first;
	*first = *end;
	*end = '';
	if (*(first + 1) != '')
	{
		reverse(first + 1);
	}
	*end = tmp;
}

int main()
{
	char arr[] = "Hello KissKernel!!!";
	printf("%sn", arr);//逆序前
	reverse(arr);
	printf("%sn", arr);//逆序后
	return 0;
}

常规的递归求k次方，递归条件就是k不等于0就继续递归，k=0就return1；

#include

int Sqr2(int n, int k)
{
	if (k == 0)
	{
		return 1;
	}
	else
	{
		return n * Sqr2(n, k - 1);
	}


}
int Sqr(int n, int k)
{
	if (k == 0)
	{
		return 1;
	}
	else if(k%2 == 0)
	{
		return Sqr(n,k/2) * Sqr(n, k /2);
	}
	else
	{
		return n * Sqr(n, k - 1);
	}



}

int main()
{
	int n = 0;
	int k = 0;
	scanf("%d %d", &n, &k);
	int ret = Sqr(n, k);
	printf("%dn", ret);
	return 0;
}

优化方法，如果求得k次方为偶数，既可以转化为两个n的k/2次方的乘积；可以将时间复杂度从O（n）降低到O（logn）

问题描述：这里一共有n阶楼梯，青蛙可以一次跳一阶或者两阶，问总共有多少种跳法。
思路：如果剩下的台阶数是2，有两种走法，如果剩下1，就只有一种走法，大于2就可以递归了；

//青蛙跳台阶问题
#include

int Fun(int n)
{
	if (n > 2)
	{
		return Fun(n - 1) + Fun(n - 2);
	}
	else
		return n;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int num = Fun(n);
	printf("%d", num);
	return 0;
}

汉诺塔是递归的最经典问题了，下面我们来看一下；
问题描述：这里有三个柱子，a，b，c；a上面放着n个圆盘从下往上，圆盘依次变小。要求把a上的圆盘移动到c上，过程种小圆盘上面不能放置大圆盘，求最后的移动次数。
思想：要想移动n个圆盘到c，首先得先移动n-1个圆盘到b（这时候要借助与c柱子）然后将a上的第n个圆盘移动到c最后在借助a柱子将b上的n-1个圆盘移动到c上就行了。
同样的如果哟啊移动n-1个圆盘首先要移动n-2个圆盘，依此类推直到第一个圆盘。
这就构成了递归。

//汉诺塔问题

#include

int move = 0;

void Move(char n1, char n2)
{
	move++;
}

void Fmove(int n, char a, char b, char c)//将a上的圆盘借助从b移动到c
{
	if (n == 1)
	{
		Move(a, c);
	}
	else
	{
		Fmove(n - 1, a, c, b);//将a上的n-1个圆盘借助c移动到b；
		Move(a, c);//将a上的圆盘放到c上；
		Fmove(n - 1, b, a, c);//将b上的n-1个圆盘借助a移动到c上。至此移动结束
	}
}

int main()
{
	int n = 0;
	char a = 'A';
	char b = 'B';
	char c = 'C';
	scanf("%d", &n);
	Fmove(n, a, b, c);
	printf("%dn", move);

	return 0;
}