当前位置: 首页 > news >正文

2.递归算法

递归算法的两个特点(很重要)

  1. 调用自身

  1. 要有结束条件

void func1(int x)
{printf("%d\n", x);func1(x - 1);
}

func1会一直死循环,没有使其结束的条件,所以不是递归

void func2(int x)
{if (x > 0){printf("%d\n", x);func2(x + 1);}
}

func2当传入的x > 0时,会一直死循环,此时没有使其结束的条件,所以不是递归

void func3(int x)
{if (x > 0){printf("%d\n", x);func3(x - 1);}
}

func3是递归,满足递归的两个特点,调用自身,有结束条件

输出结果为:3 2 1

void func4(int x)
{if (x > 0){func4(x - 1);printf("%d\n", x);}
}

func4是递归,满足递归的两个特点,调用自身,有结束条件

输出结果为:1 2 3

递归实例:汉诺塔问题

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

分析:

  1. 当A柱子只有1个盘子时

  1. A移动到B

  1. 当A柱子有2个盘子时

  1. A移动到C

  1. A移动到B

  1. C移动到A

  1. 当A柱子有n个盘子时,将A柱子中的第n个盘子看作一个整体,A柱子中的1, 2, ..., n-1看作一个整体

  1. hanoi(n - 1)从A移动到C

  1. A移动到B

  1. hanoi(n - 1)从C移动到B

源码:

#include <stdio.h>long long g_counter = 0;
void move(int n, char a, char b)
{g_counter++;printf("第%d次移动,将第%d个盘子从%c移动到%c\n", g_counter, n, a, b);
}
void hanoi(int n, char a, char b, char c)
{    if (n == 1){move(n, a, b);}else{hanoi(n-1, a, b, c);move(n, a, b);hanoi(n-1, c, a, b);}
}int main(int argc, char *argv[])
{int n = 3;printf("请输入汉诺塔的层数:\n");scanf("%d", &n);hanoi(n, 'A', 'B', 'C');return 0;
}

结果

ending😃

http://www.lryc.cn/news/24220.html

相关文章:

  • MySQL---触发器
  • PXC高可用集群(MySQL)
  • pytorch-把线性回归实现一下。原理到实现,python到pytorch
  • js中判断数组的方式有哪些?
  • 【2023unity游戏制作-mango的冒险】-5.攻击系统的简单实现
  • SpringMVC 面试题
  • 布局三八女王节,巧借小红书数据分析工具成功引爆618
  • RISCV学习(1)基本模型认识
  • 【java代码审计】命令注入
  • 速锐得适配北汽EX系列电动汽车CAN总线应用于公务分时租赁
  • 已解决ERROR: Failed building wheel for opencv-python-headless
  • 每日获取安全资讯的网站,国内外共120个
  • HUN工训中心:开关电路和按键信号抖动
  • WordPress 主题 SEO 标题相关函数和过滤器教程wp_get_document_title()
  • Qt 事件机制
  • 【Python】Numpy--np.linalg.eig()求对称矩阵的特征值和特征向量
  • 医疗床头卡(WIFI方案)
  • [YOLO] yolo博客笔记汇总(自用
  • Linux 常用 API 函数
  • 【转载】bootstrap自定义样式-bootstrap侧边导航栏的实现
  • 奇瑞x华为纯电智选车来了,新版ADS成本将大幅下降
  • 机器学习的特征归一化Normalization
  • 程序员看过都说好的资源网站,看看你都用过哪些?
  • Win11的两个实用技巧系列之设置系统还原点的方法、安全启动状态开启方法
  • 【Linux】项目的自动化构建-make/makefile
  • 【Redis学习2】Redis常用数据结构与应用场景
  • 踩了大坑:https 证书访问错乱
  • 大数据技术之Hive(四)分区表和分桶表、文件格式和压缩
  • 环形缓冲区(c语言)
  • 创建自助服务知识库的指南