c语言详解典型的递归问题---汉诺塔、青蛙跳台阶

清疚 2022-11-12 13:42 112阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、汉诺塔问题
 *   *   *   *  1.汉诺塔定义
             *  2.步骤实现图解
             *  3.实现代码解读
 *  一、青蛙跳台阶问题
 *   *   *   *  1.青蛙跳台阶定义
             *  2.步骤实现图解
             *  3.实现代码解读
 *  总结

--------------------

# 前言 #

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

--------------------

让我们一起来学习C中两个典型的递归问题吧！  
![在这里插入图片描述][20210324102445584.png]

# 一、汉诺塔问题 #

#### 1.汉诺塔定义 ####

> 汉诺塔问题是指：一块板上有三根木棒 A、B、C。A 针上套有 n个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这 n个圆盘从 A 针移动到 C 针上，每次只能移动一个圆盘，移动过程可以借助 B 针。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。从键盘输入需移动的圆盘个数，给出移动的过程。

#### 2.步骤实现图解 ####

![在这里插入图片描述][20210324103016255.gif_pic_center]

#### 3.实现代码解读 ####

![在这里插入图片描述][20210324103507368.gif_pic_center]  
**假设如上图4个盘子**  
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    void move(int n, char a, char b, char c)
    { 
    	if (n == 1)//只有一个盘子
    	{ 
    		printf("%c-->%c\n", a, c);//直接从a移动到c上
    	}
    	else
    	{ 
    		move(n - 1, a, c, b);//将n-1个元素从a通过c移动到b上
    		printf("%c-->%c\n", a, c);//将第n个元素从a移动到c上
    		move(n - 1, b, a, c);//将n-1个元素从b通过a移动到c上
    	}
    }
    
    int main()
    { 
    	int n = 0;
    	scanf("%d", &n);
    	move(n, 'a', 'b', 'c');
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]

# 一、青蛙跳台阶问题 #

#### 1.青蛙跳台阶定义 ####

> 一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

#### 2.步骤实现图解 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]

#### 3.实现代码解读 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][20210324110200605.png]  
我们可以看出当台阶数小于等于2时，跳法次数就是台阶数  
当台阶数大于3时，跳法次数就是前两个台阶数跳法相加  
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    int jump(int n)
    { 
    	if (n == 1 || n == 2)
    	{ 
    		return n;  //n==1时，有一种跳法，n==2时，有两种跳法
    	}
    	else          //n为3开始递归
    	{ 
    		return jump(n - 1) + jump(n - 2);
    	}
    }
    int main()
    { 
    	int n = 0;
    	printf("请输入跳的台阶数:>");
    	scanf("%d", &n);
    	int sum = jump(n);
    	printf("一共有%d种方法!\n",sum);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了两种常见的递归问题的描述和解决，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210324110813139.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/72f645b13dba475a9b1caeeda16b01b6.png
[20210324102445584.png]: /images/20221022/53866578ea234c9eb9d7430fa29299e6.png
[20210324103016255.gif_pic_center]: /images/20221022/2ffdc293aae04fdbbacde64c4e36e545.png
[20210324103507368.gif_pic_center]: /images/20221022/0394d1852e284dc79c985d42ef193d1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/f402facd7dba42de8b390deb08d61d39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/d9224d50e0c94d00b7f7993612fce1d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/dba13f2aa4b44ca38da0681aa2091c6c.png
[20210324110200605.png]: /images/20221022/d5504ba23cc44fdbad25f076fa467605.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/856cf10a97ac4bc48078537b54ddc8cf.png
[20210324110813139.png_pic_center]: /images/20221022/825ae98fa2394bf3aab2bf7ad054bda6.png