离散数学/递归

在本节中，我们将探讨一些数学过程，这些过程的核心是递归的基本性质。

什么是递归？

简单来说，递归就是用自身来描述一个动作的过程。这可能听起来有点奇怪，但一旦你理解了，它就是一种表达某些概念的极其强大的方法。

让我们看一些例子，让事情更清晰。

指数

当我们计算一个指数，比如x³时，我们将x自乘三次。如果我们有x⁵，我们将x自乘五次。

然而，如果我们想要指数的递归定义，我们需要用自身来定义取指数的操作。因此我们注意到，例如x⁴与x³ × x相同。但什么是x³？x³与x² × x相同。我们可以继续以这种方式进行，直到x⁰=1。那么我们一般能说些什么呢？递归地，

xⁿ = x × (x^n-1)

以及

x⁰=1

我们需要第二个事实，因为如果我们继续使用负指数，定义将不再有意义，我们将无限地继续下去！

递归定义

将问题简化为相同问题，但输入更小。例如

            a power n
            2 power 4
   the recursion(smaller inputs) of this function is = 2.2.2.2.1
   for this we declare some recursive definitions 
  a=2
  n=4
  f(0)=1
  f(1)=2
  f(2)=2
  f(3)=2
  f(4)=2
  for this recursion we form a formula f(n)= a.f(n-1)
  by putting these smaller values we get the same answer.

递推关系

在数学中，我们可以创建递归函数，这些函数依赖于其先前的值来创建新的值。我们通常称这些为递推关系。

例如，我们可以有函数 :f(x)=2f(x-1)，其中f(1)=1。如果我们计算一些f的值，我们会得到

1, 2, 4, 8, 16, ...

然而，这个数字序列对你来说应该很熟悉！这些值与函数2^x相同，其中x = 0、1，依此类推。

我们所做的是找到一个非递归函数，该函数与递归函数具有相同的数值。我们称之为求解，也称为x'to sup，其值为0，依此类推。

线性递推关系

我们将特别关注一种被称为线性的递推关系。

这是一个线性递推关系的例子

f(x)=3f(x-1)+12f(x-2)，其中f(0)=1，f(1)=1

我们通常使用a_n表示a(n)，而不是写f(x)，但这些表示法是完全可以互换的。

注意，线性递推关系应该始终有终止情况，否则我们将无法计算f(2)，例如，因为如果我们没有定义f(1)，它将是什么呢？当我们谈论线性递推关系时，这些终止情况被称为初始条件。

一般来说，线性递推关系的形式为

a_n=A₁a_n-1 + A₂a_n-2 + ... + A_ja_n-j

其中f(t₁)=u₁，f(t₂)=u₂，...，f(t_j)=u_j作为初始条件。

数字j很重要，它被称为线性递推关系的阶。请注意，我们始终至少需要j个初始条件才能使递推关系有意义。

回顾上一节，我们看到可以找到一个非递归函数（一个解），它将取与递推关系本身相同的数值。让我们看看如何求解一些线性递推关系 - 我们可以用一种非常系统的方法来做到这一点，但我们首先需要建立几个定理。

求解线性递推关系

解的和

这个定理说

如果f(n)和g(n)都是线性递推关系a_n=Aa_n-1+Ba_n-2的解，那么它们的和也是一个解。

这是真的，因为如果我们将递推关系重新排列为a_n-Aa_n-1-Ba_n-2=0，并且我们知道f(n)和g(n)是解，因此，在代入递推关系后，我们有

f(n)-Af(n-1)-Bf(n-2)=0

g(n)-Ag(n-1)-Bg(n-2)=0

如果我们将和f(n)+g(n)代入递推关系，我们将得到

(f(n)+g(n))-A(f(n-1)+g(n-1))-B((f(n-2)+g(n-2))=0

展开后，我们有

f(n)-Af(n-1)-Bf(n-2)+g(n)-Ag(n-1)-Bg(n-2)

但使用我们首先建立的两个事实，这与

0+0=0

因此，f(n)+g(n)确实是递推关系的解。

通解

下一个定理指出

假设我们有一个二阶线性递推关系，a_n-Aa_n-1-Ba_n-2=0，并给出初始条件。

那么γrⁿ是递推关系的解，其中r是二次方程

x²-Ax-B=0

的解，我们称之为特征方程。
我们猜测（为什么并不重要，现在就接受它）γrⁿ可能是一个解。我们可以证明，如果（且仅当）它解出特征方程，它就是一个解 ;

我们将γrⁿ（r不等于零）代入递推关系中，得到

γrⁿ-Aγr^n-1-Bγr^n-2=0

然后用最右边的项γr^n-2进行因式分解

γr^n-2(r²-Ar-B)=0

我们知道r不等于零，因此r^n-2永远不可能为零。因此，r²-Ar-B必须为零，因此，γrⁿ（其中r是r²-Ar-B=0的解）确实是线性递推关系的解。请注意，我们可以轻松地将这个事实推广到更高阶的线性递推关系。

这是从哪里来的？为什么它有效（除了死板的证明）？这里有一个更直观的（但数学上不那么严谨）的解释。
求解特征方程找到一个满足线性递推关系的函数，并且方便地不需要对所有n项进行求和来找到第n项。
我们需要 : 一个函数F(n)，使得F(n) = A * F(n-1) + B * F(n-2)
我们求解 : x² = A* x + B，并将其解称为r。可能有多个r值，如下面的例子所示！
我们得到 : 一个函数F(n) = rⁿ，它满足F(n) = A * F(n-1) + B * F(n-2)
让我们检查一下：rⁿ = A*r^n-1 + B*r^n-2 是否成立？将两边都除以r^n-2，我们会得到r² = A*r + B，这必须成立，因为r是x² = A* x + B的解

为什么 γ*rⁿ 也满足递归关系？ 如果 F(n)=rⁿ 是一个解，也就是说，rⁿ-A*r^n-1-B*r^n-2=0，那么 F(n)=γrⁿ 当然也是一个解，因为 γrⁿ-A*γr^n-1-B*γr^n-2=γ(rⁿ-A*r^n-1-B*r^n-2)=0。

因为我们有一个二阶递归关系，所以通解是两个解的和，这两个解对应特征方程的两个根。假设这两个根是 r 和 s。通解是 C(rⁿ)+D(sⁿ)，其中 C 和 D 是常数。我们可以通过关系的两个初始值（必须有两个才能找到 C 和 D）来求出它们。将这些值代入通解，将得到两个方程，我们可以（希望）解出它们。

例子

让我们通过一个例子来了解如何使用上述定理来解决线性递归关系。考察这里给出的函数 a(n)

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

这个递归关系的特征方程是

r²-r-2 = 0，如上所示，因为 A=1 且 B=2

即 (r-2)(r+1)=0，它的根为 2，-1。

所以通解是 C(2ⁿ)+D(-1)ⁿ。

为了找到这个特定情况下的 C 和 D，我们需要两个初始值，假设 a(1) = 0 且 a(2) = 2。这些值会得到一个由两个方程组成的系统
0 = C(2¹)+D(-1)¹
2 = C(2²)+D(-1)²
解这两个方程得到：C = 1/3，D = 2/3，所以解是 1/3*(2ⁿ)+2/3*(-1)ⁿ。