c++ - 用C++做了一个递归函数。现在要求制作一个 "tail-recursion"函数

Question

这是我想出的一个递归函数，用于满足复制字符串中每个字母的要求(即“abc”到“aabbcc”):

#include <string>
#include <iostream>

using namespace std;

string repeater(string str){
    if (str == ""){
        return "";
    }
    else{
        return str.substr(0,1) + str.substr(0,1) + repeater(str.substr(1));
    }
}

int main(){
    string test = "llama";
    cout << "repeater(\"" << test << "\") returned: " << repeater(test) << endl;
}

现在我被要求制作一个做同样事情的“尾递归”函数。我正在阅读它，我的文本给出了以下“尾递归”函数的示例:

int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n – 1);
}

这看起来与我用来创建自己的方法相同。我需要交2个版本的递归函数。我的已经是“尾递归”函数了吗？如果是这样，我将如何制作前向递归函数(或者，如果情况相反，反之亦然)？

http://ideone.com/JrtRsE

Answer 1

我建议如下:

string tail_repeater(string left, string right){
    if (right == ""){
       return left;
    }
    return tail_repeater(left + right.substr(0,1) + right.substr(0,1), right.substr(1));
}

string repeater(string str){
   tail_repeater("", str);
}