杨勇

摘要：递归算法在程序设计的许多领域都有重要应用，为了写出思路清晰，逻辑严谨的递归函数，以分治策略为基础，归纳出组成递归函数的三大部分：提前终止条件，子问题分解，结果合并。并探讨了子问题分解的几种模式，研究了各种模式下递归函数的设计思路，为模式化构建递归函数找到可行途径。

关键词：递归;分治策略;子问题分解;回溯;栈区

中图分类号：TP311.11 文献标识码：A

文章编号：1009-3044（2020）01-0264-03

1背景

c语言程序由函数组成，通过函数之间的调用完成程序功能。如果函数在其执行语句中又调用自己，形成函数的递归调用。递归在数据结构和算法设计领域应用非常广泛，但函数递归调用一直是c语言学习和研究中的一个难点。对递归中函数调用顺序，函数返回值，递归终止条件有许多模糊的，错误的认识，不能正确地推理递归结果。对运用递归方法写出思路清晰，代码简洁的递归函数则更视为畏途。本文分析了递归过程系统底层运行机理，对编写递归函数的思路做了探讨和分析。

2递归调用系统底层运行机理

递归调用是一种特殊的函数嵌套调用。当一个函数中某个语句开始调用另外一个函数时，在操作系统底层上意味着当前正在运行的一段执行指令序列中途暂停，不往下执行，转而去执行另一段指令序列。执行完毕后，又回到原来执行序列的暂停位置处，从暂停位置开始继续往下执行。每一个函数被调用时，系统都将为其分配栈区空间，把函数形参和局部变量放在栈区空间里。……