C++递归转迭代

Question

下午好，我希望有人能帮助我看看我漏掉了什么。我承认这是一个家庭作业，但我们被允许在代码上进行协作，所以希望这里的某个人不介意提供帮助。

对于这个程序，我需要使用递归和迭代来旋转一组三个项目。我已经成功地完成了递归情况，但迭代版本给我带来了很多麻烦。我尝试过的所有方法都会导致段错误或无限打印。以下是代码，再次感谢任何帮助：

template<typename A, typename B, typename C>
class Triple{
public:
    A first;
    B second;
    C third;

Triple(A a, B b, C c){ first = a; second = b; third = c;}

A fst(){return first;}
B snd(){return second;}
C thd(){return third;}

// The function change1(), changes the first component of a triple. 
void change1(A a){ first = a;}
};

// A linked list of triples where the order of the triple rotates as it goes.
template<typename A, typename B, typename C>
class RotateList{ 
public:
    Triple<A,B,C> *t;
    RotateList<B,C,A> * next; // Notice the order has changed

    RotateList(Triple<A,B,C> *t1, RotateList<B,C,A> * n1){ this->t = t1; this->next = n1;}

/*
 * Implement with recursion, creating i triples, each with the order rotated from the
 * previous.
 */
static RotateList<A,B,C> * create(A a, B b, C c, int i){
if (i <= 0) return nullptr;
Triple<A,B,C> * t = new Triple<A,B,C>(a,b,c);
RotateList<B,C,A> * n = RotateList<B,C,A>::create(b,c,a, i-1); 

return new RotateList<A,B,C>(t, n);
}

/*
 * Implement with iteration, using the same instance of the same three triples
 * over and over.
 */
static RotateList<A,B,C> * create2(A a, B b, C c, int i){
}

/* Print the whole rotating list. */ 
void print(){
cout << "{" << t->fst() << " "<< t->snd() << " "<< t->thd() << "}";
if (next != nullptr) 
    next->print();
else 
    cout << endl;
}
};


int main(){
float f = 3.14;
int i = 3;
char c = 'c';

Triple<float,int,char> t = Triple<float,int,char>(f,i,c);
Triple<float,int,char> t1 = t;
cout << "Starting triple: [" << t.fst() << " "<< t.snd() << " "<< t.thd() << "]" << endl;

cout << endl << "Rotating list created recursively" << endl;
RotateList<float,int,char> * r= RotateList<float,int,char>::create(f,i,c, 10);
r->print();

r->t->change1(42.42);
r->print();

cout << endl << "Rotating list created iteratively" << endl;
RotateList<float,int,char> * s= RotateList<float,int,char>::create2(f,i,c, 10);
s->print();

s->t->change1(42.42);
s->print();

s->next->t->change1(501);
s->print();
}

我的尝试如下：

static RotateList<A,B,C> * create2(A a, B b, C c, int i) {
    RotateList<C,A,B> *l1 = new RotateList<A,B,C>(new Triple<A,B,C>, nullptr);
    RotateList<B,C,A> *l2;
    RotateList<C,A,B> *l3;        
    RotateList<A,B,C> *tmp1 = l1;
    RotateList<B,C,A> *tmp2;
    RotateList<C,A,B> *tmp3;

    int nextTriple = 2;
    for (i; i > 0; i--) {
        tmp3->next = l1;
        tmp1 = tmp3->next;
        nextTriple = 2;
    } else if {
        temp1->mext = l2;
        tmp2 = tmp1->next;
        nextTriple = 3;
    } else {
        tmp2->next = l3;
        tmp3 = tmp2->next;
        nextTriple = 1;
    }
}
return l1;
}

- jwilson

---

你在迭代版本中尝试了哪些事情？ - 1201ProgramAlarm

我已经尝试创建列表中的三个三元组，然后循环组装它们，但每次都会出现分段错误。 - jwilson

你能把那段代码添加到你的帖子中吗？因为那是你所询问的核心。 - 1201ProgramAlarm

好的，我添加了它。希望它不会太丑，我只是从Java和Python转学C++，正在学习中。 - jwilson

关于一份作业任务的问题，你写得非常好（在这个网站的C和C++角落中似乎很少见到这样的问题）。 - PC Luddite

这个问题可能需要更详细的结果描述（例如，它是对元组应用置换(2 3 1)幂的列表，或者老师是如何表述的），即使对于那些认为（写得好的）代码自文档化的人也是如此。 - outis

Answer 1

我将以概述开始，然后是一个示例。如果您需要更具体的任务，请添加评论，但请在思考此答案之后再添加。

概述

有两种通用的将递归转换为迭代的方法。一种是重新编写递归函数以使用尾调用（即在递归调用之后不再进行任何处理；包括某些C ++编译器在内的一些编译器可以优化尾调用，生成与迭代版本无法区分的目标代码）。另一种（例如用于迭代汉诺塔解决方案）是基本上使用自己的堆栈来跟踪帧。幸运的是，通过尾调用重写可以解决任务。

示例

所有代码未经测试，可能包含错误和漏洞。

对于比所分配的更简单的示例，请考虑一个函数range(a，b)，它从a（包括）到b（不包括）生成整数列表。递归地：

List<int>* range(int a, int b) {
    if (a >= b) {
       // base case
       return new List<int>();
    }
    // recursive case
    return List<int>::cons(a, range(a+1, b));
}

将其转换为尾调用，通常需要添加一个（或多个）变量来累积计算结果，并分别使用递归和初始化函数：

List<int>* range_recur (int a, int b, List<int>* xs) {
    if (b < a) {
        // base case
        return xs;
    }
    // recursive case
    return range_recur(a, b-1, List<int>::cons(b, xs));
}

List<int>* range(int a, int b) {
    return range_recur(a, b-1, new List<int>());
}

请注意，需要进行一些其他更改，主要是处理边界的方式，以便可以将cons操作移动到递归调用之前。

基本情况对应于循环条件，但是退出循环时机不同。因此，让我们重写range_recur()，使其更接近迭代版本，通过否定测试并交换两种情况来实现。

List<int>* range_recur (int a, int b, List<int>* xs) {
    // recursive case test
    if (b >= a) {
        // recursive case
        return range_recur(a, b-1, List<int>::cons(b, xs));
    }
    // base case
    return xs;
}

这段话的意思是：“将这个递归版本转换为迭代版本非常简单：不再使用递归传递每个变量，而是将它们赋值（如果值相互依赖，则可能需要使用临时变量）。if条件变成了循环条件。初始化函数体放在循环之前，基本情况放在循环之后。”

List<int>* range (int a, int b) {
    // range():
    List<int> *xs = new List<int>();
    b = b - 1;
    // range_recur():
    // recursive case test:
    while (b >= a) {
        // recursive case
        xs = List<int>::cons(b, xs);
        b = b - 1;
    }
    // base case
    return xs;
}

您可能需要进行清理重写，使用更习惯用的操作（递减和 for 循环; 留给读者练习）。

离题

分配任务可能没有提到内存管理，但这是一个重要的主题。示例类像渔网一样泄漏（并且在使用临时变量的 RotateList 时会遇到麻烦），因为进程不会活得足够长，所以这大多不会成为问题。然而，如果这些类在另一个程序中使用，可能会非常棘手。现在，在生产中的最佳实践是使用某种 智能指针 来管理对象。对于一些作业（特别是那些您已经掌握了的作业），自己处理内存管理是一个很好的练习。

- outis

---

谢谢，你的解释比我的课程清晰多了。虽然我还没有完成解决方案，但是由于你的帮助，我离成功更近了一步！ - jwilson