Arduino安全递归调用

乐万德， 刘舟洲， 曹敬馨， 初建杰

（1.西安航空学院计算机学院，西安710077；2.西北工业大学工业设计与人机功效工信部重点实验室，西安710072）

0 引 言

作为一款便捷灵活的开源电子原型平台，Arduino得到了广泛的应用，比如汽车并线辅助系统［1］、智能防盗系统［2］，制作机械书画手臂［3］、智能盆栽养护瓶［4］等。Arduino在高校创新创业教育中也发挥着越来越重要的作用，不仅用于案例教学［5］，参与竞赛活动［6］，还用于实验调试［7］、实验室管理［8］等，也有学者研究其生态扩充［9］。

递归算法在数学和计算机领域都占据着十分重要的地位。在计算机领域，递归函数由于邱奇-图灵定理显示出重要意义［10］，邱奇-图灵论题告诉我们一切可计算过程都可以用图灵机模拟，1935年丘奇论题提出著名的“算法可计算函数都是递归函数”。同时递归函数是C语言等计算机编程中的一个重点和难点，国内外对于递归函数的教学进行了广泛的研究。Rinderknecht［11］在广泛研究递归在编程语言中出现及被程序员采用的历史之后，提出了递归的课程方法。文献［12-14］中对C语言中递归函数的教学方法、教学设计、微课等教学形式进行了探讨。

与某些单片机有限支持甚至不支持递归调用不同，Arduino支持递归调用。而前述文献虽然分别对于Arduino与递归进行了广泛的研究，但Arduino内存有限，递归算法在Arduio系统中栈溢出隐患问题鲜有研究。本文旨在探索Arduino安全递归调用，以期进一步释放Arduino应用潜能。

1 实验环境

本文实验硬件为目前广泛应用的Arduino UNO R3。作为Arduino平台的参考标准模板，UNO的处理器核心ATmega328，具有14路数字输入／输出口（其中6路可作为PWM输出）、6路模拟输入、SRAM 2 KB［15］。Arduino板通过USB与笔记本电脑相连。软件开发平台为Arduino IDE 1.8.9。

2 问题引入

在Arduino IDE输入图1所示代码，编译、下载到Arduino UNO后，在PC端打开串口监视窗口。

图1 不安全的Arduino递归调用

如图1（a）所示，在串口监视窗口可以看到，在Arduino UNO里用递归调用算法可以求出sum（1，2，…，500）的正确结果为125 250，没有发生栈溢出。

作为对比，把上面的代码稍作修改，即把上面else分支中return n＋sum（n－1）语句改为：

unsigned long temp＝sum（n－1）；

return n＋temp；

重新编译、下载，在图1（b）中串口监视窗口中显示异常，没有得到期望的结果，显然发生了递归栈溢出。

由此可见，Arduino UNO在编译时对递归调用在某些场景做了优化，使递归调用栈可以重复利用，从而避免栈溢出，但不是所有递归都进行了优化。因此，有必要对Arduino递归调用进行研究，以便对Arduino进行安全递归调用。

3 安全递归实验设计

安全递归调用要解决两个基本问题，一是要设计出正确的递归算法；二是要防止递归调用栈溢出。

3.1 递归算法

递归算法具有两个明显的特点：①一个更大规模的问题可以转换成一个规模更小的同样问题的求解，即问题的递推性。②当一个问题转换到某个规模足够小的问题时有确定的解，即问题的收敛性，也即递推终止条件。

以阶乘为例，要求n！，可以把问题转换成n*（n－1）！，即只需要求出（n－1）！这就是递推关系，即特点一。递推到足够小比如1！为1是确定的，第2个特点即递归终止条件满足。

一旦识别出上述两个特点，不难编写出递归程序，通常只需要将上述两个条件映射为递归程序判断结构的两个分支。

3.2 递归栈溢出

递归算法需要注意的第2个问题是递归栈溢出的问题，即本文研究的重点。递归调用本质上是函数调用，涉及到函数参数及函数返回地址等压栈。递归调用层数过多，栈地址与堆地址就会发生碰撞，也叫栈溢出。栈溢出会导致程序工作异常，需要避免。Arduino UNO的RAM内存空间只有2 KB，在掌握递归算法的基础上，更要关注递归栈溢出问题。

3.3 实验原理

3.3.1 AVR递归调用栈

Arduino UNO采用AVR ATMega328作为芯片平台。AVR芯片的SRAM存储示意图如图2所示。主要包括静态数据区、堆空间和栈空间。其中静态数据区和堆空间占据着低地址空间，且自下而上生长。而栈空间占据着高地址空间，且自上而下生长，主要应用于快速便捷地保存临时数据、局部变量和中断调用或子程序调用的返回地址。栈在系统程序的设计和运行中起着非常重要的作用，只要程序中使用了中断和子程序调用，就必须在SRAM空间建立栈空间，并正确地设置栈指针寄存器SP。

图2 Arduino SRAM中的存储示意图

当执行PUSH指令，1 byte的数据被压入栈，栈指针（SP中的数据）将自动减1；当执行子程序调用指令CALL或CPU响应中断时，硬件会自动把返回地址（16位数据）压入栈中，同时将栈指针自动减2；反之，当执行POP指令，从栈顶部弹出1 byte的数据，栈指针将自动加1；当执行从子程序返回或从中断返回指令时，返回地址将从栈顶部弹出，栈指针自动加2。

由于AVR的栈是向下增长的，即新数据进入栈时栈顶指针的数据将减小，所以随着栈空间和堆空间的增长，剩余内存会不断减小，甚至内存耗尽，发生栈溢出。

3.3.2 安全递归调用算法

如果在每次递归调用之前都能清楚地知道剩余内存的情况和本次递归调用所需内存，就可以有效防止内存耗尽及栈溢出情况。关于Arduino剩余动态内存的查看，可参考文献［16］，本文采用图3所示的算法来探测并规避递归调用栈溢出。

图3 Arduino剩余内存探测

图3所示的算法实现为函数，命名为availableMemory。在程序研发或者debug过程中，将availableMemory函数置于递归函数中，如果递归调用深度过深，内存可能耗尽，availableMemory返回的内存就会接近0。当剩余内存小于单次递归调用所需的内存，则告警并记录递归调用最大深度后安全返回。

Arduino安全递归调用算法如图4所示。在算法中设置一个递归调用状态参数State，初始化State为1，表示递归状态正常。每次递归调用时通过availableMemory计算剩余内存，如果剩余内存小于预设阈值，则将State变量设置为0，表示递归有栈溢出风险，即递归状态异常。每次递归调用时先查看State，只有当State为1才进行进一步的包括递归调用在内的后续操作，这样就妥善处理了栈溢出异常。最小阈值M1可以设置为每次递归调用需要消耗的内存。因为每次递归调用的压栈过程都是从高地址向低地址顺序压栈的，对于单次递归调用所消耗的内存M1，可以就两次递归调用同一个变量的内存地址相减得到。

图4 Arduino安全递归调用算法流程图

4 Arduino典型递归实验

4.1 Arduino阶加递归实验

常见的入门递归实例是求阶乘，随着n的增加，阶乘的结果迅速变大，容易造成存放其结果的数据类型越界。为了实验Arduino的递归支持能力，本文将乘改为加，设计了一个用递归算法实现从1～n求和的递归程序，称之为阶加。阶加的递推公式及终止条件如下：

阶加的递归调用算法与阶乘的递归调用算法类似，以n＝4为例，其递归调用栈入栈出栈如图5所示。递归算法中，recSum（4）需要做函数调用，其参数及函数返回地址入栈，同理recSum（3）、recSum（2）、recSum（1）也需做递归调用并依次入栈，此时入栈全部结束，递归调用栈如图5（a）所示。

图5 n为4时阶加递归调用栈分析

recSum（1）＝1为递归终止条件，函数返回并出栈，此时recSum（2）＝2＋1也为已知，recSum（2）函数返回并出栈，同理recSum（3），recSum（4）依次返回并出栈，此时栈空间为空，如图5（b）所示。

由图5可见，如果参数n足够大，recSum（n）递归调用时可能发生栈溢出。此时应该结束递归调用安全返回，并给出递归调用的最大深度提示。

用本文安全递归调用算法运行结果如图6所示。图6（a）是参数为300时程序运行的部分结果，当n逐层递归减到90时，剩余内存为15 bytes，本次递归调用后剩余内存已经不能继续进行本次递归调用了，给出错误提示，并给出根据本次计算得到的最大递归深度为211。图6（b）为按提示的最大递归深度211，计算1＋2＋…＋211的结果为22 366，计算结果正确。

图6 阶加Arduino安全递归调用运行结果

4.2 Arduino斐波那契数列递归实验

斐波那契数列又称黄金分割数列、兔子数列，由数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）提出，具有很多有趣的性质和应用。其递推公式可由下式表示：

与阶加相比，斐波那契数列递归算法略显复杂。主要的不同是，第n项的值不仅仅与第n－1项有关，还与第n－2项有关。其递归调用栈的入栈、出栈的关系也更为复杂。以4项斐波那契为例，对应式（2）的递归调用的出栈入栈如图7所示，更多项数的出栈入栈关系类似。

图7（a）中为了求Fib（4），需要进行递归调用，所以需要将参数n＝4及其函数返回地址入栈，同理当n＝3，n＝2时继续递归调用并将对应参数和函数返回地址压栈，因为Fib（2）＝1为已知，可以直接返回，第1轮压栈结束。图7（b）中Fib（2）返回弹栈后Fib（3）＝1＋Fib（1），Fib（3）不能继续弹栈，第1轮弹栈结束。图7（c）、（d），图7（e）、（f）分别进行第2、第3轮入栈出栈，分析类似，不再赘述。

图7 n为4时斐波那契递归调用栈分析

由图7可以看出，如果参数n足够大，在某轮入栈时，可能发生栈溢出，此时应该结束递归调用返回，并给出递归调用的最大深度提示。

用本文安全递归调用算法运行结果如图8所示。图8（a）是参数为300时程序运行的部分结果，当n逐层递归减到161时，剩余内存为23 bytes，本次递归调用后剩余内存已经不能继续进行本次递归调用了，给出错误提示，并给出根据本次计算得到的最大递归深度为140。图8（b）为按提示的最大递归深度140，递归调用正常。

图8 斐波那契Arduino安全递归调用运行结果

4.3 Arduino汉诺塔递归实验

汉诺塔问题是递归算法处理的经典问题。其问题可以描述为：初始状态下A座上有n个盘子，盘子大小不等，大的在下，小的在上。要求把这n个盘子从A座移到C座，但规定每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。

这是一个非数值解问题，也蕴含着递推关系，虽然不容易用递推公式，但可用下面的流程图来表达这种递推关系。Hannoi（n，x，y，z）中n为盘子的数量，x、y、z为座子变量，取值可能为A、B、C座中的一个。表示将n个盘子从x座移动到z座上，y座可以作为中转。当盘子的数量n＞1时，需要将n－1个盘子先从x座移到y座上（通过z座中转），然后将x座上剩余的一个盘子移动到z座上，最后将n－1个盘子从y座移到z座上（通过x座中转）。如果n＝1，则满足递归终止条件，直接将这1个盘子从x座移到z座上。

由图9可见，汉诺塔的递归调用从n阶到n－1阶的过程中具有两次递归调用，因此其入栈出栈也比较复杂，以3个盘子的汉诺塔递归调用为例，分析其入栈出栈关系如图10所示。更多项数的出栈入栈关系类似。

图9 汉诺塔递归调用算法

图10 n为3时汉诺塔递归调用栈分析

用本文安全递归调用算法运行结果如图11所示。图11（a）为参数为300时程序运行的部分结果，当n逐层递归减到148时，剩余内存为16 bytes，本次递归调用后剩余内存已经不能继续进行本次递归调用了，给出错误提示，并给出根据本次计算得到的最大递归深度为153。图11（b）为按提示的最大递归深度153，递归调用正常。

图11 汉诺塔Arduino安全递归调用运行结果

5 结 语

为了防止递归调用栈溢出带来的灾难性后果，本文为Arduino递归调用设计了防溢出的递归调用算法。无论是在简单阶乘（阶加）递归调用，还是在相对复杂的斐波那契数列、汉诺塔递归调用中，算法都稳定可靠。在Arduino实践中，为安全递归调用提供了保障，为Arduino创新应用提供更丰富的手段。