【函数递归】简单递归的5个经典例子，你都会吗？

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟🧸🧸🧸

今天和大家谈谈简单递归🥳🥳🥳

什么是递归

递归的定义：
递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。
也就是说说程序调用自身的编程技巧叫递归。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。

递归的重要思想就是大化小

递归最重要的就是需要避免死循环的出现和逻辑关系的正确性

递归经典例题

1.递归模拟实现库函数strlen

代码如下：

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

int main()
{
    
	char str[] = "abcdef";
	printf("%d",my_strlen(str));

	return 0;
}

需要注意的就是递归的截止条件

2.递归模拟实现字符串的逆置

代码如下：

#include <string.h>
int my_strlen(const char* str)
{
    
	if (*str == 0)
	{
    
		return 0;
	}
	else
	{
    
		return 1 + my_strlen(++str);
	}
}
void reverse_string(char*str)
{
    
	int len = my_strlen(str);
	char* temp = *str;
	*str = *(str + len - 1);
	*(str + len - 1) = 0;
	if (my_strlen(str + 1) >= 2)
		reverse_string(str+1);
	*(str + len - 1) = temp;
	//需要置换到后半部分的字符，每次递归都会创建一个temp存起来，
	//递归结束后开始回溯时才将他赋值给后半部分，因为首先要对后半
	//部分进行一个置'\0'
}

int main()
{
    
	char str[] = "abcdef";
	reverse_string(str);
	puts(str);
	return 0;
}

3.斐波那契数列的递归和非递归表示

代码如下：

}
int fib(int n)
{
    
	递归
	if (n == 1 || n == 2)
	{
    
		return 1;
	}
	else
	{
    
		return fib(n - 1) + fib(n - 2);
	}
	
	//因为斐波那契如果用递归的话效率太低了，所以用非递归
	//非递归
	int a = 1, b = 1, c = 1;
	while (n > 2)
	{
    
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}


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

4.递归青蛙跳台阶问题

代码如下：

//青蛙跳台阶
int JumpFloor(int n)
{
    
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
	{
    
		return JumpFloor(n - 1) + JumpFloor(n - 2);
	}
}
int main()
{
    	
	int n;
	scanf("%d",&n);
	printf("%d",JumpFloor(n));
	return 0;
}

5.递归汉诺塔问题

代码如下：

void move(pos1, pos2)
{
    
	printf("%c--->%c\n",pos1,pos2);
}

void hanio(int n,char pos1,char pos2,char pos3)
{
    
	if (n == 1)
	{
    
		printf("%c--->%c\n",pos1,pos3);

	}
	else
	{
    
		hanio(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		hanio(n - 1, pos2, pos1, pos3);
	}
	
}

int main()
{
    
	int n;
	scanf("%d",&n);
	char pos1 = 'A', pos2 = 'B', pos3 = 'C';
	hanio(n,pos1,pos2,pos3);

	return 0;
}

---

肺腑之言

今天的分享就到这里，以后还会持续不断的更新的！！谢谢大家的支持