递归分类详解

本文将详细介绍在C++中的递归.

定义：递归是一个函数调用它自身的过程，但由于可能会有无限次的调用，栈可能会溢出，所以递归必须要有终止条件.

在C++中，递归分为两种类型:

• 运行时递归(Run-Time Recursion)：与C语言类似
• 编译时递归(Compile-Time Recursion): 用C++提供的模板元编程,不给出翻译，请参照原文

每一种分类可以细分为以下5种类型

• 线性递归(Linear Recursion)
• 二分递归(Binary Recursion)
• 尾递归(Tail Recursion)
• 互递归(Mutual Recursion)
• 嵌套递归(Nested Recursion)

一、线性递归

该递归最常用，它通过一种简单的方式调用自己，并通过一个终止条件终止自身.这个调用过程称之为“缠绕(Winding)”,当函数返回给调用者时称之为“解除缠绕(Un-Winding)”。递归终止条件是我们已知的基础条件.

例子:计算阶乘

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

二、二分递归

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

例子:斐波那契数列

int FibNum(int n)
{
    // Base conditions
    if (n < 1)
        return -1;
    if (1 == n || 2 == n)
        return 1;

    // Recursive call by Binary Method
    return FibNum(n - 1) + FibNum(n - 2);   
}

三、尾递归

四、互递归

函数相互调用。假设FunA调用FunB, FunB递归调用FunA。这实际上不是递归的，但它和递归是一样的。所以你可以说不支持递归调用的编程语言，相互递归可以应用在那里来满足递归的要求。基本条件可以应用于任意一个或多个函数或所有函数。

例子：判断偶数或者奇数

bool IsOddNumber(int n)
{
    // Base or Termination Condition
    if (0 == n)
        return 0;
    else
        // Recursive call by Mutual Method
        return IsEvenNumber(n - 1);
}
bool IsEvenNumber(int n)
{
    // Base or Termination Condition
    if (0 == n)
        return 1;
    else
        // Recursive call by Mutual Method
        return IsOddNumber(n - 1);
}

五、嵌套递归

它和所有递归非常不同。除嵌套递归外，所有递归都可以转换为迭代(循环)。你可以通过阿克曼函数的例子来理解这个递归。

int Ackermann(int x, int y)
{
    // Base or Termination Condition
    if (0 == x)
    {
        return y + 1;
    }
    // Error Handling condition
    if (x < 0 || y < 0)
    {
        return -1;
    }
    // Recursive call by Linear method 
    else if (x > 0 && 0 == y)
    {
        return Ackermann(x - 1, 1);
    }
    // Recursive call by Nested method
    else
    {
        return Ackermann(x - 1, Ackermann(x, y - 1));
    }
}

原文链接:https://www.dreamincode.net/forums/topic/51296-types-of-recursion/