<p>I'm not sure this qualifies as an actual answer, but let me suggest that you give yourself a course in <a href="https://en.wikipedia.org/wiki/Structural_induction" rel="nofollow noreferrer">Structural Induction</a>. 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.</p>
<p>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.</p>
<p>One important lesson that you have to teach is that a recursion can do &quot;work&quot; both on the winding phase (before the recursive calls) or after (when they return). That is easily demonstrated with the following code (pseudocode) snippet:</p>
<pre><code>Global s &lt;- 0;
Fun recur x {
    If x &gt; 0 {
        Print x; // winding phase
        recur x - 1;
        s &lt;- s + x;
        Print x; // unwinding phase
    } Else {
        Println;
    }
    return s;
}
</code></pre>
<p>Translate that to your favorite language and see what it outputs for a call like <code>recur 10</code>.</p>
<p>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 &quot;bottom-up&quot; 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.</p>
<p>As proof of a &quot;deeper&quot; 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.</p>
<hr />
<p>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 &quot;paint&quot; it. You can either &quot;apply colors&quot; before the recursion of &quot;paint&quot; or after, stopping at the innermost doll. You can talk about how messy your fingers get if you do all of the &quot;apply colors&quot; 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 &quot;apply colors&quot; to one half on the winding phase and to the other half on the unwinding phase.</p>
<p>As a bridge from linear to tree-like structures, imagine a matryoshka that has two &quot;inner&quot; dolls instead of one for each intermediate doll.</p>

CC BY-SA 4.0
2020-10-05T00:16:44.127Z
The Russian Doll image is very good, and even better the image of getting paint all over your fingers from trying to do the steps in the 'wrong' order. Coming up with the correct and elegant solution is extremely satisfying, and is what makes programming worthwhile.
Scott Rowe
CC BY-SA 4.0
2020-11-27T23:02:26.603Z
This answer simply does not address the question. Your knowledge of LL(n) compiler semantics is not appropriate material for a *high school* class where the poor teacher has learners that 'find it hard to understand that a whole structure can be stored in one variable'.
Jon Guiton
CC BY-SA 4.0
2020-11-27T23:10:33.060Z
@JonGuiton, actually, the point was that the OP needs to review structural induction and understand it deeply, not that they should teach a compiler course. And, I flagged it myself as a not-answer. It is only a path to find an answer.
Buffy
CC BY-SA 4.0
2020-11-27T23:30:44.943Z
Beg to differ, but *first time learners* in a *high school* where some students find the idea of compound variables tricky do *not* need to review structural induction any more than first time automotive maintenance students need to deeply understand hydrocarbon oxidation theory. It is much more helpful for teaching staff if answers address audience needs and contain practical teaching aids at the appropriate level e.g. examples actually written in C would be useful for a teacher teaching data-structures in C.
Jon Guiton
CC BY-SA 4.0
2020-11-27T23:32:16.360Z
i.e. which do not use functional programming paradigms with global variables - what kind of example is that setting?
Jon Guiton
CC BY-SA 4.0
2020-09-26T12:00:25.483Z
2020-09-27T10:19:16.220Z
2020-09-27T10:19:16.220Z
Buffy
<p>I tried a hybrid of both your suggestions together @Buffy, @Rusi
Beginning with induction principle leading to an inductive definition...for lists in haskell.</p>
<p>We began by proving that:
<span class="math-container">$$\sum_{i=0}^n i = \frac{n(n+1)}{2}$$</span> 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</p>
<pre><code>sum [] = 0
sum (x: xs) = x + magic
              where
                 magic = sum xs
</code></pre>
<p>The <strong>magic</strong> was the induction hypothesis. And we did not simplify the code until this sunk in.</p>
<p>So I never once called it recursion, always induction.</p>
<p>Its been <strong>magic</strong>al! week3 into intro course and the kids are pumping out all kinds of recursive definitions. And now they use the words synonymously!</p>

CC BY-SA 4.0
2020-09-27T17:32:18.037Z
There seems to be a spurious backquote (‛)  in your sum definition. And yes, @buffy suggestion toward structural induction is spot on. I meant to say that but we ended up somewheres...else
Rushi
CC BY-SA 4.0
2020-09-27T17:38:03.120Z
spurious backquote fixed
Anuradha
CC BY-SA 4.0
2020-09-28T04:31:11.350Z
And thanks for reminding me that the beauty of Tex math works on this site — my answer changed accordingly. Seemingly irrelevant but actually germane to the point that recursion becomes easy to the extent that programming becomes math
Rushi
CC BY-SA 4.0
2020-11-27T23:06:28.713Z
I have to ask how this is an answer to the question about teaching tree data structures in a high school.
Jon Guiton
CC BY-SA 4.0
2021-02-14T15:59:42.203Z
A senior CMU Prof makes a similar point: https://existentialtype.wordpress.com/2011/04/12/a-dead-dog/ and https://existentialtype.wordpress.com/2011/03/21/the-dog-that-didnt-bark/
Rushi
CC BY-SA 4.0
2020-09-27T17:02:26.060Z
2020-09-27T17:36:52.940Z
2020-09-27T17:36:52.940Z
Anuradha

<h1>Is Recursion hard?</h1>
<p><a href="https://en.wikipedia.org/wiki/L._Peter_Deutsch" rel="nofollow noreferrer">Peter Deutsch</a>, the creator of the smalltalk implementation that inspired the Java-jit (and much else), famously said:</p>
<blockquote>
<p>To iterate is human, to recurse divine</p>
</blockquote>
<p>So you and your struggling students are in august company!</p>
<p>Now let's turn over to math. And not just math but...</p>
<h1>Basic school math</h1>
<p>Here are two identities</p>
<p><span class="math-container">$$
\begin{aligned}
a(b+c)  &amp;= ab + ac &amp; \text{distributive law} \\
x^{m+n} &amp;= x^m x^n &amp; \text{index law}
\end{aligned}
$$</span></p>
<p>I guess everyone will agree that <em>in the context of school math</em> these are
unproblematic? Almost trivial?</p>
<p>Lets special-case the above with <span class="math-container">$c=1$</span> in the first and <span class="math-container">$n=1$</span> in the second and we get
<span class="math-container">$$
\begin{aligned}
a(b+1) &amp;= ab + a \\
x^{m+1} &amp;= xx^m
\end{aligned}
$$</span></p>
<p>Lets now ponder...</p>
<ul>
<li>Are these equations in any way difficult?</li>
<li>Do you (anyone) find it an issue that they are recursive?</li>
<li>Does one even <strong>notice</strong> that they are recursive?</li>
</ul>
<p>(Assuming that the answer to all the above is no,no,no)<br />
Lets ask now:<br />
Whats this to do with programming?</p>
<p>Well... All we need are base cases, respectively
<span class="math-container">$$a.0 = 0$$</span>
<span class="math-container">$$x^0 = 1$$</span></p>
<p>And we get a complete recursive specification for multiplication as repeated addition and exponentiation as repeated multiplication</p>
<p>These can be trivially<sup>1</sup> translated to haskell as</p>
<pre class="lang-none prettyprint-override"><code>a*(b+1) = a*b + a
a*0     = 0
</code></pre>
<p>and</p>
<pre class="lang-none prettyprint-override"><code>x^(m+1) = x*(x^m)
x^0     = 1
</code></pre>
<h1>Returning to the Programming world</h1>
<p>Ok so you say that this is some math-toy. What's it to do with programming?</p>
<h1>An inappropriate pun</h1>
<p>In almost all today's programming languages you can write the &quot;statement&quot;
<code>i = 1</code></p>
<p>And in math we write <span class="math-container">$i = 1$</span></p>
<p>Doing the first makes the second true; or staying in the programming world, after <code>i = 1</code>
<code>i == 1</code>
becomes true</p>
<p>So what's the big deal?
Well programmers also write
<code>i = i+1</code></p>
<p>(Or moral equivalents like <code>i++</code> <code>i += 1</code> etc)</p>
<p>So after <code>i = i+1</code> does <code>i == i+1</code> ?!</p>
<p>Lets ask our math-respecting executor Haskell:<br />
One can easily enough <em>write</em></p>
<pre class="lang-none prettyprint-override"><code> i = i+1
</code></pre>
<p>And no trouble...it seems</p>
<p>But when we ask what is <code>x</code> we get, almost literally, an explosion!</p>
<pre class="lang-none prettyprint-override"><code> ? i
 
 ERROR: Control stack overflow
</code></pre>
<p>In effect our executor is saying that it got into trouble trying to &quot;solve the equation&quot; <span class="math-container">$i=i+1$</span></p>
<h1>So is the problem in programming or math??</h1>
<p><strong>Mathematicians</strong> would almost universally protest at <span class="math-container">$i=i+1$</span> as</p>
<ul>
<li>wrong</li>
<li>impossible</li>
<li>no (finite) solution</li>
<li>or just plain nonsense</li>
<li>etc</li>
</ul>
<p>Clearly if we <strong>programmers</strong> accept <code>i=i+1</code> as normal and ok we cannot then expect our <strong>programs</strong> to respect <strong>mathematical</strong> concepts.</p>
<p>So it seems we have</p>
<h1>An inevitable dilemma: Programming XOR Mathematics</h1>
<p>This seems like a very high price to pay!</p>
<p>But there's good news!</p>
<p>A large number of very intelligent people for many decades have thought about the problem and come to a very simple conclusion:</p>
<h1>The culprit is assignment</h1>
<ul>
<li>Once you have assignment, a mathematical semantics of our programming language is a lost cause</li>
<li>Throw the assignment out of the programming language (and morally equivalent things like mutating data-structures)<sup>2</sup> and your programming language essentially becomes mathematics</li>
</ul>
<h1>A bit of terminology</h1>
<ul>
<li>Those who think as above and prefer assignment-free<sup>3</sup> languages are typically called <em>functional<sup>4</sup> programmers</em></li>
<li>Languages with assignment are called <em>imperative languages</em> (and from the pov above OO and classic imperative languages are much the same)</li>
</ul>
<h1>Conclusion</h1>
<p>So in answer to your explicit statement: <em>My students find recursion hard!</em> and its implied questions: <em>Am I or my students doing something wrong?</em></p>
<p>The answer is Yes: Using imperative programming in a first programming course
<sup>5</sup> befuddles their thinking</p>
<p>Or hear <a href="https://www.cs.utexas.edu/users/EWD/OtherDocs/To%20the%20Budget%20Council%20concerning%20Haskell.pdf" rel="nofollow noreferrer">Dijkstra's take</a> on this</p>
<hr />
<p><sup>1</sup> Ok for those who try this in haskell there are some wrinkles -- Ive tested in <a href="https://en.m.wikipedia.org/wiki/Gofer_(programming_language)" rel="nofollow noreferrer">gofer</a>
-- <strong>GO</strong>od <strong>F</strong>or <strong>E</strong>quational <strong>R</strong>easoning -- a Haskell predecessor which facilitates this kind of playing around better than Haskell</p>
<p><sup>2</sup> Mutation is actually much worse than assignment; in fact mutation messes up imperative programming as much as imperative programming messes up mathematics. A <a href="https://cseducators.stackexchange.com/a/6567/8837">brief trailer</a></p>
<p><sup>3</sup> And sequencing... A story for another day</p>
<p><sup>4</sup> &quot;Functional&quot; is actually a misnomer; something like &quot;mathematical&quot; would have been better.</p>
<p><sup>5</sup> Imperative programming of course must be taught; if it is done in a later course, there is no unnecessary confusion.</p>

CC BY-SA 4.0
2020-09-27T15:20:42.190Z
Why the insulting tone? Can you make your point otherwise? Note also that the language of instruction may not be up to the instructor or the OP here.
Buffy
CC BY-SA 4.0
2020-09-27T15:28:22.123Z
@buffy I changed the "you" to "I" in last para. (I actually don't understand all the versions!) Does that help? Or were you thinking of the other question https://cseducators.stackexchange.com/a/6567/8837
Rushi
CC BY-SA 4.0
2020-09-27T15:33:03.530Z
Your comments about the teacher and the students in the "warning" section are not called for.
Buffy
CC BY-SA 4.0
2020-09-27T15:44:19.860Z
@buffy i think there's a communication problem here. I really mean the order is reversed (typically). And the innocent party — student or teacher — is punished for an inept medium of instruction. Anyways... I've made the order more explicit and toned down the epithets. Hope that helps!
Rushi
CC BY-SA 4.0
2020-09-27T15:53:40.107Z
Do you teach? Do you think of your students as dumb?
Buffy
CC BY-SA 4.0
2020-09-27T15:59:07.663Z
@buffy
«medium of instruction not a choice» In 1990 I taught a bit of functional approach (scheme) in the discrete math course (the parallel C-based course was proceeding disastrously) In 1991 (thanks to the disaster!) I was allowed to teach the 1st programming course on the condition that minimum C was delivered at end. So I taught Haskellish gofer. It went quite a bit better. So there is always some degree of freedom.
Rushi
CC BY-SA 4.0
2020-09-27T16:00:24.623Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/113445/discussion-between-rusi-and-buffy).
Rushi
CC BY-SA 4.0
2020-10-05T00:20:25.543Z
I am so perplexed that anyone thinks that programming has anything whatsoever to do with math. This seems like a fundamental error in conception that really should be sorted out. I've been programming for 40 years and never had any more complex math to do that managing a circular buffer that allows push and pop (like 'unreading' something). What's with all the math references? I have recently written some SQL statements that would curl your hair, no Math required, Set Theory was nowhere in sight. Someone got the whole study of programming off on the wrong foot with this math stuff.
Scott Rowe
CC BY-SA 4.0
2020-10-05T04:06:17.423Z
@ScottRowe «I wrote some SQL that would curl your hair... No math, No Set Theory» [Check again!](https://en.m.wikipedia.org/wiki/Tuple_relational_calculus) 
AFAIC SQL is bog standard [modern-math set theory](https://en.m.wikipedia.org/wiki/Set-builder_notation) 
with COBOL syntax. And no offence to COBOL. The key phrase here is that [SQL is a declarative language](https://en.m.wikipedia.org/wiki/SQL) 
which AFAIC is CS-ese for saying SQL is math! We could continue but as Fermat said 4 centuries ago: «The comment section of SE is too narrow». Seriously:we could continue elsewhere, maybe meta
Rushi
CC BY-SA 4.0
2020-10-05T10:35:07.670Z
How much thought did you give to grammar, phonetics and word origins while writing your last comment? But what else is written language than those, eh? It takes solving differential equations to balance on a bicycle, or even just stand on one foot. Yet, a bear can ride a bicycle. We have to get over this rubbish that programming is in any way related to math, just like talking is in any way related to the study of language, or biology is chemistry, or psychology is 'just' operant conditioning. These are degenerate thought-functioning, as in: "a point is a degenerate circle".
Scott Rowe
CC BY-SA 4.0
2020-10-05T10:42:43.807Z
@ScottRowe I showed 3 pianists [here](https://cseducators.stackexchange.com/a/6164/8837). Putting the first aside do you think the other two just magically play the notes? Or do they know some music theory? And if you do answer the first question as "yes" then graduate from these pianists to the composers they're playing. Put simply: Do you imagine they could write the music without knowing music? OTOH I don't believe that expert musicians "think their theory" while performing or ultimately even composing. I think we're about 1-2 hundred years away from that in programming
Rushi
CC BY-SA 4.0
2020-10-05T16:18:21.770Z
"*In theory, there is no difference between Theory and Practice. In practice, there is.*" -- Yogi Berra
Scott Rowe
CC BY-SA 4.0
2020-11-27T23:09:06.730Z
Your article on the meta-semantics of the assignment operator and how good you are at finding quotes from Dijkstra on Google doesn't actually answer the question asked.
Jon Guiton
CC BY-SA 4.0
2021-08-31T08:15:24.033Z
I don't see anything rude about his post. But I don't see correction as an insult. I do worry about the word maths. Many people associate this with school/arithmetic/etc. If you see maths to mean a language, then non-mathematical just means ungrammatical nonsense. Functional (mathematical) programs describe **what** is to be done. Imperative programs describe **how** to do it (leaving you in the dark about **what** it is that is being done).
ctrl-alt-delor
CC BY-SA 4.0
2020-09-27T14:01:51.957Z
2020-11-01T15:24:54.257Z
2020-11-01T15:24:54.257Z
Rushi
<p>I would probably go with expression trees.</p>
<pre><code>2 + ( 6 * x * 3 )  ---&gt;  

         +
       /   \
       2    *
           /  \
           *  3
          / \
         6   x
</code></pre>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2020-11-27T22:57:41.490Z
2020-11-28T21:30:35.200Z
2020-11-28T21:30:35.200Z
Jon Guiton
<p>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 &quot;get&quot; 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.</p>
<p>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 &quot;base case first, then the recursive case&quot; until you're blue in the face, but it will simply take time and a lot of practice for students who have <em>already</em> gotten quite good at thinking imperatively to be able to switch over to a paradigm so starkly different.</p>
<p>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 <code>append(int)</code>, then <code>length()</code>, then <code>find(int)</code>, then <code>insert(int, int)</code>, then, then, then... you can pick an order based on how you wish to present it all.</p>
<p>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 <code>for</code>, <code>while</code>, and <code>goto</code> (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.</p>
<p>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.)</p>
<p>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.</p>
<p>Good luck!</p>

CC BY-SA 4.0
2020-10-05T00:24:41.633Z
People only understand something they have 'learned' after a night of sleep. I guess it takes about 40 days (and more importantly, 40 *nights*) to learn some things. That is just part of being human, no shortcuts available. Can't tell you how many times I stared dumbfounded at a programming problem one day, and the next morning sat down and polished it off. Naps should be required in programming. Having kids stop taking naps after Kindergarten is really a failure of the educational system. College is great because there is very flexible sleep time.
Scott Rowe
CC BY-SA 4.0
2020-09-26T03:52:19.833Z
2020-09-26T12:22:14.077Z
2020-09-26T12:22:14.077Z
Ben I.
<p>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?</p>
<p>The course focuses on C and is aimed at advanced high school students.</p>

CC BY-SA 4.0
2020-10-05T00:14:34.150Z
I'm not sure that I understand the statement "*the idea that an entire structure is stored in one variable*"... You mean that a pointer to the root is stored in one variable? Otherwise it would be like saying that my entire earnings history is stored in my Social Security Number. Yes? Do students know that a variable is just a memory location that holds something? That the something could be "the address of *another* memory location"? Yes? Without that knowledge, I wonder at how they would understand recursion or anything else in programming.
Scott Rowe
CC BY-SA 4.0
2020-10-05T15:47:52.303Z
Yes they know what a variable really is, I didn't want to waste words.  What I meant by that comment is that they struggle with accessing a data structure through one variable (memory location storing other memory locations).  Their pointer skills are adequate for how long they've been practicing, recursion is a different story.
guitarcat
CC BY-SA 4.0
2020-10-15T16:37:37.217Z
When I learned about linked data structures, I had the advantage (?) of having to hand in assignments written in a computer language that had neither pointer types, nor reference types. The links in my data structures were integer _indices_ into statically allocated arrays of records. Learning how to use pointers later on was almost painless: It was easy to think of them as just integer indices into a big array called "memory."
Solomon Slow
<secondary-education><algorithms><data-structure><c>
First Time Learning Non-Linear Data Structures
# First Time Learning Non-Linear Data Structures

(Asked by: username_0 on 2020-09-25)

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.

**Tags:** secondary-education, algorithms, data-structure, c

> **Comments:**
> **username_1**: I'm not sure that I understand the statement "*the idea that an entire structure is stored in one variable*"... You mean that a pointer to the root is stored in one variable? Otherwise it would be like saying that my entire earnings history is stored in my Social Security Number. Yes? Do students know that a variable is just a memory location that holds something? That the something could be "the address of *another* memory location"? Yes? Without that knowledge, I wonder at how they would understand recursion or anything else in programming.  
> **username_0**: Yes they know what a variable really is, I didn't want to waste words.  What I meant by that comment is that they struggle with accessing a data structure through one variable (memory location storing other memory locations).  Their pointer skills are adequate for how long they've been practicing, recursion is a different story.  
> **username_2**: When I learned about linked data structures, I had the advantage (?) of having to hand in assignments written in a computer language that had neither pointer types, nor reference types. The links in my data structures were integer _indices_ into statically allocated arrays of records. Learning how to use pointers later on was almost painless: It was easy to think of them as just integer indices into a big array called "memory."  

---

## 5 answers

### Answer by username_3 on 2020-09-26. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_1**: The Russian Doll image is very good, and even better the image of getting paint all over your fingers from trying to do the steps in the 'wrong' order. Coming up with the correct and elegant solution is extremely satisfying, and is what makes programming worthwhile.  
> **username_4**: This answer simply does not address the question. Your knowledge of LL(n) compiler semantics is not appropriate material for a *high school* class where the poor teacher has learners that 'find it hard to understand that a whole structure can be stored in one variable'.  
> **username_3**: @JonGuiton, actually, the point was that the OP needs to review structural induction and understand it deeply, not that they should teach a compiler course. And, I flagged it myself as a not-answer. It is only a path to find an answer.  
> **username_4**: Beg to differ, but *first time learners* in a *high school* where some students find the idea of compound variables tricky do *not* need to review structural induction any more than first time automotive maintenance students need to deeply understand hydrocarbon oxidation theory. It is much more helpful for teaching staff if answers address audience needs and contain practical teaching aids at the appropriate level e.g. examples actually written in C would be useful for a teacher teaching data-structures in C.  
> **username_4**: i.e. which do not use functional programming paradigms with global variables - what kind of example is that setting?  

---

### Answer by username_5 on 2020-09-27. Score: 3

I tried a hybrid of both your suggestions together @username_3, @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!

> **Comments:**
> **username_6**: There seems to be a spurious backquote (‛)  in your sum definition. And yes, @buffy suggestion toward structural induction is spot on. I meant to say that but we ended up somewheres...else  
> **username_5**: spurious backquote fixed  
> **username_6**: And thanks for reminding me that the beauty of Tex math works on this site — my answer changed accordingly. Seemingly irrelevant but actually germane to the point that recursion becomes easy to the extent that programming becomes math  
> **username_4**: I have to ask how this is an answer to the question about teaching tree data structures in a high school.  
> **username_6**: A senior CMU Prof makes a similar point: https://existentialtype.wordpress.com/2011/04/12/a-dead-dog/ and https://existentialtype.wordpress.com/2011/03/21/the-dog-that-didnt-bark/  

---

### Answer by username_6 on 2020-09-27. Score: 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 trivially1 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)2 and your programming language essentially becomes mathematics

A bit of terminology

Those who think as above and prefer assignment-free3 languages are typically called functional4 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
5 befuddles their thinking
Or hear Dijkstra's take on this

1 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
2 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
3 And sequencing... A story for another day
4 "Functional" is actually a misnomer; something like "mathematical" would have been better.
5 Imperative programming of course must be taught; if it is done in a later course, there is no unnecessary confusion.

> **Comments:**
> **username_3**: Why the insulting tone? Can you make your point otherwise? Note also that the language of instruction may not be up to the instructor or the OP here.  
> **username_6**: @buffy I changed the "you" to "I" in last para. (I actually don't understand all the versions!) Does that help? Or were you thinking of the other question https://cseducators.stackexchange.com/a/6567/8837  
> **username_3**: Your comments about the teacher and the students in the "warning" section are not called for.  
> **username_6**: @buffy i think there's a communication problem here. I really mean the order is reversed (typically). And the innocent party — student or teacher — is punished for an inept medium of instruction. Anyways... I've made the order more explicit and toned down the epithets. Hope that helps!  
> **username_3**: Do you teach? Do you think of your students as dumb?  
> **username_6**: @buffy «medium of instruction not a choice» In 1990 I taught a bit of functional approach (scheme) in the discrete math course (the parallel C-based course was proceeding disastrously) In 1991 (thanks to the disaster!) I was allowed to teach the 1st programming course on the condition that minimum C was delivered at end. So I taught Haskellish gofer. It went quite a bit better. So there is always some degree of freedom.  
> **username_6**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/113445/discussion-between-rusi-and-buffy).  
> **username_1**: I am so perplexed that anyone thinks that programming has anything whatsoever to do with math. This seems like a fundamental error in conception that really should be sorted out. I've been programming for 40 years and never had any more complex math to do that managing a circular buffer that allows push and pop (like 'unreading' something). What's with all the math references? I have recently written some SQL statements that would curl your hair, no Math required, Set Theory was nowhere in sight. Someone got the whole study of programming off on the wrong foot with this math stuff.  
> **username_6**: @ScottRowe «I wrote some SQL that would curl your hair... No math, No Set Theory» [Check again!](https://en.m.wikipedia.org/wiki/Tuple_relational_calculus)  AFAIC SQL is bog standard [modern-math set theory](https://en.m.wikipedia.org/wiki/Set-builder_notation)  with COBOL syntax. And no offence to COBOL. The key phrase here is that [SQL is a declarative language](https://en.m.wikipedia.org/wiki/SQL)  which AFAIC is CS-ese for saying SQL is math! We could continue but as Fermat said 4 centuries ago: «The comment section of SE is too narrow». Seriously:we could continue elsewhere, maybe meta  
> **username_1**: How much thought did you give to grammar, phonetics and word origins while writing your last comment? But what else is written language than those, eh? It takes solving differential equations to balance on a bicycle, or even just stand on one foot. Yet, a bear can ride a bicycle. We have to get over this rubbish that programming is in any way related to math, just like talking is in any way related to the study of language, or biology is chemistry, or psychology is 'just' operant conditioning. These are degenerate thought-functioning, as in: "a point is a degenerate circle".  
> **username_6**: @ScottRowe I showed 3 pianists [here](https://cseducators.stackexchange.com/a/6164/8837). Putting the first aside do you think the other two just magically play the notes? Or do they know some music theory? And if you do answer the first question as "yes" then graduate from these pianists to the composers they're playing. Put simply: Do you imagine they could write the music without knowing music? OTOH I don't believe that expert musicians "think their theory" while performing or ultimately even composing. I think we're about 1-2 hundred years away from that in programming  
> **username_1**: "*In theory, there is no difference between Theory and Practice. In practice, there is.*" -- Yogi Berra  
> **username_4**: Your article on the meta-semantics of the assignment operator and how good you are at finding quotes from Dijkstra on Google doesn't actually answer the question asked.  
> **username_7**: I don't see anything rude about his post. But I don't see correction as an insult. I do worry about the word maths. Many people associate this with school/arithmetic/etc. If you see maths to mean a language, then non-mathematical just means ungrammatical nonsense. Functional (mathematical) programs describe **what** is to be done. Imperative programs describe **how** to do it (leaving you in the dark about **what** it is that is being done).  

---

### Answer by username_4 on 2020-11-27. Score: 2

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.


---

### Answer by username_8 on 2020-09-26. Score: 2

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!

> **Comments:**
> **username_1**: People only understand something they have 'learned' after a night of sleep. I guess it takes about 40 days (and more importantly, 40 *nights*) to learn some things. That is just part of being human, no shortcuts available. Can't tell you how many times I stared dumbfounded at a programming problem one day, and the next morning sat down and polished it off. Naps should be required in programming. Having kids stop taking naps after Kindergarten is really a failure of the educational system. College is great because there is very flexible sleep time.  

---

