用函数的递归来解决几道有趣的题

一.前言

啊哈亲爱的小伙伴们，大家好啊！我回来了经过20多天的预习加复习我终于把这学期的考试给考完了，累死我了，那么在这个暑假期间我就可以正常的更新文章了，啊哈我们又可以继续一起进步了，那么废话不多说我们来看今天的内容，如何用函数的递归来解决问题。

二 .第一题

模拟实现strlen这个函数
首先我们来回想一下strlen这个函数的作用是什么？想必在看的小伙伴都应该知道,就是它能够帮助我们来求得一个字符串的长度，我们来看下面这段代码：

#include<stdio.h>
#include<string.h>
int main()
{
    
	char arr[] = "abcd";
	size_t len = 0;
	len = strlen(arr);
	printf("字符串的长度为：%zd", len);
	return 0;
}

我们再来看看这段代码的运行结果 ：

我们便可以看到这个函数的具体的作用，那么我们这里就提出了一个问题就是我们自己如何来模拟实现这个strlen函数？如果在不创建临时变量的条件下又如何来实现这个函数呢？我们首先来看第一个先简单的实现这个函数：首先我们想一下我们是通过数组的形式来存储字符串，那么既然是数组的话，我们是不是就可以通过数组名来得到这个数组的首元素的地址，而且我们还知道一个数组在创建的时候是在内存中申请的是一段连续的空间，那我们就可以根据第一个元素的地址然后过相对应的数字加减来得到数组中其他元素的地址，比如说下面这段代码

#include<stdio.h>
int main()
{
    
	int arr[10] = {
     1,2,3,4,5,6,7,8,9,10 };
	int a = 0;
	int i = 0;
	a = *arr;
	for (i = 0; i < 10; i++)
	{
    
		a = *arr + i;
		printf("%d\n", a);
	}
	return 0;
}

当然有些小伙伴们可能还没有学过数组方面的相关的内容，所以可能不是很能理解，大家不要担心哈，数组的文章很快就会来了，那么大家通过上面的代码便可以明白我们可以通过数组名加上n来得到数组中第n-1个位置的元素的地址，那么我们反回来看这道题，我们既然可以得到数组中每一个元素的地址，那么我们也就可以挨个进行解引用来得到这个这个地址所对应的内容，而且我们还知道一个字符串的结尾一定是\0，那我们这么想我们先创建一个变量count，然后我们就可以通过数组名得到首元素的地址并对其解引用，然后对其进行一次判断，判断它是否为\0,如果不是我们就将count和数组名进行++，因为我们数组的元素会有很多个，所以我们将其放到一个while循环里面并且我们将这个while循环的判断部分直接变成1，让他是一个死循环，这样我们就可以进行无限次的判断，如果是这样的话，我们是不是得有一个结束的标志，那么这个标志就是解引用判断内容为\0的时候，我们就可以用break来直接跳出这个循环，那么这时我们的count的值的大小就是我们这个字符串的长度，我们的代码如下：

#include<stdio.h>
int my_strlen(char* str)
{
    
	int count = 0;
	while (1)
	{
    
		if (*str != '\0')
		{
    
			str++;
			count++;
		}
		else
		{
    
			break;
		}
	}
	return count;
}
int main()
{
    
	char arr[] = "abcdefg";
	int len = 0;
	len = my_strlen(arr);
	printf("字符串的长度为：%d", len);
}

看到这里我们的代码就基本上实现了strlen的功能，那么这里大家再想一下，如果我们这里再加上一个条件说：不准创建零时变量，那又该如何来模拟实现这个函数呢？那么这里我们就可以往函数的递归这个方面来进行思考了。好我们这里可以先想一下函数递归的作用是什么，我们之前说过函数的递归他可以实现一个功能就是可以将一个复杂的问题进行层层的简化，最终就变成了一个简单的问题，那么我们这里就要想一下：我们这里是如何来简化的？简化到最终这个问题又是什么呢？好我们首先来解决这个问题如何来进行简化，我们还是先创建一个字符串我们假设这个字符串的内容就是char arr[]=“abcdefg”,我们要得到这个字符串的长度，那么我们就先进行一次简化，我们要求abcdefg的长度，我们可以将其简化成a的长度加上求bcdefg的长度，而我们又知道a的长度就是1啊，那么这里就简化成1+bcdefg的长度，而求bcdefg的长度又可以简化成1+求cdefg的长度，看到这里想必大家应该懂得了这个求解的规律，那么我们这里不停的简化不停的简化，简化的最终的结果是什么呢？是不是就是1+求‘\0’的长度，而我们\0的长度就是0，那么这里我们函数的简化就结束了，递归递归我们这里只是递的过程我们最后是不是得归啊！那么我们这里就可以用return将其归回去，如果*str != '\0'我们就return 1 + my_strlen(str+1);如果*str == '\0'我们就return 0；那么这里我们归就实现了我们可以看一下代码的具体实现：

#include<stdio.h>
int my_strlen(char* str)
{
    
	if (*str != '\0')
	{
    
		return 1 + my_strlen(str+1);\\注意这里写的是+1
	}
	else
	{
    
		return 0;
	}
}
int main()
{
    
	char arr[] = "abcdefg";
	int len = 0;
	len = my_strlen(arr);
	printf("字符串的长度为：%d", len);
	return 0;
}

这里大家注意一个点就是我们这里写的是str+1，大家不要写成++str这样的形式，因为前置++确实可以让他往后一位，但是前置++他也让str本身的值也发生了变化，大家注意一下哈。看到这里想必大家就知道了如何模拟实现这个函数，那么我们接着往下看。

三.第二题

求第n个斐波那契数列
首先我们来看一下斐波那契数列是什么？ 我们首先看这么一个数列1、1、2、3、5、8、13、21、34、……大家可以发现这么一个规律就是这个数列的第一个和第二个数字都是1，从第三个数字开始他的值就等于他前面两项数字的和，比如这里的数列第四位（3）他前两项分别为第2位（1）和第3位（2）所以第四位的值就为3， 那么我们这里如何来得到第20位的大小呢？那么这里我们就可以用到函数的递归这个方法，我们可以将其一步一步的简化，然后将其归一起来，比如说我们要求第20位的大小，而且我们又知道第20位的值是等于第19位加上第18位的，那么我们是不是就可以将计算第20位的大小简化成计算第18位的大小和第19位的大小并将其相加，而计算第18位的大小又可以将其简化位计算第16位的大小和第17位的大小并将其相加，而计算第19位的大小又可以将其简化为计算第18位和第17位的大小，而第16位和第17位是不是也可以接着进行简化，那么这么一步又一步的简化下去我们最终的结果就是简化到第一位和第二位进行相加，而这个第一位和第二位我们是知道的他就是1和1这样我们是不是就简化完成了，那么我们接下来所要作的是不是就是将其归起来，那我们这里直接将两个进行相加不就够了吗，我们，我们来看看代码的具体实现：

#include<stdio.h>
int count = 0;
int fib(int n)
{
    
	if (n <= 2)
	{
    
		return 1;
	}
	else
	{
    
		return fib(n - 1) + fib(n - 2);
	}
}
int main()
{
    
	int n = 30;
	int ret = fib(n);
	printf("第30位斐波那契数列的大小位%d\n", ret);
	return 0;
}

啊有小伙伴看到了这里可能立马动手尝试了起来将数据进行了修改把30改成了50，于是在运行的时候就发现了一个问题好像运行不出来这是为什么呢？因为我们电脑他是没有人性化的记忆能力的，我们人类再计算这种问题的时候会将一些经常要用的数据记住但是我们的计算机他是不会比如说我们刚刚计算出来第28位的斐波那契数列的大小我们人类就将他记下来了，等下次再用的时候肯能就直接写上去了，而不会再将他算一遍，但是计算机他不会记下来，他可能前一秒刚算出来第28位的大小下一秒要用的时候他就会重新算一遍这也是为什么我们在算第50位的斐波那契数列的时候半天没有结果的原因，因为我们这样的算法太浪费算力了，我们可以看看下面这个代码看看在计算第30位斐波那契数列的时候得计算多少边第三位斐波那契数列

#include<stdio.h>
int count = 0;
int fib(int n)
{
    
	if (n == 3)
	{
    
		count++;
	}
	if (n <= 2)
	{
    
		return 1;
	}
	else
	{
    
		return fib(n - 1) + fib(n - 2);
	}
}
int main()
{
    
	int n = 30;
	int ret = fib(n);
	printf("第30位斐波那契数列的大小位%d\n", ret);
	printf("计算第3位的次数为%d\n", count);
	return 0;
}

我们来看看计算结果：

是不是有种感觉就是计算机仿佛对你说了一句话就是虽然我不是人但是你是真的苟啊！这只是就算第3位的还有第4第5第六等等，所以这也就导致看似数据很小但是却计算不出来的原因，那么我们这里就要告诉大家一件事就是系统分给程序的栈空间是有限的，如果出现了死循环或者死递归的话，就可能导致一直开辟栈空间，最终导致产生的栈空间耗尽的情况，这样的现象我们就称为栈溢出，那么我们这里如何来将其进行改进呢？首先我们递归的方法肯定是行不通的了，那么我们还有什么办法呢？我们想一下是不是还有循环，那么我们这里如何将他和循环扯上关系呢？大家想一下我们首先创建三个变量a b c然后将a和b都等于1然后这个a就表示这个数列的中的第一位，b就表示这个数列的第二位，而c就表示这个数列的第三位，而c的值就等于a+b，如果我们要计算第四位值的话，我们就得将第三位和第二位的值加起来，那么我们就要先将b的值赋值给a，这时a就表示为数列中的第二位，然后将c的值赋值给b那么这个b就表示为数列中的第三位，那么我们就将c看成第四位所以他的值就变成a+b，那么这里大家就要想一个问题就是我们是先计算还是先赋值呢？因为我们这里的c一开始的值是为0的所以我们这里就要先计算再赋值，那么这里还剩下一个问题就是既然是循环那么循环的次数又是多少次呢？因为第一位和第二位的值我们是知道的，那么只要计算第三位包括第三位以上的大小时我们都要计算，那么我们这里就可以使用while循环，并且判断条件为n>=3，每次循环的末尾我们都让n的大小减去1，就ok了，那么我们的代码实现如下：

#include<stdio.h>
int fib(int n)
{
    
	int a = 1;
	int b = 1;
	int c = 0;
	while (n >= 3)
	{
    
		c = a + b;
		a = b;
		b = c;
		if (n == 3)
		{
    
			return c;
		}
		n--;
	}
	return 1;
}
int main()
{
    
	int n = 0;
	scanf_s("%d", &n);
	int ret = fib(n);
	printf("%d\n", ret);
	return 0;
}

四.第三个问题

汉诺塔问题
可能很多人还不知道这个问题是啥，那么这里我来给大家看几张图片大家就应该能够知道汉诺塔是啥了

大家可以看一下这就是我们的汉诺塔，我们所有的木块都是放到了最左边，然后他的放置情况是按照从小到大的顺序进行排序，那我们这时就要把所有的木块全部移动到最右边的杆上，并且在移动木块的过程中始终要保持一个规则就是每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。然后我们这里要解决的问题就是如果有n个从大到小的木块在最左边，如果我们要移动到最右边最少得需要多少步？好我们看到这个问题我们先一步一步的分析我们先来解决一个简单一点的问题就是，如果只有一个木块我们把他移动到中间杆子需要几步呢？答案很简单就一步，直接移过去就可以了，同样的道理移动到最右边也是一步，那如果有两个木块把他移动到最右边的杆子需要几步呢？

大家可以看到最少需要三步，那么我们把两个木块移动到最右边需要三步，那么同样的道理我们将他移动到中间的杆也需要三步，把这两个木块从中间杆移动到最右边的杆也需要三步，那么这里我们就可以来讨论三个木块的情况，如果我们要想将三个木块全部移动到最右边那我们就先将两个小的看成一个整体，先将这两个小的移动到中间的杆，那么这里就需要三步，然后再把最大的木块移动到最右边这里就又要一步，最后再把这个两个小的木块移动到最右边的杆，又是三步所以我们这里移动三个木块所需要的步数为7步
那我们就可以用同样的思想来想想有四个木块有需要多少步呢？我们先来总结一下这个想法是什么？就是先将除了最大的全部看成一个整体（a），再把最大的看成一个整体（b），这样之后我们所需要的步骤就可以全部简化为三步先将整体a移动到中间的杆，再将整体b移动到最右边的杆（这一步只需要一步），最后再将整体a移动的最右边的杆，而移动整体a的两次所需要的步数是一样的，这么看的话我们要求4个块所需要的步骤其实也就是先将最小的三块移动到中间的杆，再将最大的块移动到最右边的杆，最后再将最小的三个块从中间的杆移动的最右边的杆，这么看的话他需要的步骤就等于2*（移动三个块到其他的杆的步数）+1，那么同样的道理移动5个杆所需要的步骤就等于2*（移动四个块到其他的杆的步数）+1，这么看的话我们要移动n个块到最右边所需要的步骤就等于2*（移动n-1个块到其他杆的步数）+1，那么看到这里我们小伙伴应该能够知道如何用递归的方法来解决这个问题了，首先我们一步一步的简化这个问题，首先可以将移动n个块所需要的步骤简化为2*（移动n-1个块到其他杆所需要的步骤）+1，再将移动n-1个块到其他杆所需要的步骤简化成2*（移动n-2个块到其他杆所需要的步骤）+1，这么依次内推简化到最简单的问题是不是就变成了移动一个块到其他杆所需要的步骤，那是不是就是等于1啊，好看到这里我们的问题基本上就解决完了，我们来看具体的代码是如何实现的：

#include<stdio.h>
int han(int n)
{
    
	if (n > 1)
	{
    
		return 2 * han(n - 1) + 1;
	}
	else
	{
    
		return 1;
	}
}
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	int bu_zhou = 0;
	bu_zhou = han(n);
	printf("移动%d个块所需要的最少步骤是%d",n,bu_zhou);
	return 0;
}

五.第四个问题

青蛙跳台问题
这个问题是什么呢？就是说有一个蛤蟆它可以一下子跳一个台阶也可以一下跳两个台阶，然后我们这里有n个台阶问这个蛤蟆有多少种跳法？好我们这里是用递归的方法来解决这个问题，那么我们就得对这个问题进行简化，我们来看它是要跳n个台阶问有多少种跳法，那么我们这里可以将跳n个台阶进行简化一下因为它有两种跳法一个是跳一个台阶和一下子跳两个台阶，那么我们这里就可以将他进行简化，因为我们知道跳到n台阶的跳法其实是等于跳到n-1个台阶可能跳法加上跳到n-2个台阶的跳法，那我们要求跳到n个台阶的跳法可将其简化为求跳到n-1个台阶的可能跳法加上跳到n-2个台阶的可能跳法，那么n-1个台阶的跳法是不是又可以进行简化简化成n-2个台阶的跳法加上n-3个台阶的跳法，而n-2个台阶的跳法是不是又可以简化成n-3个台阶的跳法加上n-3个台阶的跳法，那么大家看到这里应该就知道这个简化的过程那么我们这里的最终简化结果是什么呢？就是简化成跳到第2个台阶的跳法加上第1个台阶的跳法，那么第二个台阶的跳法是不是就有两种啊对吧，两次跳一个台阶加上一次跳两个台阶，那么跳到第二台阶的跳法是不是就有两种，而跳到第一个台阶的跳法是不是就只能有一种对吧，我们简化的过程想好了，那么剩下来的是不是就是归的过程，那我们这就直接相加不就够了吗，好我们来看代码是如何实现的：

#include<stdio.h>
int tiao_tai(int n)
{
    
	if (n >= 3)
	{
    
		return tiao_tai(n - 1) + tiao_tai(n - 2);
	}
	else if (n == 2)
	{
    
		return 2;
	}
	else
	{
    
		return 1;
	}
}
int  main()
{
    
	int a = 0;
	int x = 0;
	scanf("%d", &a);
	x = tiao_tai(a);
	printf("跳到第 %d个台阶所需要的次数为 %d", a, x);
	return 0;
}

六.小结

想必看到这里小伙伴们应该能对函数的递归有了更加深刻的理解那么这里我们的文章就结束了，我们函数的递归其实有一个很鲜明的特点就是他好想但是他得以消耗很大的算力，比如说我们这里的斐波那契数列和青蛙跳台问题，所以以后大家写代码的时候要注意一下使用情况，那么这篇文章就到此结束了，谢谢阅读感谢大家支持。

点击此处获得本章代码