C语言中递归的实际应用与经典问题

2024-04-02 19:04:59 532人浏览薄情痞子

摘要

目录一、什么是递归二、递归模板三、递归的实际应用1.阶乘递归2.斐波那契数列四、递归的经典问题汉诺塔问题青蛙跳台阶总结一、什么是递归递归简单的来说就是在函数中调用自己它通常把一

一、什么是递归

递归简单的来说就是在函数中调用自己

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的两个必要条件：

存在限制条件，当满足这个限制条件的时候，递归便不再继续。

每次递归调用之后越来越接近这个限制条件。

二、递归模板


void recursion(参数0) 
{
    if (终止条件)
    {
        return;
    }
    else
    {
        recursion(参数1)
    }
}

三、递归的实际应用

1.阶乘递归


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

2.斐波那契数列

斐波那契数列指的是这个数列从第3项开始，每一项都等于前两项之和。

递归算法：


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

非递归方法：


int fibonacci(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

四、递归的经典问题

汉诺塔问题

汉诺塔问题来源：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

这里我们使用的方法是从特殊到一般，这也是数学问题中常用的方法。

首先我们设计一个盘，那就直接把这个盘从自身柱子移到目标柱。

其次我们看两个盘，三根柱子两个盘，先将上面的柱子移动到中间柱，然后将最下面的柱子移动到目标柱，最后中间的柱子。

再来看多个盘


void hanno(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a, c);
	}
	else
	{
		hanno(n - 1, a, c, b);//递归处理,一开始的时候,先将n-1个盘子移至过渡柱z上后再将最底下的大盘子直接移至目标柱子y
		printf("%c->&c\n", a, c);
		hanno(n - 1, b, a, c);//然后重复以上步骤,递归处理放在过渡柱z上的n-1个盘子,
	}
}

青蛙跳台阶

一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:跳上第一级台阶只有一种跳法:直接跳 1 级即可。跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级.问要跳上第 n 级台阶有多少种跳法?

解题思路

我们设台阶数位N;

当N=1时，当然只有1种跳法；

当N=2时，青蛙可以跳2次1层和跳1次2层；

当N=3时，当有3层台阶时，青蛙可以选择先跳1层，剩下2层台阶，所以此时就是有2层台阶时的跳法，有2种；当青蛙选择第一次跳2层台阶时，剩下1层台阶，此时有1层台阶时的跳法，所以3层台阶时的方法是：2层台阶的方法 + 1层台阶的方法。


#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   return frog(n-1) + frog(n-2);
}
int main()
{
   int n;
   scanf("%d",&n);
   int ways = frog(n);
   printf("%d\n",ways);
   return 0;
}