Common Lisp中的简单递归示例:

MYMAP对列表中的每个元素应用一个函数。

1)空列表没有元素，所以我们返回空列表-()和NIL都是空列表。

2)将函数应用到第一个列表，对列表的其余部分调用MYMAP(递归调用)，并将两个结果合并到一个新列表中。

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

让我们观察跟踪执行。在输入函数时，输出参数。在退出函数时，输出结果。对于每个递归调用，输出将按级别缩进。

这个例子对列表(1 2 3 4)中的每个数字调用SIN函数。

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

这是我们的结果:

(0.841471 0.9092975 0.14112002 -0.75680256)

递归函数就像弹簧，每次调用都要压缩一点。在每一步中，您将一些信息(当前上下文)放在堆栈上。当到达最后一步时，释放弹簧，立即收集所有值(上下文)!

不确定这个比喻是否有效…: -)

无论如何，除了经典的例子(阶乘是最糟糕的例子，因为它效率低，很容易被平化，Fibonacci, Hanoi…)，这些都有点人为(我很少，如果有的话，在实际编程案例中使用它们)，看看它真正被使用的地方是有趣的。

A very common case is to walk a tree (or a graph, but trees are more common, in general). For example, a folder hierarchy: to list the files, you iterate on them. If you find a sub-directory, the function listing the files call itself with the new folder as argument. When coming back from listing this new folder (and its sub-folders!), it resumes its context, to the next file (or folder). Another concrete case is when drawing a hierarchy of GUI components: it is common to have containers, like panes, to hold components which can be panes too, or compound components, etc. The painting routine calls recursively the paint function of each component, which calls the paint function of all the components it holds, etc.

不确定我是否很清楚，但我喜欢展示现实世界中教材的使用，因为这是我过去偶然发现的东西。

如果你想要一本很好地用简单的术语解释递归的书，可以看看Gödel，埃舍尔·巴赫:道格拉斯·霍夫施塔特的《永恒的金辫子》，特别是第五章。除了递归，它还能很好地以一种可理解的方式解释计算机科学和数学中的许多复杂概念，一个解释建立在另一个解释的基础上。如果你以前没有接触过这类概念，这可能是一本非常令人兴奋的书。

Ouch. I tried to figure out the Towers of Hanoi last year. The tricky thing about TOH is it's not a simple example of recursion - you have nested recursions which also change the roles of towers on each call. The only way I could get it to make sense was to literally visualize the movement of the rings in my mind's eye, and verbalize what the recursive call would be. I would start with a single ring, then two, then three. I actually ordered the game on the internet. It took me maybe two or three days of cracking my brains to get it.

我会用一个例子来解释。

你知道n!意味着什么?如果不是:http://en.wikipedia.org/wiki/Factorial

3! Is 1 times 2 times 3, which is 6

下面是一些伪代码

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

让我们试试吧:

factorial(3)

n是0吗?

no!

所以我们在递归中深入挖掘:

3 * factorial(3-1)

3 minus 1 is 2

2 == 0?

no!

所以我们要深入! 3 * 2 *阶乘(2-1) 2-1 = 1

1 == 0吗?

no!

所以我们要深入! 3 * 2 * 1 *阶乘(1-1) 1-1 = 0

0 == 0?

yes!

我们有一个小问题

所以我们有 3 * 2 * 1 * 1 = 6

我希望这对你有所帮助

递归

方法A调用方法A调用方法A，最终这些方法A中的一个不会调用并退出，但这是递归，因为有东西调用了它自己。

递归的例子，我想打印出硬盘驱动器上的每个文件夹名称:(在c#中)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}