本文将详细介绍在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/


0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注