王笋 耿霞

摘要：递归是一种重要的程序设计方法，但在程序设计过程中一直是个难点。本文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中不仅介绍了递归程序设计的一般步骤和方法，还介绍了如何通过降阶、分治和回溯等策略进行递归程序设计。

关键词：递归；分治；回溯；汉诺塔问题；N皇后问题

引言

递归在程序设计基础、数据结构以及算法设计与分析等方面都占用重要地位，是一类重要的程序设计方法，但递归程序设计一直是个难点。程序设计过程通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。究其原因，一方面是通常只将递归作为一个概念进行简单介绍，对递归的执行过程以及递归程序设计的一般性步骤和方法描述过少；更重要的是缺少对递归程序设计方法系统性的概述。本文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法，还介绍了如何通过降阶、分治和回溯等策略进行递归程序设计。

1 什么是递归

简单来说，递归就是指函数或者过程在执行过程中直接或间接调用自身的现象。……