0

我正在尝试学习递归。分解练习以绘制递归树时遇到问题 - 在基本案例下方的代码中包括函数 window.drawPolarLine(branchbase, length, angle)，它返回刚刚绘制的分支末端的 GPoint（x 和 y）。任何递归解决方案都必须跟踪大量 GPoint。我不知道这是否应该发生在堆栈帧中，或者我是否应该使用向量来存储它们。使用向量似乎正在走向迭代解决方案的道路？

无论如何，到目前为止，这是我非常混乱的代码；

/**
 * File: trees.cpp
 * ---------------
 * Draws a recursive tree as specified in the Assignment 3 handout.
 */

#include <string>    // for string
#include <iostream>  // for cout, endl
using namespace std;

#include "console.h" // required of all CS106 C++ programs
#include "gwindow.h" // for GWindow class and its setTitle, setColor, and drawPolarLine methods
#include "gtypes.h"  // for GPoint class
#include "random.h"  // for randomChance function

const static double kWindowWidth = 600;
const static double kWindowHeight = 600;
const static string kWindowTitle = "Recursive Trees";
const static double kTrunkLength  = kWindowHeight/4;
const static double kShrinkFactor = 0.70;
const static int kBranchAngleSeparation = 15;
const static int kTrunkStartAngle = 90;
const static string kLeafColor = "#2e8b57";
const static string kTrunkColor = "#8b7765";
const static double kBranchProbability = 1.0;

static GPoint drawTree(GWindow& window, int order, GPoint branchBase, double length, int angle, Vector<GPoint>& branches);

const static int kHighestOrder = 5;
int main() {
    GWindow window(kWindowWidth, kWindowHeight);
    window.setWindowTitle(kWindowTitle);
    cout << "Repeatedly click the mouse in the graphics window to draw " << endl;
    cout << "recursive trees of higher and higher order." << endl;
    GPoint trunkBase(window.getWidth()/2, window.getHeight());
    Vector<GPoint> branches;
    for (int order = 0; order <= kHighestOrder; order++) {
        waitForClick();
        window.clear();
        drawTree(window, order, trunkBase, kTrunkLength, kTrunkStartAngle, branches);
    }

    cout << endl;
    cout << "All trees through order " << kHighestOrder << " have been drawn." << endl;
    cout << "Click the mouse anywhere in the graphics window to quit." << endl;
    waitForClick();
    return 0;
}

static GPoint drawTree(GWindow& window, int order, GPoint branchbase, double length, int angle, Vector<GPoint>& branches) {
    if (order == 0) {

        GPoint base = window.drawPolarLine(branchbase, length, angle);
        branches.add(base);
        return branchbase;
    }

        window.setColor(order < 2 ? kLeafColor : kTrunkColor);

        branchbase = branches.get(order - 1);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle - 45, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle - 30, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle - 15, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle + 15, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle + 30, branches);
        drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle + 45, branches);


        return drawTree(window, order - 1, branchbase, length * kShrinkFactor, angle, branches);
    }
    // update this function to wrap around another version of drawTree, which
    // recursively draws the tree of the specified order....
4

1 回答 1

0

这个问题需要与经典递归示例（如排序）略有不同的方法，其中问题集在每次递归时都会减少，并且存在自然限制（问题大小 <= 1）。

有了这个问题，信息量随着树的顺序呈指数增长。这使得通过首先绘制二阶树并让函数返回给您这些分支结束的位置（以及角度）来绘制三阶树是不切实际的，因此您可以将三阶分支添加到它。

对于这类问题，编写这样的递归函数要容易得多：

void drawTreeOrder(GWindow& window, int curr_order, int max_order, GPoint branchBase, double length, int angle)
{
    /* Check if there is more work to do */
    if (curr_order >= max_order)
    {
        return;
    }

    /* Draw a branch */
    window.setColor(curr_order - max_order < 2 ? kLeafColor : kTrunkColor);
    GPoint end = window.drawPolarLine(branchBase, length, angle);

    /* Draw the higher-order branches starting from the current one */
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle - 45, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle - 30, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle - 15, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle + 15, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle + 30, branches);
    drawTreeOrder(window, order + 1, max_order, end, length * kShrinkFactor, angle + 45, branches);
}

/* Convenience function, so the caller does not have to bother with curr_order */
void drawTree(GWindow& window, int max_order, GPoint branchbase, double length, int angle)
{
    drawTreeOrder(window, 0, max_order, branchBase, length, angle);
}
于 2012-12-14T15:42:05.697 回答