and the illustration below:
It took me a while because I was distracted by a seductively sneaky solution to the problem using MATLAB's array math. If the steps below the middle step could be calculated, all the steps after the middle step could be calculated in one swell foop by adding the value of the end point of the middle step to the array of steps between 0 and the lower x-value of the middle step.
It took me a while to find the appropriate quote from Knuth: "The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming." (From Computer Programming as an Art, p. 671, https://en.wikiquote.org/wiki/Donald_Knuth)
It was only after I'd solved the problem myself that an online search found a recursive solution (m2matlabdb.ma.tum.de/download.jsp?MC_ID=5&SC_ID=13&MP_ID=104) which provides not only a plot of the staircase, but the Cantor set as well.
(I avoid recursion because 1) I'm not good at it (why not admit it here), 2) recursion generally uses more memory than looping, and, lastly, I suspect that the repetitive function calls is slower.)
From a quick look at the recursive code I like mine even better because the recursive code starts with a conditional check to see how many steps are requested whereas mine will take any step. (To be frank, however, the recursive code does the mandatory parameter checking. Mine assumes that the user will not pass an invalid number of steps, e.g., 0 or a negative number, or pass a string or other pathalogical value.)
The recursive code creates the middle step and then if more steps are required generates the left and right side of the Devil's Staircase. The code involves a lot of multiplication of array values. My early assembler experience always made me avoid multiplication and array values. I wish I could blame a cruel instructor for beating into using pointers and addition, but I did it to myself. As MATLAB doesn't have pointers (yeah, I know, arrays are really pointers) I had to use arrays also. You can see from the code that calculating a new vector value required two or three multiplications, depending on how you count. (I'm guessing that the multiplication by 0.5 is accomplished by shifting the bits to the right rather than actually multiplying by 0.5
xr(stufe)=.5*((1-e)*xr(stufe+1)+(1+e)*xl(stufe+1));
yr(stufe)=.5*(yr(stufe+1)+yl(stufe+1));
My MATLAB solution is far from inspired, but much shorter than the recursive method. The code generates the two member vector (0 and 1) and calls the genXValues function to generate the new values by using every other value in the current vector. Here's the heart of it:
