递归是程序在其中一个步骤涉及调用过程本身时所经历的过程。递归的过程被称为“递归过程”。

要理解递归，必须认识到一个过程和一个过程的运行之间的区别。程序是基于一组规则的一组步骤。程序的运行涉及实际遵循规则并执行步骤。类比：程序就像书面食谱;运行程序就像实际准备饭菜一样。

递归与执行某些其他过程的过程规范中的引用相关，但与之不同。例如，食谱可能指的是烹饪蔬菜，这是另一种程序，又需要加热水等等。然而，一个递归过程是（至少）其中一个步骤中的一个步骤需要一个相同过程的新实例，就像一个sourdough配方调用最后一次同一个配方所剩下的一些面团。这当然会立即产生无限循环的可能性;如果在某些情况下跳过有问题的步骤，则可以在定义中正确使用递归，因为该过程可以完成，就像一个sourdough配方，也告诉你如何获得一些起始面团，以防万一你从未做过。即使正确定义，递归过程对于人类来说也不容易，因为它需要区分新的与过程的（部分执行的）调用;这需要对各种同时进行的程序的实现进行一些管理。因此，递归定义在日常情况下非常罕见。一个例子可能是以下程序找到一条通过迷宫的方式。继续前进，直到到达出口或分支点（死端被认为是具有0个分支的分支点）。如果达到的点是退出，终止。否则反复尝试每个分支，递归地使用该过程;如果每次试验都没有达到死胡同，就返回到导致这个分支点的路径并报告失败。这是否实际上定义了终止程序取决于迷宫的性质：它不能允许循环。在任何情况下，执行该过程需要仔细记录所有当前探索的分支点，并且哪些分支已经被彻底地尝试。