Lecture Week 6: Dynamic programming: rod example, is the recursion approach correct?

Question

so then I was watching the lecture and I thought at the time it would be nice to try implement the example (well, partially at least) used in the lecture.

I have two questions:

• Is my approach to this problem from the recursion perspestive correct? I am struggling with the recursion a lot, trying to understand it in depth.
• Could you guys recommend me some good material/books/etc about the recursion and how can I understand it better?

The rod problem:

Suppose you have a rod of length n, and you want to cut up the rod and sell the pieces in a way that maximizes the total amount of money you get.

My code (in c++):

#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>

using namespace std;

// Main struct
struct rd_value {

    int profit = 0; // Profit that we will gain from the particular rod size.
    string rod_ap = ""; // How it would look like ( for style purposes only ).
};

// Just a data structure to tie a struct with a particular rod size.
map<int,rd_value> rod_values;

// It holds our current rod data, 
// we will populate it in the function cut_rod.
rd_value current;

// Global ints to ease the work/
int n, orig;

int cut_rod(int pos)
{
    // Add the style strings and the profit into our current struct.
    current.profit += rod_values[pos].profit;
    current.rod_ap += rod_values[pos].rod_ap + " ";

    // Subtract the cut position from the length of the rod
    // aka we are selling the cut side immediatly as said in the video.
    n -= pos;

    // 1) If our rod can support the same cut after the initial cut,
    // do it again
    // 2) If it can't do 1), try to cut it by one less.
    // 3) If it can't do 1) and 2), just cut it by the it's current length
    // ( actually we are not cutting it now, but for the simplicity purposes
    // let say we are.
    // 4) Exit if we are out of cutting options.

    // 4) is first because it would trigger stack overflow eventually 
    // if it were in the end it will trigger stack overflow.

    if (n <= 0) // 4)
        return 0;
    else if (n >= pos) // 1)
        cut_rod(pos);
    else if (n >= pos - 1) // 2)
        cut_rod(pos - 1);
    else if (n != 0) // 3)
        cut_rod(n);
}

void init_def_values()
{
    // A void function to initialize the selling points for the rods.
    // Could be replaced with a text file approach or something to hold all/some 
    // precomputed rod values to speed the solving process.

    rod_values[1].profit = 1;
    rod_values[1].rod_ap = "*";
    rod_values[2].profit = 5;
    rod_values[2].rod_ap = "**";
    rod_values[3].profit = 8;
    rod_values[3].rod_ap = "***";
    rod_values[4].profit = 10;
    rod_values[4].rod_ap = "** **";
}
int main()
{
    init_def_values();

    // Entering the length of our rod.
    cout << "Please Enter your rod length:";
    cin >> orig;

    n = orig;

    // Exit the program if the length is not valid.
    if (n <= 0)
        return 0;

    // Serve the purpose of a look-up table, if we had all/some of the values in a text file for e.g.
    if (rod_values[n].profit != 0)
        cout << "You would get: " << rod_values[n].profit << "  and the cut rods look like: " << rod_values[n].rod_ap << endl;
    else
    {
        // Why we are starting at 3rd position?
        // Because it makes more sense after all:
        // 1) most economically viable lengths are 2 and 3, they
        // bring the most profit to us, so we start at 3 and move down if neeeded
        // 2) length of 4 is useless except of the length value itself, because it does make
        // more sense to just cut it the 4 length into two smaller peaces of length 2, 
        // thus making  10 profit instead of 8.

        cut_rod(3);

        cout << "Current rod profit: " << current.profit << "  and it looks like: " << current.rod_ap << endl;  
    }

    system("Pause");
    return 0;
}

Answer 1

Recursion isn't done right. For example, your function meant to return an int might end without returning anything.

Essence of recursion is that you define a base case (like for example rod of length 0 is worth nothing), and assume a sub-problem closer to that base case (shorter rod) can already be solved. Like you get a rod of length 10, and assume the problem to have been solved for all rods shorter than 10. You just have to make sure you actually get closer to a base case every recursion, otherwise your recursion turns into an infinite loop (that's not so infinite as call stack grows and eventually overflows).

In the recursive function, you would consider all the different lengths you can sell now (this excludes lengths no longer possible for the remaining length). For each of those lengths, you would take the sum of the value of the current piece and the result of the recursive call for the corresponding rest. At the end, you'd return the largest of those sums.

Your recursive function should not use global variables other than maybe an array with the length->value relations and a memoization structure. Especially it should not change the length (unless you make sure to change it back before you return, but that's useful for larger variables only, where you change only a few bytes)

Cannot recommend any material, as I would also just do an internet search for "recursion explained" or something similar ;)

edit: So a solution might look like

recursive function, called with the rod length as argument:
    if done before for same length:
        return old result
    current best total value = 0
    for all possible cut lengths (in the example 1, 2, 3) that are less than or equal rod length:
        total value = value of cut + recursive function called for rod length minus cut length
        if total value > best total value:
            make total value new best total value (depending on problem also remembering the corresponding cut length)
    remember and return best total value for this rod length