递归在C++中执行到函数有多远?

每次递归调用函数时,它都会有效地复制所需的信息,然后继续。

你可以有一个“无限地”重复出现的程序,也就是说,直到它耗尽了资源,通常堆栈空间这些副本将要进入的空间。看起来像是

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

显然,这并不是很有用,所以您需要编写一个对重复频率有一定限制的程序。下面是一个非常简单的程序,它可以管理:

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

如果编译并运行它,请使用以下命令:

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

你会得到结果:

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $ 

看看它是如何被调用的,10,9,等等,然后在它到达底部之后,它显示它返回1,然后2,等等,回到10?

基本规则是 每一个 递归函数应该有一个基本情况,即 做 再给自己打电话。在这个例子中,基本情况是 count == 0 实际上,我们可以把它写成递归定义。

复发的:
如果c=0:打印底部
如果C>0:打印计数,并且重复发生(C-1)

随着数学的发展,您将看到许多这种类型的递归定义。

这里有一个稍微漂亮的C版本,输出更好:

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

输出:

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10

查字典:

递归 名词。看见 递归

现在,严肃地说,在上面的笑话中,递归的定义是根据递归本身给出的。这是递归。

递归算法是一种基于算法本身实现的算法。开发这种算法的过程从最基本的情况开始,这些情况的解决方案要么是预先知道的,要么是可以简单计算的。然后你用它本身来定义算法。

作为一个简单的例子,计算一个给定整数的n次幂,我可以是一个函数。 power( int number, int power ) . 你怎么能实现它?在很多方面。最简单的方法是调用一个库,然后调用一个循环,或者您可以根据函数本身定义函数:

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

我们已经根据函数本身定义了函数。从最基本的情况开始(n^0=1)。如果我们不是在最简单的情况下,您可以用自己的方式表达您的算法。

程序将通过调用 power( 2, 10 ) 它会反复出现并召唤 power( 2, 9 ) 将问题简化为 更小的 然后根据更简单的问题组成最终答案。

实际调用跟踪将是:

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

在开发递归算法的过程中,它通常帮助我相信我已经启动并运行了该算法,并且只处理新结果的简化/组合。

递归可以理解为归纳原理的一个实际应用。为了证明一个语句p(n)对于所有n,其中p(n)表示“从1到n的整数之和是n(n+1)/2”,我们必须证明两件事:

1. 基本情况: p(n)表示特定整数。P(1)为真,因为1=1(1+1)/2。
2. 归纳案例: 如果p(n)为真,则p(n+1)必须为真。1 +…+n+(n+1)=n(n+1)/2+(n+1)=n(n+1)/2+2(n+1)/2=(n+1)((n+1)+1)/2,即稳定p(n+1)。

类似地,在类似mergesort的递归函数中,我们需要处理两种情况:

1. 基本情况: 如果数组有一个元素,则对其进行排序;否则
2. 递归情况: 将数组拆分为两个较小的数组,合并对每个数组进行排序,然后将它们合并在一起。

关键是这两个数组 更小的 而不是原来的,否则他们中的一个永远不会击中基本情况。因为数组被分割成大约一半,所以在这种情况下,递归的深度大约是log2(n)。

就问题中的代码而言,有三个问题:

1. 基本情况丢失。
2. 重复使用变量farray和sarray并不是绝对必要的,可能会造成混淆。
3. 由于创建和销毁的std::向量的数目,代码将非常慢。mergesort的最佳接口将两个vector::iterator作为输入,类似于std::sort()函数。

新程序员应该尝试用纸和铅笔运行mergesort。

如果递归函数不是无限的,则需要有某种条件,在这种情况下,它返回而不调用自身。对于某些算法来说,这种情况是对数据执行调用不再有意义的时候。

在您的例子中,如果您拆分传入的向量,最终得到两个向量,每个向量只包含一个项,那么对它们调用mergesort()是否有意义?不。

您可以通过检查farray和sarray的大小来处理这个问题,并在组合它们并返回组合之前决定是对两者之一调用mergesort()。

如果一个有两个项目,一个有一个项目怎么办?对大小2调用mergesort(),但对大小1不调用mergesort()。

如果调用mergeSort()在返回之前未对farray或sarray调用mergeSort(),则递归将开始展开。

看看维基百科网页 merge sort 有关您正在尝试执行的操作的其他信息。

作为旁注,请注意您正在复制作为参数给定的每个向量。使用vector<>const&代替。