Scratch递归程序设计的教学探讨.pptxVIP

Scratch递归程序设计的教学探讨汇报人：2024-01-21

目录CONTENTS递归程序设计基本概念Scratch实现递归程序设计方法案例分析：经典递归问题求解学生思维能力培养与提升途径教学方法改进及策略探讨总结与展望

01CHAPTER递归程序设计基本概念

定义自我调用简化问题终止条件递归定义与特归是一种编程技巧，它允许函数直接或间接地调用自身，以简化复杂问题的求解。函数在执行过程中会调用自身。通过将大问题分解为与原问题相似但规模较小的小问题来求解。必须有一个或多个终止条件，以确保递归不会无限进行下去。

联系执行方式空间占用适用场景递归与迭代关系递归和迭代都是用于解决重复计算问题的方法，都可以用来描述计算机程序的执行过程。迭代通常使用固定的内存空间，而递归每次调用都会占用新的内存空间，因此空间占用较大。迭代是通过循环结构实现重复执行，而递归是通过函数自我调用实现。迭代适用于问题规模已知且固定的情况，而递归适用于问题规模不确定或需要分解为更小问题的情况。

阶乘问题计算一个数的阶乘，例如5!=5×4×3×2×15!=5×4×3×2×15!=5×4×3×2×1。生成斐波那契数列，其中每个数是前两个数的和，例如0,1,1,2,3,5,8,13,…0,1,1,2,3,5,8,13,ldots0,1,1,2,3,5,8,13,…。遍历树或图结构数据，如二叉树的先序、中序和后序遍历。将大问题分解为小问题求解，例如归并排序、快速排序等。通过将问题分解为重叠子问题并保存其解，以避免重复计算，例如背包问题、最长公共子序列等。斐波那契数列分治算法动态规划树的遍历常见递归问题类型

02CHAPTERScratch实现递归程序设计方法

递归函数设计与实现确定递归终止条件在设计递归函数时，首先需要明确递归的终止条件，即当满足何种条件时，递归将不再继续。递归调用自身在函数中，需要调用自身以实现递归。在Scratch中，可以通过在自定义积木中调用自身来实现递归调用。传递参数在递归调用中，需要将必要的参数传递给下一层递归，以便在递归过程中保持正确的状态。

使用变量监视器01Scratch提供了变量监视器功能，可以实时查看变量的值。在递归过程中，可以使用变量监视器来展示递归过程中的关键变量变化。绘制递归过程02可以使用Scratch的绘图功能，将递归过程绘制出来。例如，在解决分治问题时，可以绘制出每次递归调用的分割和合并过程。使用角色和背景03通过Scratch中的角色和背景功能，可以模拟递归过程中的状态变化。例如，在解决汉诺塔问题时，可以使用不同角色来代表不同的盘子，并通过移动角色来模拟盘子的移动过程。递归过程可视化展示

设置递归深度限制在Scratch中，可以通过设置自定义积木的递归深度限制来避免无限递归。当递归深度超过一定限制时，可以停止递归并给出相应提示。优化算法设计针对具体问题，可以优化算法设计以减少不必要的递归调用。例如，在解决某些问题时，可以使用迭代算法代替递归算法，从而避免无限递归的风险。使用尾递归优化尾递归是一种特殊的递归形式，其特点是在递归调用的最后一步进行调用，且调用后无需进行任何额外操作。在Scratch中，可以通过将递归函数设计为尾递归形式来优化性能并减少无限递归的风险。避免无限递归策略

03CHAPTER案例分析：经典递归问题求解

问题描述斐波那契数列是一个经典的递归问题，其定义为前两项为1，后续每一项为前两项之和。求解斐波那契数列的第n项。递归思路根据斐波那契数列的定义，我们可以将问题拆分为求前两项和后续项的递归过程。当n=1或2时，直接返回1；否则，返回前两项之和。递归实现在Scratch中，可以通过创建自定义积木块来实现递归求解斐波那契数列。首先创建一个名为“斐波那契数列”的积木块，并设置参数n。在积木块内部，使用条件判断语句来实现递归过程。斐波那契数列求解

问题描述汉诺塔问题是一个经典的递归问题，涉及三个柱子和多个大小不同的盘子。目标是将所有盘子从一个柱子移动到另一个柱子，并满足每次只能移动一个盘子且移动过程中必须保持盘子大小顺序。递归思路汉诺塔问题的递归思路是将问题拆分为更小的子问题。首先将除最底下的盘子外的所有盘子从起始柱子移动到辅助柱子，然后将最底下的盘子从起始柱子移动到目标柱子，最后将辅助柱子上的所有盘子移动到目标柱子。递归实现在Scratch中，可以通过创建自定义积木块来实现递归求解汉诺塔问题。首先创建一个名为“汉诺塔”的积木块，并设置参数起始柱子、目标柱子和辅助柱子。在积木块内部，使用递归调用自身来实现汉诺塔问题的求解过程。汉诺塔问题求解

树的遍历是计算机科学中的基本问题之一，涉及对树中所有节点的访问。常见的树遍历算法有先序遍历、