First Time Learning Non-Linear Data Structures

Question

I'm looking for effective strategies and projects for introducing non-linear data structures to students. I currently teach linked lists, stacks, and then introduce binary trees. A lot of students struggle with the idea that an entire structure is stored in one variable and is not in any particular order (other than infix, prefix etc). The other thing I notice is weak recursion skills tend to spell doom when first trying to learn these data structures and their operations. What are some ways for a struggling student to practice recursion in a meaningful way (projects or tools)? What are some good accompanying algorithms for trees, and eventually self balancing binary trees?

The course focuses on C and is aimed at advanced high school students.

Answer 1

I'm not sure this qualifies as an actual answer, but let me suggest that you give yourself a course in Structural Induction. Perhaps you already know of this, of course. But the main idea is that the processing of a data structure (the method invocations) matches the structure of the data itself.

Thus, for a binary tree, a method processing an internal node (or the root) will make (recursive) calls to the two child nodes, with the recursion ending at a leaf. This is actually how a recursive descent compiler works, with the processing (parsing) exactly following the structure of the language as defined in a (LL) grammar.

One important lesson that you have to teach is that a recursion can do "work" both on the winding phase (before the recursive calls) or after (when they return). That is easily demonstrated with the following code (pseudocode) snippet:

Global s <- 0;
Fun recur x {
    If x > 0 {
        Print x; // winding phase
        recur x - 1;
        s <- s + x;
        Print x; // unwinding phase
    } Else {
        Println;
    }
    return s;
}

Translate that to your favorite language and see what it outputs for a call like recur 10.

For a tree structure that means that you can recurse (twice) before you process the current node, thus having the results of the two recursions available. This is often called "bottom-up" processing. OR, you can work top-down by computing something in the current node and passing it down with the two recursive calls. Bottom-up processing can be used to construct a tree, for example as is often done in optimizing compilers.

As proof of a "deeper" understanding of recursion. Ask the students to write a linear running time function to copy a list. A quadratic function is easy, but linear running time is a bit harder.

---

To teach the winding v unwinding idea I often used a matryoshka. Imagine that you have an unpainted matryoshka (which I do), and you want to "paint" it. You can either "apply colors" before the recursion of "paint" or after, stopping at the innermost doll. You can talk about how messy your fingers get if you do all of the "apply colors" operations on the winding phase, since you have to open a freshly painted doll. A bit weirder, though it demonstrates the point, is that you can "apply colors" to one half on the winding phase and to the other half on the unwinding phase.

As a bridge from linear to tree-like structures, imagine a matryoshka that has two "inner" dolls instead of one for each intermediate doll.

Answer 2

I tried a hybrid of both your suggestions together @Buffy, @Rusi Beginning with induction principle leading to an inductive definition...for lists in haskell.

We began by proving that: $$\sum_{i=0}^n i = \frac{n(n+1)}{2}$$ as learnt in school. Then we dwelt a bit on the process and the structure of numbers and how induction indeed proves our claim. That the process of construction of numbers is (+1) and from here we took a leap to (x:xs) as the process of construction of lists

sum [] = 0
sum (x: xs) = x + magic
              where
                 magic = sum xs

The magic was the induction hypothesis. And we did not simplify the code until this sunk in.

So I never once called it recursion, always induction.

Its been magical! week3 into intro course and the kids are pumping out all kinds of recursive definitions. And now they use the words synonymously!

Answer 3

Is Recursion hard?

Peter Deutsch, the creator of the smalltalk implementation that inspired the Java-jit (and much else), famously said:

To iterate is human, to recurse divine

So you and your struggling students are in august company!

Now let's turn over to math. And not just math but...

Basic school math

Here are two identities

$$ \begin{aligned} a(b+c) &= ab + ac & \text{distributive law} \\ x^{m+n} &= x^m x^n & \text{index law} \end{aligned} $$

I guess everyone will agree that in the context of school math these are unproblematic? Almost trivial?

Lets special-case the above with $c=1$ in the first and $n=1$ in the second and we get $$ \begin{aligned} a(b+1) &= ab + a \\ x^{m+1} &= xx^m \end{aligned} $$

Lets now ponder...

• Are these equations in any way difficult?
• Do you (anyone) find it an issue that they are recursive?
• Does one even notice that they are recursive?

(Assuming that the answer to all the above is no,no,no)
Lets ask now:
Whats this to do with programming?

Well... All we need are base cases, respectively $$a.0 = 0$$ $$x^0 = 1$$

And we get a complete recursive specification for multiplication as repeated addition and exponentiation as repeated multiplication

These can be trivially¹ translated to haskell as

a*(b+1) = a*b + a
a*0     = 0

and

x^(m+1) = x*(x^m)
x^0     = 1

Returning to the Programming world

Ok so you say that this is some math-toy. What's it to do with programming?

An inappropriate pun

In almost all today's programming languages you can write the "statement" i = 1

And in math we write $i = 1$

Doing the first makes the second true; or staying in the programming world, after i = 1 i == 1 becomes true

So what's the big deal? Well programmers also write i = i+1

(Or moral equivalents like i++ i += 1 etc)

So after i = i+1 does i == i+1 ?!

Lets ask our math-respecting executor Haskell:
One can easily enough write

 i = i+1

And no trouble...it seems

But when we ask what is x we get, almost literally, an explosion!

 ? i
 
 ERROR: Control stack overflow

In effect our executor is saying that it got into trouble trying to "solve the equation" $i=i+1$

So is the problem in programming or math??

Mathematicians would almost universally protest at $i=i+1$ as

• wrong
• impossible
• no (finite) solution
• or just plain nonsense
• etc

Clearly if we programmers accept i=i+1 as normal and ok we cannot then expect our programs to respect mathematical concepts.

So it seems we have

An inevitable dilemma: Programming XOR Mathematics

This seems like a very high price to pay!

But there's good news!

A large number of very intelligent people for many decades have thought about the problem and come to a very simple conclusion:

The culprit is assignment

• Once you have assignment, a mathematical semantics of our programming language is a lost cause
• Throw the assignment out of the programming language (and morally equivalent things like mutating data-structures)² and your programming language essentially becomes mathematics

A bit of terminology

• Those who think as above and prefer assignment-free³ languages are typically called functional⁴ programmers
• Languages with assignment are called imperative languages (and from the pov above OO and classic imperative languages are much the same)

Conclusion

So in answer to your explicit statement: My students find recursion hard! and its implied questions: Am I or my students doing something wrong?

The answer is Yes: Using imperative programming in a first programming course ⁵ befuddles their thinking

Or hear Dijkstra's take on this

---

¹ Ok for those who try this in haskell there are some wrinkles -- Ive tested in gofer -- GOod For Equational Reasoning -- a Haskell predecessor which facilitates this kind of playing around better than Haskell

² Mutation is actually much worse than assignment; in fact mutation messes up imperative programming as much as imperative programming messes up mathematics. A brief trailer

³ And sequencing... A story for another day

⁴ "Functional" is actually a misnomer; something like "mathematical" would have been better.

⁵ Imperative programming of course must be taught; if it is done in a later course, there is no unnecessary confusion.

Answer 4

Weak recursion skills are, indeed, the big problem here. I also teach advanced high school students, and over the years, I have found that about 15% of students "get" recursion quite quickly, but I haven't found any shortcuts to getting the other 85% to mastery. Instead, we slog through, using a functional language (Racket) for about 8 weeks. By the end of that time, they are all quite good at recursion; the language demands it.

If I were limiting myself to an imperative language, then I would resign myself first and foremost to the idea that it simply takes time to absorb the norms of recursion. Unfortunately, eight weeks is about right. You can break it down as "base case first, then the recursive case" until you're blue in the face, but it will simply take time and a lot of practice for students who have already gotten quite good at thinking imperatively to be able to switch over to a paradigm so starkly different.

Perhaps have them start by building a linked list of ints, one method at a time. Let them try the given, then show them how to do it. Build append(int), then length(), then find(int), then insert(int, int), then, then, then... you can pick an order based on how you wish to present it all.

You could then follow this up by bringing them back to their very early programming assignments and ask them to redo the assignments, but ban for, while, and goto (assuming you ever let them use that -- yuck!). Tell them that the only way permissible to get a loop structure is to use function calls, and allow them to work in pairs without any sort of penalty if they get themselves right and truly stuck. This will get them used to the mechanics of recursion without having an attendant data structure to also have to learn about.

I'd avoid trees until they are able to build mildly complex programs using recursion, because the cognitive tax of recursion is too high to additionally make sense of the data structure (never mind self-balancing! With how long this all takes, you may decide to forgo that goal for now.)

If you do find any faster ways, please post a self-answer. The only approach I've found is to slog, slog, slog, slog. It takes time, but it works well, and everyone does eventually get quite good at it.

Good luck!

Answer 5

I would probably go with expression trees.

2 + ( 6 * x * 3 )  --->  

         +
       /   \
       2    *
           /  \
           *  3
          / \
         6   x

It demystifies something, it's based on pre-existing knowledge, there are umpteen ways to generate practical exercises and it represents an abstract use of the data type. It's also fun.

Moving on you could look at common sub-expressions as a way of introducing DAGs. The tree traversals have different applications also - e.g. postorder traversal is useful for evaluation.

Sorry, its not a pseudo academic answer oozing with self aggrandising polemic but it seems to fit the tone of your question. Worked well with my lot.