递归类型

得分: 3.7/5 (44 票)

简介

在此，我将详细介绍 C++ 中的递归。定义：递归是函数调用自身的过程，但由于函数调用会无限次地进行，因此堆栈帧会超出限制。所以递归必须有终止条件。

许多复杂的问题可以通过递归用简单的代码来解决。但它比迭代要昂贵得多。因为每次递归调用都会形成一个堆栈帧。你们都已经知道它的成本了。但是，如果问题非常复杂，除了递归之外别无他法。

背景

递归首先出现在数学中，然后进入计算机科学。它的使用思想是首先将问题分解为子问题，然后使用递归来解决它。

代码

在 C++ 中，递归可分为两类
(a) 运行时递归: 与 C 中的普通递归相同
(b) 编译时递归: 通过使用模板

这些都可以进一步细分为以下几类

1. 线性递归
2. 递归
3. 尾部递归
4. 相互递归
5. 嵌套递归

1. 线性递归: 这是最常用的递归。在此递归中，函数以简单的方式调用自身，并通过终止条件终止。这个过程称为“缠绕”（Winding），当它返回调用者时，称为“解缠”（Un-Winding）。终止条件也称为基本条件。

示例: 通过线性递归计算阶乘

运行时版本

代码

int Fact(long n)
{
if(0>n)
return -1;
if(0 == n)
return 1;
else
{
return ( n* Fact(n-1));
}
}

缠绕过程

函数调用函数返回

Fact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)
终止点
Fact(0) 1

解缠过程

Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1

编译时版本

代码

// 模板用于基本条件
template <>
struct Fact<0>
{
enum
{
factVal = 1
};
};

template
struct Fact
{
// 通过线性方法进行递归调用
enum
{
value = n * Fact::factVal
};
};

要测试它在编译时如何工作，只需调用
cout <<>::factVal ;
并编译它，然后会出现编译器错误，因为没有针对 -1 的模板。

2. 递归: 递归是一个函数一次调用两次的过程，而不是一次调用一次。它主要用于树形数据结构，如遍历、查找高度、合并等操作。

示例: 斐波那契数列

运行时版本代码
代码

int FibNum(int n)
{
// 基本条件
if (n < 1)
return -1;
if (1 == n || 2 == n)
return 1; // 通过递归方法进行递归调用
return FibNum(n - 1) + FibNum(n - 2);
// 一次调用两个递归函数，所以是递归
}
// binary }

编译时版本代码
代码

// 基本条件
template<>
struct FibNum<2>
{
enum { val = 1 };
};
template <>
struct FibNum<1>
{
enum { val = 1 };
};

// 通过递归方法进行递归调用
template
struct FibNum
{
enum { val= FibNum::val + FibNum::val };
};

3. 尾部递归: 在此方法中，递归函数最后被调用。因此，它比线性递归方法更有效。这意味着终止点将（100%）出现，你只需要设置该条件。

示例: 斐波那契数列

运行时版本代码
代码

int FibNum(int n, int x, int y)
{
if (1 == n) // 基本条件
{
return y;
}
else // 通过尾部方法进行递归调用
{
return FibNum(n-1, y, x+y);
}
}

编译时版本代码

代码

template
struct FibNum
{
// 通过尾部方法进行递归调用
enum
{
val = FibNum::val
};
};

// 基本条件或终止
template
struct FibNum<1,>
{
enum
{
val = y
};
};

4. 相互递归: 函数相互调用。例如，FunA 调用 FunB，FunB 又递归调用 FunA。这实际上不是递归，但它做的事情与递归相同。所以你可以说，不支持递归调用的编程语言，可以通过相互递归来实现递归的需求。基本条件可以应用于一个、多个或所有函数中的任何一个。

示例: 判断奇偶数

运行时版本代码
代码

bool IsOddNumber(int n)
{
// 基本或终止条件
if (0 == n)
return 0;
else
// 通过相互方法进行递归调用
return IsEvenNumber(n - 1);
}
bool IsEvenNumber(int n)
{
// 基本或终止条件
if (0 == n)
return 1;
else
// 通过相互方法进行递归调用
return IsOddNumber(n - 1);
}

编译时版本代码
代码

// 基本或终止条件
template <>
struct IsOddNumber<0>
{
enum
{
val = 0
};
};
template <>
struct IsEvenNumber<0>
{
enum
{
val = 1
};
};

// 通过相互方法进行递归调用

template
struct IsOddNumber
{
enum
{
val = n == 0 ? 0 : IsEvenNumber::val
};
};

template
struct IsEvenNumber
{
enum
{
val = n == 0 ? 1 : IsOddNumber::val
};
};

5. 嵌套递归: 这与其他所有递归都非常不同。除了嵌套递归，所有递归都可以转换为迭代（循环）。你可以通过 Ackermann 函数的例子来理解这种递归。

示例: Ackermann 函数

运行时版本代码
代码

int Ackermann(int x, int y)
{
// 基本或终止条件
if (0 == x)
{
return y + 1;
}
// 错误处理条件
if (x <> 0 && 0 == y)
{
return Ackermann(x-1, 1);
}
// 通过嵌套方法进行递归调用
else
{
return Ackermann(x-1, Ackermann(x, y-1));
}
}

编译时版本代码
代码

// 基本或终止条件
template
struct Ackermann<0,>
{
enum { val = y + 1 };
};

// 通过线性方法进行递归调用
template
struct Ackermann
{
enum
{
val = Ackermann::val
};
};
// 通过嵌套方法进行递归调用
template
struct Ackermann
{
枚举
{
val = Ackermann ::val>::val
};
};

C++

文章

递归类型