C++에서 재귀 분해

Question

재귀를 배우려고합니다. 재귀 트리를 그리는 데 어려움을 겪는 데 문제가있는 경우 기본 case 아래의 코드에서 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)가된다 (소트 등) 고전 재귀 예보다 약간 다른 접근법을 필요로한다.

이 문제로 인해 정보량은 트리 순서에 따라 기하 급수적으로 증가합니다. 이로 인해 2 차 트리를 먼저 그려서 그 분기가 끝난 곳으로 (그리고 어떤 각도로) 함수가 반환되도록함으로써 3 차 트리를 그리는 것이 비현실적입니다. 따라서 3 차 분기를 추가 할 수 있습니다. 이런 종류의 문제를 들어

, 그것은이 같은 재귀 함수를 작성하기가 훨씬 더 쉽습니다 : 바트 많이

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); 
}