离散数学中的递归函数

递归函数是指函数的值在任何一点都可以从函数在某些先前点的值计算出来的函数。例如，假设一个函数 f(k) = f(k-2) + f(k-3)，它定义在非负整数上。如果我们知道函数在 k = 0 和 k = 2 的值，我们也可以找到它在任何其他非负整数的值。换句话说，我们可以说递归函数是指一个函数使用它自己的先前点来确定后续项，从而形成一个项序列。在本文中，我们将通过一些例子来学习递归函数。

什么是递归？

递归是指一个递归过程重复自身的過程。递归是一种函数，它有一个或多个变量，通常通过一个特定的过程指定，该过程通过不断地将特定的关系应用于已知函数值来生成该函数的值。

在这里，我们将通过一个例子来理解递归。

假设你要爬楼梯从地面到一楼。要做到这一点，你必须一步一步地走。到达第二级台阶的唯一方法是先到达第一级台阶。假设你想去第三级台阶；你必须先上到第二级台阶。在这里，你可以清楚地看到重复的过程。你可以看到，随着每一个新的台阶，你都在将前一个台阶加进去，就像一个具有相同步距差的重复序列一样。这就是递归函数的实际概念。

第 2 级台阶： 第 1 级台阶 + 最低台阶。

第 3 级台阶： 第 2 级台阶 + 第 1 级台阶 + 最低台阶。

第 4 级台阶： 第 3 级台阶 + 第 2 级台阶 + 第 1 级台阶 + 最低台阶，依此类推。

一组自然数是递归函数的基本例子，它从一开始一直到无穷大，1, 2, 3, 4, 5, 6, 7, 8, 9,……无穷大。因此，自然数集表现了一个递归函数，因为你可以看到每一项之间都有一个公差 1；它表明下一项每次都通过前一项重复自身。

什么是递归定义的函数？

递归定义的函数包含两个部分。第一部分处理最小参数的定义，另一方面，第二部分处理第 n 项的定义。最小参数用 f(0) 或 f(1) 表示，而第 n 个参数用 f(n) 表示。

请看下面的例子。

假设有一个序列 4, 6, 8, 10

上述序列的显式公式为 f(n) = 2n + 2

上述序列的显式公式由以下给出

f(0) = 2

f(n) = f(n-1) + 2

现在，我们可以通过应用递归公式来获得序列项，如下所示：f(2) = f(1) + 2

f(2) = 6

f(0) = 2

f(1) = f(0) + 2

f(1) = 2 + 2 = 4

f(2) = f(1) + 2

f(2) = 4 + 2 = 6

f(3) = f(2) + 2

f(3) = 6 + 2 = 8

通过上述递归函数公式，我们可以确定下一项。

是什么使函数具有递归性？

使任何函数具有递归性都需要它本身的值来计算序列中的下一项。例如，如果你想计算给定序列的第 n 项，你首先需要知道前一项以及前两项。因此，你需要知道前一项才能确定序列是否递归或非递归。所以我们可以得出结论，如果函数需要前一项来确定序列中的下一项，那么该函数就被认为是递归函数。

递归函数公式

如果 a₁, a₂, a₃, a₄, a₅, a₆, ………a_n,……是许多集合或序列，那么递归公式将需要计算所有先前存在的项来计算 a_n 的值

a_n = a_n-1 + a₁

上述公式也可以定义为等差数列递归公式。你可以清楚地看到上述序列，这是一个等差数列，它包含第一项以及其他项，并且每项之间都有一个公差。公差是指你加或减的数字。

递归函数也可以定义为等比数列，其中数集或序列之间有一个公因子或公比。等比数列的公式如下：

a_n = a_n-1 * r

通常，递归函数定义为两部分。第一个是第一项及其公式的陈述，另一个是第一项及其与后续项相关规则的陈述。

如何写等差数列的递归公式

要写出等差数列的递归公式，请按照以下步骤操作：

步骤 1

第一步，你需要确保给定的序列是否为等差数列（为此，你需要相加或相减两个连续的项）。如果你得到相同的输出，那么该序列就被认为是等差数列。

步骤 2

现在，你需要找到给定序列的公差。

步骤 3

使用第一项制定递归公式，然后使用前一项和公差创建公式；这样你就会得到给定的结果

a_n = a_n-1 + d

现在，我们通过一个例子来理解给定的公式

假设 3, 5, 7, 9, 11 是给定的序列

在上面的例子中，你可以很容易地发现这是一个等差数列，因为序列中的每一项都增加了 2。所以，两项之间的公差是 2。我们知道递归序列的公式

a_n = a_n-1 + d

已知,

d = 2

a₁ = 3

所以，

a₂ = a_(2-1) + 2 = a₁ + 2 = 3 + 2 = 5

a₃ = a_(3-1) + 2 = a₂ + 2 = 5 + 2 = 7

a₄ = a_(4-1) + 2 = a₃ + 2 = 7 + 2 = 9

a₅ = a_(5-1) + 2 = a + 2 = 9 + 2 = 11，过程继续。

如何写等比数列的递归公式？

要写出等比数列的递归公式，请按照以下步骤操作：

步骤 1

第一步，你需要确保给定的序列是否为等比数列（为此，你需要将每一项乘以或除以一个数）。如果你从一项到下一项得到相同的输出，那么该序列就被认为是等比数列。

步骤 2

现在，你需要找到给定序列的公比。

步骤 3

使用第一项制定递归公式，然后使用前一项和公比创建公式；这样你就会得到给定的结果

a_n = r * a_n-1

现在，我们通过一个例子来理解给定的公式

假设 2, 8, 32, 128, ………是给定的序列

在上面的例子中，你可以很容易地发现这是一个等比数列，因为序列中的下一项是通过将前一项乘以 4 得到的。所以，两项之间的公比是 4。我们知道递归序列的公式

a_n = r * a_n-1

a_n = 4

a_n-1 = ？

已知,

r = 4

a₁ = 2

所以，

a₂ = a_(2-1) * 4 = a₁ + * 4 = 2 * 4 = 8

a₃ = a_(3-1) * 4 = a₂ * 4 = 8 * 4 = 32

a₄ = a_(4-1) * 4 = a₃ * 4 = 32 * 4 = 128，过程继续。

递归函数示例

示例 1

确定序列 4, 8, 16, 32, 64, 128, ……… 的递归公式？

解决方案

给定的序列 4, 8, 16, 32, 64, 128, ………

给定的序列是等比数列，因为如果我们乘以前一项，我们会得到后续的项。

为了确定给定序列的递归公式，我们需要以表格形式书写

因此，函数表示法中的递归公式由以下给出：

f(1) = 4, f(n) . f(n-1)

在下标表示法中，递归公式由以下给出：

a₁ = 4, a_n = 2. a_n-1