：清华大学软件学院基本概念基于回溯策略的递归

从算法上（很难）如何找到递归形式？ 如何找到递归界限？ 如何编写递归程序？ 递归算法的类型 递归算法可以分为两类： 基于分而治之策略的递归算法； 基于回溯策略的递归算法。 基本概念 基于回溯策略的递归 基于分而治之策略的递归 11 分而治之的算法设计思想：：将问题划分为若干个子问题；：对待每个子问题中的每个子问题同样的方式；：将各个子问题的处理结果合并起来，形成最终的处理结果。 8.2.112 Call Call Call Call Call 14 如何编写基于分而治之策略的递归程序？ 在算法分析中，需要建立分而治之的递归思维方式。 在编程实现中，必须建立递归置信度(,,)。 15如何建立分而治之的递归思维方式？ 基本原则：目标驱动！ 计算n!: n! 递归形式 递归边界 16 call call fact(3)fact(2)fact(1)(("请输入一个整数：");scanf("%d",((1);(nfact (2)=2* fact(1)fact(3)=3*fact(2) call调用和的递归图 19 如何建立递归置信度？函数的递归调用是如何执行的？在递归调用过程中，它们是否执行相同的代码? 它们访问的是同一个数据吗？如果是的话，会不会互相干扰、互相阻碍？ 栈帧(("请输入一个整数：");scanf("%d",((1);(nfact's栈帧218.2.2 问题描述：给定一个整型数组a，求最大值。

如何设计相应的递归算法？ 22如何设计相应的递归算法？ 目标：max{a[0],a[n-1]}可以分解为：max{a[0],max{a[1],a[n-1]}}。 另外，已知 max{x} 是递归算法的递归形式和递归边界，基于它可以编写相应的递归函数。 (,;if(-1)[first];(a,first+1,a[first])[first];;Max(a,0,n) 调用 Max(a,1,n) 调用 Max( a , n-1, n) 248.2.3 问题描述：Find()：根据给定的值，判断一组数据（特别是数组）中是否存在具有相同值的数据元素。顺序查找， 25 前提：数据按顺序排列；基本思想：将目标值与数组中间元素进行比较，相等则查找成功，否则查找范围按下式缩小一半比较结果，然后重复这个过程，是在这个列表中吗？是在这个列表中吗？数组中间的元素。

问：这个名单上有吗？ 不考虑。 它在这个名单上吗？ 询问中间的元素：它在这个列表中吗？ 中间的元素不考虑吗？ (){05,13,​​19,21,37,56,64,75,80,88,92};int21;("x 位于数组的第 %d 个元素\n",(b, 如何使用递归实现？32函数原型：(int递归形式？递归边界？(;(-1); midb[mid]); elseb[mid]) (b, mid-1); (b, 348.2.4 传上在一座古印度寺庙里，有一个和尚整天把三根柱子上的金盘抛来扔去，原来他想把64块金盘，一个比一个小，从一根柱子搬到另一根柱子上。

移动时遵循以下规则：一次只允许移动一个磁盘，并且大磁盘不能落在小磁盘上（是不是很简单？如果每秒移动一个磁盘，则需要 5800 亿）年） 35 如何编写这样的程序？ 思维方面，我们先从最简单的情况开始分析，搬动一下，慢慢的理出思路。 1. A 列只有 1 个车牌，假设车牌号为 1，则只需将车牌直接从 A 移动到 C 即可，记为从 362 移动。 A 列有 2 个车牌，1 个就是小盘子。 二是市场。 分三步进行：373。A柱上有三块板，从小到大编号为1号、2号、3号。 如何移动？ 七步走！ 38 分三步进行：移动板块，从小到大，1号、2号、3号。 步骤：将1号、2号、……、n-1号板块作为一个整体，并在C的帮助下，从A移动到B； 步骤：然后将1号、2号、……、n-1号棋盘整体移动，并借助A从B移动到C； 这三个步骤记为： move n-1 个圆盘 from moven -1 个圆盘 从递归形式！ 40 定义函数 move(int 表示 move 1，即从谁开始移动？ 41 # stdio.h void move(int ( ("请输入一个整数：");scanf("%d", , , void move (int 43 请输入整数: 3 移动