Computer Science Teacher

# July, 2008

• #### The Four Digit Problem

So I was remembering a piece of code I had to write once. Honestly I don’t remember exactly why I had to write it. I think it may have been part of a set of patterned data for some test software though. In any case the problem was to generate a four digit random number with no duplicated digits. Now there are lots of ways to do this. A simple brute force way is below.

```    Function Digit4() As Integer

Dim i(4) As Integer
i(0) = r.Next(1, 9)
Do
i(1) = r.Next(0, 9)
Loop Until i(1) <> i(0)
Do
i(2) = r.Next(0, 9)
Loop Until i(2) <> i(0) And i(2) <> i(1)
Do
i(3) = r.Next(0, 9)
Loop Until i(3) <> i(0) And i(3) <> i(1) And i(3) <> i(2)
Return i(0) * 1000 + i(1) * 100 + i(2) * 10 + i(3)
End Function```

Yes I left out the comments to save space. (That’s my story and I’m sticking to it) The way it works is to pick a single random digit, then pick a second one looping back to pick a new one if by some chance the digit drawn is the same as the one previously checked. This is done again except that the next one has two numbers to compare against and the final number has three numbers to compare against. It works (I tested it) but it doesn’t scale well.

The task I would assign students is to come up with at least two other ways to solve this problem that are more scalable and then compare them all for performance. I might hint at the word “recursion” which I’ve been thinking a lot about lately. This sample code is in Visual Basic because that is my hack something together language of choice. Converting it to other languages is another exercise left to the student.

Two notes: The best part about this post is all the discussion in the comments so don't miss them. Second is that the "solution" I entered is what students often come up with and not what I would use is a real application. I wanted to get some discussion going and that seems to have happened.

Edit: 12/2/2009 Bart Massey of Portland State University has a very helpful reply post called Random non-repeating sequences that I highly recommend. I appreciate his letting me know about it as I think it is an interesting solution that is well explained. So please go read it.
• #### Microsoft Visual Studio Middle School Power Toy 1.0

The Microsoft Visual Studio Middle School Power Toy 1.0 was originally created by Microsoft China to help meet the curriculum needs for teaching programming in that country. According to regulations/policies of China’s Ministry of Education (MOE) almost all Chinese high school students need to learn computer programming. Bring that up at the next meeting you attend where the need for programming/computer science is questioned! But I digress. This week the English language version of these tools were made available.

The Power Toy is a set of five tools that add into Visual Studio to help beginners. These tools are a free download. Three of the five work equally well with both Visual Basic and C#. Two of them (the assistant class designer and flow chart creator) only work with C# at least for now. The following descriptions comes from the download page. I plan to have individual posts on each of these tools in the very near future.

• The Visual Sort Designer Control is a supplementary teaching tool developed to help middle school students learn the basic concepts, algorithms, and implementations of popular computer sorting algorithms. It supports bubble and insertion sorting. The control generates initial values automatically and demonstrates intermediate states in the sorting process. It also generates sorting source code for both Visual Basic and C#.
• The Visual Search Designer Control is a teaching tool developed to help middle school students learn the basic concepts, algorithms, and implementations of popular data search algorithms. It supports binary and sequential searches. The control generates initial values automatically and demonstrates intermediate states in the searching process. It also generates source code for both Visual Basic and C#.
• The Visual Declarative Designer is an intuitive variable declaration tool designed for novice programmers. During the coding process the student can declare variables of various types and generate the corresponding source code. Visual Variable Declarative Designer provides a visual approach to variable declaration. Teachers in the Information Technology (IT) field can use this designer to teach students the basic concepts of variable declaration and naming, variable types, access modifiers, and initial values.
• The Assistant Class Designer is a visual class designer intended for novice programmers such as middle school students. During the design process, students can easily add classes, properties, methods and events. The designer also generates source code that can be inserted into a project and modified as needed. By using this class designer and code generator, complicated classes can be easily created and configured. The Assistant Class Designer provides an intuitive approach to designing classes and helps students to understand key object-oriented programming concepts such as classes, encapsulation, inheritance, and polymorphism.
• Visual Programming Flow Chart is a supplementary teaching tool designed to help students understand program control flow. It generates flow charts for functions and saves them in the JPG picture format. This tool is easily activated from the Visual Studio Integrated Development Environment (IDE) by simply right-clicking on a function name and choosing “Generate flow chart…” from the context menu. The resulting flowchart can be customized by changing its colors and other effects. This visual tool provides an intuitive way to explore source code, to examine its control flow, and to identify logic errors.
• #### Recursion See Recursion Again

I don’t remember exactly when I learned recursion. If I recall correctly, and I could be wrong after almost 35 years, the version of FORTRAN that was my first programming language didn’t even support recursive subroutine calls. But somewhere along the line I did learn it. While I admit that I had a hard time grasping it at first I thought it was pretty cool once I did. There is no question that it can be a powerful tool in the right hands.

I do remember one memorable day when one of my students discovered recursion accidentally though. It was his second programming course so of course he knew about loops. But this was the first week and we were just starting with C++. This clever student wondered if perhaps he could get the same result by having main call itself. Of course he could but without setting a way to end the loop he also discovered the stack overflow. Now that is a teachable moment!

Recursion has traditionally been thought of as a difficult concept. Not by everyone of course. The people who use functional languages like Scheme and probably F# introduce recursion early – before “conventional” loops. Lately I’ve seen some discussion that recursion should be taught early in all programming courses.

Marty Billingsley of the University of Chicago Laboratory Schools recently said on the APCS mailing list that:

I've found that teaching recursion before loops results in students who are willing to use more of the design tools in their mental toolboxes.

When taught loops first, students find recursion sort of "unnatural" and will only use it when directed to. When taught recursion first, students usually will consider recursion as well as loops when designing a program on their own.

While neither he nor I have empirical data to support this I find this a reasonable theory. I have mixed feelings about using recursion when a loop will do but that may be because I “grew up” in a world where function calls were more expensive in time and memory then they are today. But I want people to think about recursive solutions even when they are not forced into it. More than that I want people to be comfortable with recursive solutions. I still remember a code review some years ago when three professional developers asked me to re-write a very clever routine I’d written to use conventional loops rather than a recursive solution just because they were not comfortable supporting it. It really wasn’t that complex but the idea of using recursion made them uncomfortable.

Honestly though I am not sure where in a textbook/curriculum to introduce recursion or how to start. I’ve really ignored it too often in the past. Do any of you have suggestions of textbooks or other resources that introduce recursion in a good way for beginners who have not already learned loops? This is going to keep me awake while I am on vacation this week. Really it is.

Page 1 of 8 (22 items) 12345»