Math for CS: Recursive Definition

Recursive data - define something in terms of simpler version of the same thing.

Recursive data types play a central role in programming, and induction is really all about them. Recursive data types are specified by recursive definitions, which say how to construct new data elements from previous ones. Along with each recursive data type there are recursive definitions of properties or functions on the data type. Most importantly, based on a recursive definition, there is a structural induction method for proving that all data of the given type have some property. This chapter examines a few examples of recursive data types and recursively defined functions on them:

• strings of characters,
• “balanced” strings of brackets,
• the nonnegative integers, and
• arithmetic expressions.

They start off by showing an example of recursively-defined character strings. This structure is actually very similar to the data definition of a list of strings in the course Systematic Program Design. They even mention using the cons operator for constructing such a list.

Structural induction is a method for proving that all the elements of a recursively defined data type have some property. A structural induction proof has two parts corresponding to the recursive definition:

• Prove that each base case element has the property.
• Prove that each constructor case element has the property, when the constructor is applied to elements that have the property.

We then go on to an example of strings with matching brackets. We also go over the fibonacci, ill-formed function definitions, and the Ackermann function, followed by arithmetic expressions.s

On Structural Induction in Computer Science

What matters is that for recursively defined data types, structural induction is a simple and natural approach. This makes it a technique every computer scientist should embrace.

The in-class problems were not easy. I had to look up the solutions, after taking some time to read and understand the questions and give them an attempt.

There’s no way I would have came up with the solutions on my own. If I was actually taking this class at MIT, either I’d have years of the right math knowledge compounded enough to where I’m able to figure it out in some time, or I’d be constantly going to office hours for the professor or TA’s, or taking advantage of study groups where someone else was able to figure it out and then explain.

I’m not too concerned that I’m not able to solve many of these problems right away. The exercises are difficult. Hard to say if these type of questions will pop up in the real world. It seems to be mostly theory.