明确一点，我并不是指在给定序列中的最后两个数字后提供下一个数字：
(2, 3, -> 5)而是指在给定任何索引后提供对应的斐波那契数：
(0 -> 1) 或 (7 -> 21) 或 (11 -> 144) 对于任何机器学习结构来说，添加两个数字是一项非常简单的任务，进而按一、二或任何固定数字进行计数也只是一个简单的加法规则。然而，递归计算…
据我所知，大多数学习网络依赖于仅向前评估，而大多数编程语言则具有循环、跳转或循环流模式（这些通常是某种形式的汇编跳转），从而允许递归。
当然，有些网络不仅仅是向前；但使用双曲正切或S形函数处理权重能否进入任何计算上完整的状态呢？
例如，条件语句、条件跳转、强制跳转、简单循环、具有多个条件的复杂循环、提供排序顺序、实际重新排序元素、赋值、分配额外寄存器等？
似乎即使是非仅向前的网络也只能找到最佳拟合的多项式，减少训练集范围内的误差，仅此而已。
我是否遗漏了什么显而易见的东西，还是大多数机器学习只是看到了递归并假装这些问题不存在？
更新
从技术上讲，任何编程语言都可以被视为遗传算法的DNA，其中编译器（可能还有控制台输出测量）将是适应度函数。问题在于，编程（到目前为止）无法以爬山的方式表达——字面上，适应度为0，直到适应度为1。编程中的事情不会半途而废，如果它们确实如此，也无法测量程序在未知情况下的“工作”程度。即使是一个偏差一的错误也可能看起来是一个完全不同且混乱的系统，没有任何输出。这正是学习编程如此困难的原因，学习曲线几乎是垂直的。
有些人可能会争辩说，你只需要为系统提供更强的基础规则来利用——但这只会导致试图概括所有编程问题，这又回到了设计编程语言，并失去了所有关于某种学习机器的概念。沿着这条路走下去，你会得到一个与LISP相近的变体，具有可变代码和几乎毫无意义的适应度函数，这些函数试图通过蛮力来遵循人类编码最佳实践，探索“美观”和“简单”的代码空间。
其他人可能会争辩说，我们只是没有使用足够的种群或动量来在错误表面获得立足点，或者迈向解决方案的有意义的一步。但当你的种群接近DNA排列的数量时，你实际上只是在蛮力（而且非常低效）。蛮力代码排列并不是什么新鲜事，绝对不是机器学习——这在正则表达式高尔夫球中相当常见，我认为甚至有一个xkcd关于这个…
真正的问题不是找到适用于某个特定递归函数的解决方案，而是找到一个能够以某种有用方式涵盖递归领域的解决方案空间。
那么，除了使用反向传播训练的神经网络假设性地找到递归函数的闭合形式（如果存在闭合形式的话，而在大多数递归有用的实际情况下并不存在），或者一个非仅向前的网络像一个伪编程语言一样运行，具有最佳情况下糟糕的适应度前景，再加上调整退出约束以防止无限递归的几乎不可能的任务…这就是目前机器学习和递归的全部了吗？
回答：
好吧，从哪里开始…
首先，你谈到了“机器学习”和“完美模拟”。这通常不是机器学习算法的目的。它们在给定一些证据和一些关于世界中存在的结构的一般概念的情况下做出有根据的猜测。这通常意味着一个近似答案比一个“精确”但错误的答案更好。所以，不，大多数现有的机器学习方法并不是回答你问题的好工具。
其次，你将“递归结构”视为某种灵丹妙药。然而，它们只是表示函数的方便方式，有点类似于高阶微分方程。由于它们引入的反馈，这些函数往往是非线性的。一些机器学习方法会对此感到困扰，但许多（例如神经网络）应该能够在给定足够的证据的情况下很好地近似你的函数。
顺便说一下，这里是否有闭合形式的解并不重要。重要的是手头函数与机器学习算法中体现的假设的契合程度。这种关系可能很复杂（例如，尝试用支持向量机近似斐波那契），但这就是本质。
现在，如果你想要一个专门用于搜索递归结构精确表示的机器学习算法，你可以设定一些假设，让你的算法产生最可能的“精确”递归结构来拟合你的数据。可能在现实世界中存在这样的问题是有用的。实际上，优化领域接近于解决类似的问题。
其他答案中提到的遗传算法可能就是这种情况的一个例子，特别是如果你提供了一个与你认为可能处理的递归函数相匹配的“基因组”。如果您认为闭合形式的原语比更复杂的遗传生成算法更可能“精确”，它们也可以构成该空间的一部分。
关于你声称编程无法以爬山的方式表达，这并不妨碍学习算法通过它能够重现多少你的证据以及它们的复杂程度来评分可能的解决方案。在许多情况下（大多数？尽管在这里计数案例实际上是不可能的），这种方法会找到正确的答案。当然，你可以想出病态情况，但对于那些情况，反正也没什么希望。
总结一下，机器学习算法通常不是设计来解决寻找“精确”解决方案的问题，所以它们本身并不是合适的工具。但是，通过嵌入一些关于精确解决方案是最好的假设，以及你所追求的精确解决方案的类型，你可能会用遗传算法做得很好，可能也适用于像支持向量机这样的算法。
我认为你也很好地总结了这一点：
真正的问题不是找到适用于某个特定递归函数的解决方案，而是找到一个能够以某种有用方式涵盖递归领域的解决方案空间。
其他答案在很大程度上告诉你了当前的技术状态。如果你想要更多，前方有一条明亮的新研究道路！
