北屋教程网

(十三) 函数递归

一、栈

在说函数递归的时候，顺便说一下栈的概念。

栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。

在编程的世界里，我们习惯用for和while循环来重复执行任务。但有一种方法，它让函数调用自身，像俄罗斯套娃一样，一层套着一层，以一种极其简洁和优雅的方式解决复杂问题。这种方法就是递归。它看似神奇，甚至有些违反直觉，但一旦理解其核心思想，你将会获得一件强大的思维武器。本文将带你揭开递归的神秘面纱，从概念到实践，彻底掌握它。