# Solving a rod cutting problem with recursion

I'm trying to use Mathematica 10.0. to solve a rod cutting problem with naive recursion. The problem is taken from Introduction to Algorithm, 3rd edition.

The length price for rod is defined in the book as

price = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30}


where the i-th element means length i can be sold for price[[i]]. I want to find the optimal cut for given length to generate maximum profit.

Following the idea of naive recursion given in the book, I write following code:

rodcut[price_, length_] :=
Module[{n = length, q = 0},
If[n == 0,
0,
For[i = 1, i <= n, i++,
q = Max[q, price[[i]] + rodcut[price, n - i]]];
Return[q]]]


However, when I run the code rodcut[price, k], it always output outcome price[[k]]. It seems like the iteration skips the process and just run the last step i = k.

Could anyone give me some help?

• It looks like it's because i gets reset to 1 repeatedly, presumably because it has global scope, simply add i to the list of symbols being declared locally at the top of your Module. – Quantum_Oli Nov 11 '16 at 8:45
• Or use Do instead of For. – Simon Woods Nov 11 '16 at 19:50
• @Quantum_Oli You're right. i is global variable but I'm wondering how i gets to reset to 1 repeatly – nwdsl Nov 12 '16 at 0:49