让我们以斐波那契数列(1,1,2,3,5,8,13,21…)的计算为例，数列中后一个数是两个数之和。给定一个数字N，我们想知道从1到N的序列中的所有数字，递归函数调用自身，进入循环运行，直至达到停机状态，即当数字N的值变为0；N=0或N=1是最终目的的判定标志。
long fibonacci(long N) {
if((N==0)|(N==1))
return number;
else
//recursion step
142
递归与偶然
①同上，第 297 页；另见威尔弗里德·西格(Wilfried Sieg)，《数学程序与数学经验》(Mechanical Procedures and Mathematical Experience)，见《数学与心灵》(Mathematics and Mind)，牛津：牛津大学出版社，1994年。
②索阿雷认为，“术语递归’不应再具有‘可计算性’或‘可判定性’的附加含义”。