C++中的遞歸分解

Question

我在學習遞歸。無法分解練習來繪製遞歸樹 - 在基本案例下面的代碼中包含函數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.... 

Answer 1

這個問題需要比傳統的遞歸實施例（如分選），其中該問題集被減小每個遞歸和存在自然限制（問題大小< = 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); 
}