<p>Several answers have said things like "We need recursion to handle tree structures." The problem with this type of answer is that the student then asks "Why would we have a tree structure in the first place?"</p>

<p>@Syndic's example of handling directories with subdirectories is probably the best answer, but there are others.</p>

<p>My favorite example where recursion feels natural is <strong>Parsing</strong>.  For many parsing tasks, a <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">recursive descent parser</a> is the easiest approach to take.  </p>

<p>For example, parsing <a href="https://en.wikipedia.org/wiki/JSON" rel="nofollow noreferrer">JSON</a>:</p>

<p>The top level will something like <code>ParseItem</code>, a function that takes an input stream and returns an data item corresponding to the JSON found there.</p>

<p>This function looks at the first characer to find out what type of item it  should parse.  Depending on this, it will call <code>ParseObject</code>, <code>ParseNumber</code>, <code>ParseArray</code>, <code>ParseString</code> or whatever.</p>

<p>Now, <code>ParseArray</code> will set up an array and starts parsing items to fill it with.  How does it do that?  Why, it calls <code>ParseItem</code>!  Recursion!</p>

CC BY-SA 3.0
2018-01-15T13:14:29.787Z
Thank you for coming back to improve your answer! I hope that you'll continue to share your knowledge here at [cseducators.se].
thesecretmaster
CC BY-SA 4.0
2018-11-14T21:20:24.643Z
Whatever language they are *coding* in, their understanding/definition of *it* is recursive.
philipxy
CC BY-SA 3.0
2018-01-11T08:52:23.580Z
2018-01-15T08:38:06.440Z
2018-01-15T08:38:06.440Z
Stig Hemmer
<p>Operating on the key word, <strong>motivate</strong>, I do believe that <a href="/users/2037/andrew-t" title="Andrew T.'s profile">Andrew T.</a> had the best choice with <a href="//en.wikipedia.org/wiki/Tower_of_Hanoi#Solution" rel="nofollow noreferrer">Tower of Hanoi</a>. Yes, it's an old one, and it does not lead to anything useful once it's done, (the code is not reusable for some other &quot;real world&quot; problem.) Yet it remains a classic for some reason. I'm going to speculate that the reason is that when presented properly it <em>motivates</em> the students to think about using recursion for other purposes. As to what the <em>motivation</em> is - simple: less work! AKA - unmitigated self-interest. Who doesn't like the idea of getting something done fast and easy, preferring instead to do it the long and hard way while getting the exact same results? That suggests that the <em>motivation</em> comes from the presentation, not from the example used.</p>
<p>With the <a href="//en.wikipedia.org/wiki/Tower_of_Hanoi#Solution" rel="nofollow noreferrer">Tower of Hanoi</a> example, adding in the &quot;legend&quot; of the back story can help with interest, but it can also be a waste of classroom time. Using the legend, or not, is a judgment call for your class and your style. (I have encountered at least three versions of the legend, and I am partial to the version that mentions the walls of the temple crumbling into dust and the world vanishing.)</p>
<p>The key to the presentation is to begin with solving it using an iterative approach. Preferably even before you raise the idea of recursion, leaving the <em>alternative</em> as a way out of the maze later. In a comment, <a href="/users/2806/eric-lippert" title="Eric Lippert's profile">Eric Lippert</a> states that it is easier to solve with an iterative algorithm using these steps and rules: &quot;number the disks in order of size; never move a larger disk onto a smaller disk, never move an odd disk onto an odd disk or an even disk onto an even disk, and never move the same disk twice in a row.&quot; That sounds good, and you can present it, just as given, in the classroom. Before trying to code it, however, give it a try physically. Using that rule-set with 5 disks I get the following:</p>
<ul>
<li>Only disk available is 1, move 1 from A to B.</li>
<li>Disks 1 and 2 are available, just moved 1 so only 2 is left. It cannot go on top of 1 (reverse sizes) so move 2 from A to C.</li>
<li>Disks 1, 2, and 3 are now available. 2 just moved, and 3 cannot go on top of 1 (reverse sizes) or 2 (reverse sizes), so 1 must move. 1 cannot go on 3 (odd on odd), so move 1 from B to C.</li>
<li>Disks 1 and 3 are available. Disk 1 just moved so we must move 3. It cannot go on 1 (reverse sizes) so move 3 from A to B.</li>
<li>Disks 1, 3 and 4 are available. Disk 3 just moved, so only 1 and 4 can move. 4 cannot go anywhere (reverse sizes) so 1 moves. 1 cannot go on 3 (odd on odd), so move 1 from C to A.</li>
<li>Disks 1, 2, and 3 are available. 1 just moved, 3 cannot go anywhere (reverse sizes) so 2 moves. 2 cannot go on 1 (reverse sizes), so move 2 from C to B.</li>
<li>Disks 1 and 2 are available. 2 just moved, so 1 is next. 1 Can go on top of 2, OR to the empty post.</li>
</ul>
<p>The given rules offer no guidance for the next move, and computers <em>must</em> have rules to follow.</p>
<p>There is another iterative approach, which does work for creating an algorithm. It has a setup rule, a movement rule and a cycle to repeat. The puzzle usually does not give the arrangement of the posts, only that there are three of them. It is commonly displayed, or presented, with the posts being in a straight line. It can, however, be presented as an arrangement of three posts in a triangular formation, like the image below. In either case, working this iterative approach needs to treat the set of posts as a <em>wrap-around</em> collection, being able to move between the posts infinitely in either direction. The triangular formation makes that easier to visualize than the linear formation.</p>
<p><img src="https://i.sstatic.net/UucJf.jpg" alt="triangular Hanoi puzzle" /></p>
<p>If we consider the top-left as post &quot;A&quot; (the source post), the top-right as post &quot;B&quot; (the target post), and the bottom-center as post &quot;C&quot; (the working post), then the setup rule is:</p>
<blockquote>
<p>For an odd number of disks, the smallest disk moves clockwise, and for an even number of disks the smallest disk moves counter-clockwise.</p>
</blockquote>
<p>The movement rule is:</p>
<blockquote>
<p>With the disks numbered from smallest, as zero, to largest, disks with an even parity <em>always</em> move the same direction as the smallest disk, and disks with an odd parity <em>always</em> move in the reverse direction.</p>
</blockquote>
<p>Finally, the cycle for the moves is:</p>
<blockquote>
<ol>
<li>Move the smallest disk.
2. Move the only other &quot;legal&quot; move.</li>
</ol>
</blockquote>
<p>Using that two-move cycle, following the movement rule, will solve the puzzle in the smallest possible set of moves. Performing that in class with a 6-disk set shouldn't take very long (about 90 seconds without commentary, 2 or 3 minutes with decision commentary). Especially true if you have previously labeled the disks with their numbers, and marked them in some fashion to show which way they move so that you don't get confused during the demonstration. (Overheads, projector, or animation on screen works as well, but physical objects may have an enhanced long-term effect.)</p>
<p>Now, you have the students primed to learn the power of recursion. The rules for the iterative solution are <em>oh, so simple</em>. Turning those rules into an actual no-fail algorithm, with decisions mapped out, is not so simple after all. As humans, we can see, instantly, where the smallest disk is, which disks are able to move, and almost instantly reject the illegal moves when there are two open disks at the same time. Setting all that human ability into formal codified logic that can be followed blindly and achieve the desired result turns out to be <em>much</em> more difficult than it sounds.</p>
<p>Having not dealt with Hanoi since the middle 1980s, I think I can consider myself as having an almost <em>fresh</em> perspective on the problem. Trying to codify the algorithm for the above rules took up quite a bit of my spare time. I cannot put an amount of clock time to it since it was a &quot;between-times&quot; progress when other issues weren't pressing. Still, it took me the better part of a day to be confident in my algorithm and put it into code. With that in mind, I'm not sure if you should task the students with converting the above rules into a formal algorithm or not. Perhaps you can walk the class through developing one or two of the decisions within the algorithm to give them a sense of the work involved.</p>
<p>The main objective of the presentation up to this point is to help them to see, or experience, how much effort goes into creating the solution using the coding skills they have. Then they are ready to see the power that recursion can give them when the situation is right. Re-address the Hanoi puzzle to show that is can be reduced to a collection of smaller sub-problems that are the same as the original problem, except for size. Any solution that works for the main problem also works for the smaller sub-problems, and any solution that works for the smaller sub-problems also works for the main problem. Use that recognition to design a recursive approach to the solution. Hopefully, the amount of time spent finding the (un-coded) recursive solution is nearly the same as was spent finding the (un-coded) iterative solution, showing that finding the basics for the solution is pretty much the same for either approach. Then the magic happens when the un-coded recursive solution is written into pseudo code, or live code in the chosen language. If you have a coded version of the iterative solution to present, and then they write, or are shown, the recursive solution, they will see that dozens of lines have been reduced to about a dozen (depending on the language used). Reduced lines, with simpler logic means less typing, less chance for bugs and errors, and less work for them.</p>
<p>Once they see the benefits of recursion, you can also deliver the caveats (with examples if you have them) which includes:</p>
<ul>
<li>The recursive solution may <em>not be</em> the shortest</li>
<li>The recursive solution may <em>not be</em> the fastest</li>
<li>A recursive solution may <em>not</em> exist for a given problem</li>
<li>A recursive solution might take <em>longer</em> to create than an iterative vesrion</li>
<li>Recursive solutions <em>can</em> create issues with the stack, and memory management</li>
<li>Recursion is not, by itself, faster or slower, than iteration</li>
<li>Recursion has to have the base case built in to the model, there is no outside decision maker</li>
</ul>
<hr />
<p>This is also a case where the recursive solution is faster, significantly, than the iterative solution. Running a series of time trials, with the output comment out and disk count set to 25 (33,554,431 moves), the iterative solution averaged 1m22.4s and the recursive solution averaged 0m28.4s.</p>
<p>Granted, my code is in Perl, and most of your classes are in Java, C++, or a functional language, so it would have to be converted for use in your languages. I took advantage of a few of the patterns inherent in the puzzle solution, and stated the &quot;tricks&quot; used in the comments. I did not, however, try for serious optimization or other forms of code cleaning. In spite of that, this is the final version of a tested, and timed, version of the Hanoi puzzle using an iterative approach:</p>
<pre class="lang-perl prettyprint-override"><code>#!/usr/bin/perl
use strict;
use warnings;
use 5.10.0;
my $disks = 20; # How many disks to use for the game.
sub move_tower_iterative { # (height of tower, souce post, destination post, spare post)
    my ($height, @names) = @_; # Collect the parameters
    my @posts =  ([reverse (0 .. $height-1)], [], []); # The post, to track the state of the game
    my $rotation = ($height % 2)? 1 : -1; # Direction the smallest disk moves
        # 1 is source -&gt; destination -&gt; spare -&gt; source ...
        # -1 is source -&gt; spare -&gt; destination -&gt; source ...
    my ($disk, $from, $to) = (0) x 2; # Temporary data, pre-loaded for the first move
    do {
        # Figure out where the disk to be moved will go
        $to = ($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3;
        # Take the disk off the top of one post
        $disk = pop $posts[$from];
        # Add it to the top of the other post
        push $posts[$to], $disk;
        # Say what we did
        printf &quot;\tMove disk from %s to %s\n&quot;, $names[$from], $names[$to];
        # Find the next legal move
        if ( 0 != $posts[$to][-1] ) { # Was the smallest disk NOT the last move? Then move it.
            # It will be found where the just moved disk would move to, if it was to move again.
            $from = ($to + $rotation * (($posts[$to][-1] % 2)? -1 : 1) + 3) % 3;
        }
        else { # Not moving the smallest disk means finding the one other legal move
            while ( # Starting with the same post we just moved from check if ...
                    ( -1 == $#{$posts[$from]} ) # The post is empty 
                    || ( # OR both
                        ( -1 != $#{@posts[($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3]} ) # The destination post is not empty
                        &amp;&amp; ($posts[$from][-1] &gt; $posts[($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3][-1]) # AND has a smaller disk
                    )
                    || ( # OR both
                        ( 0 == $posts[$from][-1]) # The post has the smallest disk
                        &amp;&amp; ($#{$posts[$from]} != $height-1) # AND the post is not full
                    )
            ) { # Keep looking for by cycling to the next post
            $from = ++$from % 3;
            }
        }
    } until ($#{$posts[1]} == $height-1); # Stop when the destination post is full
}
move_tower_iterative $disks, &quot;Back-left&quot;, &quot;Back-right&quot;, &quot;Front&quot; ; # Start moving.
1;
</code></pre>
<p>To balance that out, and to show the difference, here is the recursive version, also tested and timed. In this case I've removed the comments, just as a visual enhancement of the difference between the two versions:</p>
<pre class="lang-perl prettyprint-override"><code>#!/usr/bin/perl
use strict;
use warnings;
use 5.10.0;
my $disks = 20;
sub move_tower_recursive { 
    my ($height, $source, $dest, $spare) = @_;
    if ( 1 &lt;= $height) {
        move_tower_recursive($height-1, $source, $spare, $dest);
        printf &quot;\tMove disk from %s to %s\n&quot;, $source, $dest;
        move_tower_recursive($height-1, $spare, $dest, $source);
    }
}
move_tower_recursive $disks, &quot;Left side&quot;, &quot;Right side&quot;, &quot;Center&quot; ;
1;
</code></pre>

CC BY-SA 3.0
2018-01-15T17:12:16.907Z
This is the best answer for motivating recursion, in my opinion.
justhalf
CC BY-SA 3.0
2018-01-15T17:22:24.217Z
@justhalf Welcome to [cseducators.se]. I hope we see you around here often. I don't like Tower of Hanoi puzzle as a project because the work, or the solution to it, cannot be reused. Yet, when presented well, it can show the power of recursion and motivate students to explore the technique and develop the mental muscles to use recursion when appropriate.
Gypsy Spellweaver
CC BY-SA 3.0
2018-01-15T18:32:07.283Z
Which is exactly what the question is about! =)
And I said your answer is great, not just the Tower of Hanoi.
justhalf
CC BY-SA 4.0
2018-01-11T13:02:50.467Z
2020-10-06T03:18:41.193Z
2020-10-06T03:18:41.193Z
Gypsy Spellweaver
<h1>Tree Traversal</h1>
<p>Let's compare the recursive and iterative approaches to doing an in-order traversal of a binary search tree.</p>
<h3>Recursive approach</h3>
<pre class="lang-c prettyprint-override"><code>void orderedTraversal(const Node *node, void (*f)(int)) {
    if (!node) return;
    orderedTraversal(node-&gt;left, f);
    f(node-&gt;val);
    orderedTraversal(node-&gt;right, f);
}
</code></pre>
<h3>Iterative approach</h3>
<pre class="lang-c prettyprint-override"><code>typedef struct StackNode {
    Node *node;
    int state;
    struct StackNode *next;
} StackNode;

StackNode *push(StackNode *stack, Node *node, int state) {
    StackNode *newNode = malloc(sizeof *newNode);
    assert(newNode);
    newNode-&gt;next = stack;
    newNode-&gt;node = node;
    newNode-&gt;state = state;
    return newNode;
}
StackNode *pop(StackNode *node) {
    StackNode *next = node-&gt;next;
    free(node);
    return next;
}

void orderedTraversalIterative(Node *node, void (*f)(int)) {
    int state = 0;
    StackNode *stack = NULL;

    for (;;) {
        switch (state) {
            case 0:
                if (!node) {
                    state = 2;
                    continue;
                }

                stack = push(stack, node, 1);
                state = 0;
                node = node-&gt;left;
                continue;
            case 1:
                f(node-&gt;val);

                stack = push(stack, node, 2);
                state = 0;
                node = node-&gt;right;
                continue;
            case 2:
                if (!stack) return;
                node = stack-&gt;node;
                state = stack-&gt;state;
                stack = pop(stack);
                continue;
        }
    }
}
</code></pre>
<p>Of course, with a few macros, we can make the logic a bit clearer...</p>
<pre class="lang-c prettyprint-override"><code>#define CALL(NODE) \
    stack = push(stack, node, __LINE__); \
    state = 0;     \
    node = NODE;   \
    goto start;    \
    case __LINE__: \

#define RETURN do {       \
    if (!stack) return;   \
    node = stack-&gt;node;   \
    state = stack-&gt;state; \
    stack = pop(stack);   \
    goto start;           \
} while (0)

void orderedTraversalIterative(Node *node, void (*f)(int)) {
    int state = 0;
    StackNode *stack = NULL;

    start: switch (state) {
    case 0:
        if (!node) RETURN;
        CALL(node-&gt;left);
        f(node-&gt;val);
        CALL(node-&gt;right);
        RETURN;
    }
}
</code></pre>
<p>...and reveal that the iterative approach to this problem is to manually build a call stack mechanism so we can go back to using the recursive approach.</p>

CC BY-SA 3.0
2018-01-11T08:35:44.867Z
Now all we need is a motivating example for using a tree structure.
Stig Hemmer
CC BY-SA 3.0
2018-01-11T18:17:09.443Z
Anything where you need a stack data structure to implement iteratively is a potential candidate, including the https://en.wikipedia.org/wiki/Ackermann_function (which has the advantage of not needing a data structure as input.)
Peter Cordes
CC BY-SA 3.0
2018-01-11T18:40:06.773Z
@StigHemmer Lookup over ordered sets (e.g. std::map) or sets with string keys (usually in the form of a trie), abstract syntax trees, network flow (minimum spanning trees), pathfinding (really, almost anything involving graphs will have a tree somewhere), hierarchical clustering, minimax, suffix trees...  It's like asking when you'd use an array, or a variable; I'm almost not sure where to start.  Of course, some of these also have non-tree-based ways to do them, and the exact functions will differ from the binary search tree example, but they'll all use recursion somewhere.
Ray
CC BY-SA 4.0
2018-01-10T19:38:09.980Z
2020-10-06T03:17:26.400Z
2020-10-06T03:17:26.400Z
Ray
<p>Show them how they use recursion in solving puzzles in their <em>civilian life</em>.</p>

<h1>Sudoku</h1>

<p>Ask them how to solve <a href="https://en.wikipedia.org/wiki/Sudoku" rel="nofollow noreferrer">Sudoku</a>.</p>

<p>What's the naive way? You have to iterate through all (roughly) 9^81 numbers, checking each board.</p>

<p>Assuming each check takes on plank second (we're not even close to that in real life), it will take about 3.35843803 × 10^26 years years to solve each Sudoku puzzle.</p>

<p>That's <em>way</em> after the earth <a href="https://en.wikipedia.org/wiki/Timeline_of_the_far_future" rel="nofollow noreferrer">falls into a black dwarf sun</a>.</p>

<p>So how do we solve it?</p>

<p>Recursion. Find the "easiest" block to solve (meaning, the one with the least possible variation). Let's say it's the next small board:</p>

<pre><code>| _ | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |
</code></pre>

<p>So you that first blank could be a 4, 3, 1 or 1.</p>

<p>So what do you do?</p>

<p>You fill a four.</p>

<p>Then you check the board:</p>

<pre><code>| 4 | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |
</code></pre>

<p>Does it work?</p>

<p>No. There are two fours in the first column. </p>

<p>Try the next, and the next... until you get a one.</p>

<pre><code>| 1 | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |
</code></pre>

<p>Hey, that works!!</p>

<p>Let's move to the next blank. And you <em>recursively</em> [1] check each square.</p>

<p>How does it work?</p>

<p>Because each problem is a <em>subset</em> of the previous problem.</p>

<p><a href="https://play.rust-lang.org/?gist=84f488360abe78ff6a74e9301727081d&amp;version=undefined" rel="nofollow noreferrer">Here</a> is a sample solver of a given Sudoku board (The <a href="http://www.7sudoku.com/very-difficult" rel="nofollow noreferrer">website</a> I found it labeled it as "very difficult"). </p>

<p>The program solved it in less than a second, going through only 40,000 iterations.</p>

<hr>

<p>In reality, that's  how most people actually solve the problem (ever seen people writing small numbers in each square, erasing ones that don't work? That's your stack!)</p>

<p>[1] In this case you don't need recursion, because the board is too simple. But if you take a real board with moderate difficulty, you need to take steps in, check if they work, and if not, pop out until there's another way to solve it. In short, you push and pop solutions, which is easiest to do with recursion.</p>

<h1>A Maze</h1>

<p>How do you solve a maze?</p>

<p>You go down one path? If it doesn't work you <em>pop</em> back to the last state where there's hope and try again.</p>

<h1>Solving arithmetic problems</h1>

<p>How would you solve (1-2)/((1+2)/(3-4))?</p>

<p>Let's assume for a moment that all order-of-operations have been taken care of through parenthesis.</p>

<p>The simplest way would be a <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">recursive-descent parser</a>.</p>

<ol>
<li>Lex it. You now have the following lexical array: [<code>(</code> <code>1</code> <code>-</code> <code>2</code> <code>)</code> <code>/</code> <code>(</code> <code>(</code> <code>1</code> <code>+</code> <code>2</code> <code>)</code> <code>/</code> <code>(</code> <code>3</code> <code>-</code> <code>4</code> <code>)</code> <code>)</code>]</li>
<li>Start at position 0.</li>
<li><p>Go block by block:</p>

<ol>
<li><p>If it's a regular block (a number): do something like: </p>

<p><code>DoMath(curVal[pos],curVal[pos+1],curVal[pos+2])
pos = pos+2</code></p></li>
<li><p>If it's a 'control character' (a parenthesis in our example):</p>

<ol>
<li><em>Recurse</em> back to 3, with the 'end control character' being a 'close parenthesis'.</li>
<li>Replace 'n' characters (the length of the inner parenthesis expression) with the the return value.</li>
</ol></li>
</ol></li>
<li>If it's an 'end control character' (a 'close parenthesis' or an 'end-of-string tag'):
Return the value that's left after all that work.</li>
</ol>

CC BY-SA 3.0
2018-01-11T00:52:51.180Z
This is a really interesting first answer! Welcome to [cseducators.se], @cse! I hope to see you around more!
thesecretmaster
CC BY-SA 3.0
2018-01-11T12:48:22.253Z
You can do the naive way easily with recursion as well though :D
Koekje
CC BY-SA 3.0
2018-01-11T18:56:06.887Z
@Koekje Well, you wouldn't want to spend too much time on an algorithm that would never work in reality.  With the recursive approach, you've only wasted about 10 minutes of your life writing the naive version. :-)
Ray
CC BY-SA 3.0
2018-01-11T19:06:28.080Z
@Koekje anything done with recursion could be done iteratively (through a stack data type stored in heap), and anything done iteratively can be done with recursion (as is typically done in languages without mutable variables). The real point is where is recursion more _elegant_ (especially for beginners, especially if you're teaching them a language which supports mutable variables - which 99% popular languages do - R and MATLAB (I may be wrong as I don't know them at all) seem to be the only exception in [TIOBE](https://www.tiobe.com/tiobe-index/)'s index).
cse
CC BY-SA 3.0
2018-01-11T19:42:08.177Z
@cse Yes I know. Generally with method calls behind the scenes a stack is operating anyway, so the recursion will indirectly be translated to an iterative approach. The point I was trying to make, but failed to do, is that for me it seems like you could interpret the answer as recursion being a whole different beast, automagically opening up a vastly improved way to  solve the Sudoku. I do not however see how recursion is more elegant with languages containing mutable variables. Isn't it the other way around? Why are most functional languages built on using recursion?
Koekje
CC BY-SA 3.0
2018-01-12T00:11:44.700Z
@Koekje Sorry, the opposite. In languages with only non-mutable variables, you _must_ use recursion for everything, even a simple `for` loop. The question is where could recursion be useful in a regular imperative or OOP language.
cse
CC BY-SA 3.0
2018-01-13T23:09:26.463Z
Isn't the naive approach 9^81 instead of 10^81?
Paŭlo Ebermann
CC BY-SA 3.0
2018-01-16T06:29:50.697Z
That's not how you solve sudoku. It's not recursive. It's iterative and even that's not true. There are algorithms, which are neither iterative nor recursive.
ItamarG3
CC BY-SA 3.0
2018-01-19T18:42:34.810Z
@PaŭloEbermann True. You're going from 111... to 9999..., not 000... to 999...
cse
CC BY-SA 3.0
2018-01-21T05:00:49.307Z
@ItamarG3 [This](https://play.rust-lang.org/?gist=84f488360abe78ff6a74e9301727081d&version=undefined) is my implementation of my algorithm. How is it not recursive?
cse
CC BY-SA 3.0
2018-01-11T00:13:37.530Z
2018-01-21T05:03:06.573Z
2018-01-21T05:03:06.573Z
cse
<p>When teaching recursion, it is important to emphasize that the true power of recursion comes from its ability to branch. This rules out all the factorial and other similarly silly recursion examples much better written as for-loops.</p>

<p>Have your students write a function that, given an open tile in Minesweeper whose value is zero, opens all the tiles in the neighbourhood that are safe to open. I have used this example for about 15 years in intro to Java course, and think it is the best way to show the usefulness of recursion in a first year course.</p>

<p>Solving the subset sum problem in an integer array is another great example of branching recursion that is only three lines of code using recursion, and a lot more without it.</p>

CC BY-SA 3.0
2018-01-11T15:24:03.390Z
This is not only a gorgeous problem, but would also work very well in an Objects-first curriculum.
Ben I.
CC BY-SA 3.0
2018-01-11T15:26:09.377Z
Oh, and welcome to [cseducators.se].  I hope you'll join us in our mission here!
Ben I.
CC BY-SA 3.0
2018-01-11T15:17:52.503Z
2018-01-11T15:17:52.503Z
Ilkka Kokkarinen
<p>I'd suggest some version of string length, implemented recursively.  It's even simpler than factorial.  You just break one character off the string, feed it to a recursive call and add one to the result.  With that we can teach the essence of recursion.</p>
<p>I find programmers often get confused by trying to &quot;be the computer&quot; working out the recursion to depth rather than working abstractly.  So, one trick is to get the aspiring programmers to look at the recursive invocation as a black box rather than to try to think of what's happening at depth.  Within the implementation of a recursive function, we want to be able to use the recursive function as if we are merely a client consuming some other function (that already exists and provides some usable capability) with little to no concern about the actual recursion itself.</p>
<p>We always have to switch our hats from provider of an implementation to consuming client.  The trick with recursion is to be able to do that with the same function as its implementation is itself a consuming client (of itself).</p>
<p>One approach is to start something like this:</p>
<pre class="lang-c prettyprint-override"><code>int string_length(char *str) {
    if (*str == '\0')
        return 0;
    return 1 + strlen(str+1);
}
</code></pre>
<p>With the objective of looking at <code>strlen()</code> as a black box that just works (here: just what it does for us, not how), and then understanding how this <code>string_length()</code> works (e.g. just those three lines of implementation).</p>
<p>Then introduce the idea that since we have confidence that <code>string_length()</code> works — that it does the same thing as <code>strlen()</code> — we can use it in our own implementation: substituting <code>string_length()</code> for <code>strlen()</code>.</p>

CC BY-SA 3.0
2018-01-10T03:32:18.357Z
This is a nice, clear example of recursion, but is it a good *motivating* example for the entire process?  The iterative version (such as the simple `for` loop) is both more efficient and simpler to write.
Ben I.
CC BY-SA 4.0
2018-01-10T01:04:12.843Z
2020-10-05T21:31:16.490Z
2020-10-05T21:31:16.490Z
Erik Eidt
<p>If the students have learned object-oriented programming then network-traversal or tree-exploration works well because it is easier to visualize one node calling another than to visualize a method calling itself. Start with a directed graph with no cycles so you don't get infinite loops.</p>
<pre><code>//returns true of this is part of the path
public boolean findLastNode(List&lt;Node&gt; pathSoFar)
{
    if (this.isLastNode())
    {
        path.add(this);
        return true;
    }
    for (Node aNeighbor:this.getNeighbors)
    {
        if (aNeighbor.findLastNode())
        {
            path.add(this);
            return true;
        }
    }
    return false;
}
</code></pre>
<p>The code is easy to visualize and draw on the whiteboard because each recursive call moves you across the graph, and you can visualize each node having its own copy of the findLastNode method so you don't have to think of the flow of control reusing variables that are already holding other data.</p>

CC BY-SA 3.0
2018-01-11T11:15:26.070Z
Welcome to [cseducators.se]! This is a very interesting answer.
ItamarG3
CC BY-SA 3.0
2018-01-11T05:33:22.617Z
2020-11-27T01:17:39.153Z
2020-11-27T01:17:39.153Z
Readin
<p>Another approach, entirely different from my other answer, is to ask students how they might approach the following real-life scenario: they have just been given 1400 paper forms, all filled out by potential enrollees for a program.  The forms arrived in the mail and are in no particular order, but they must be sorted into one of 4 geographical regions, and then alphabetically by last name/first name.</p>

<p>The student has been situated in a meeting room with a giant, empty table, and boxes full of forms.  The student is told that the sorting needs to be done before the end of the work day.  Of course, the activity itself is boring, and the student would love to get out of there as soon as possible.  What approach might the student take to the task itself in order to get it done accurately and on time?</p>

<p>Typically, someone will almost immediately suggest sorting the sheets into subpiles.  One logical number of subpiles for this first case is 4: divide into 4 piles by geographic region.  Now repeat the procedure, dividing into further subpiles.  While a true computer algorithm might use 4 piles again, a person would more likely use 26 piles (for the letters of the alphabet).  At that point, look at the size of the piles.  Repeat the procedure as many times as you need on any piles that are large enough to still be unwieldy.  </p>

<p>At some point, you will have a series of tiny piles.  A person would probably sort these small piles using some form of insertion or selection sort. </p>

<p>We would now reverse the process, taking our tiny sorted piles, and recombining them into larger and larger fully sorted files.  These would be our recursive unwinding steps.</p>

<p>This entire procedure is not dissimilar from a standard mergesort (or, really, a recursive bucket sort).  Divide the problem, conquer the smaller pieces, and then recombine.  Breaking the problem into smaller subproblems is what makes the entire enterprise more manageable.</p>

<p>What's nice about this procedure as a motivator for examining recursion is that it, with only minor variations, is the natural solution that most people arrive at when faced with such a daunting sorting task because the benefits are clear and natural.</p>

CC BY-SA 3.0
2018-01-10T05:37:23.150Z
I don't have problems thinking of recursive methods, but I do struggle to see how this will help. From a code POV, it will look something like: `for (s in sheets) { switch (s.region) { a: region[a].append(s) ...} }; parallel for (r in region) { for (s in r) { switch (s.name[0]) {...} } }`, and the students will still see it as imperative, though it can be written in a recursive form more easily.
muru
CC BY-SA 3.0
2018-01-10T05:41:01.127Z
Hmmm, I'm not entirely certain that students would grasp that sorting on more than one key by sorting first on one key and then on another key actually IS an example of recursion.  That sounds a little funny even to me.
Wildcard
CC BY-SA 3.0
2018-01-11T00:08:33.820Z
You just proposed an iterative approach.
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-11T01:13:22.750Z
@immibis How so? I'm not seeing how breaking a big problem repeatedly into smaller subsections, fully solving the small problems, and recombining at the end is iterative. It's basically a mergesort.
Ben I.
CC BY-SA 3.0
2018-01-11T01:53:27.987Z
@BenI. Putting the forms into 4 piles is an iterative loop. Putting the forms from those 4 piles into 26*4 piles is just two nested loops. It's not recursive because you are just saving up all the work from one step until you're done with that step. See muru's comment.
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-11T02:50:24.433Z
@immibis I see that others agree with you from the upticks, but nevertheless, I still see it as subdividing and then re-merging, which is recursive. (FWIW, I am [not alone](https://en.wikipedia.org/wiki/Sorting_algorithm#Popular_sorting_algorithms) in calling this a [merge sort](https://stackoverflow.com/a/105983/4151129).) If anything, I might describe it as a recursive bucket sort.
Ben I.
CC BY-SA 3.0
2018-01-11T04:20:41.647Z
Oh now I see what you were getting at. For some reason it seems hard to understand your example.
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-11T04:23:46.950Z
@immibis Do you see any way to fix my description?  Apparently I'm being unclear to many folks, but I'm unsure about how.
Ben I.
CC BY-SA 3.0
2018-01-11T04:36:24.580Z
Perhaps it's because the intuitive way to do this is non-recursive (it's essentially a breadth-first search made with two nested loops).
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-11T13:14:12.030Z
@BenI. I think the major problem of the algorithm is the fixed recursion depth of only two levels. If you had done something like "*split by 4 regions. Every pile higher than 10 sheets, split by first letter of name. Every pile higher than 10 sheets, split by second letter of name. Every pile still higher than 10 sheets…*" the recursive approach (with "*small enough pile*" as base case) would have been clearer. Using different things (4 regions and 26 letters) in the two first steps didn't exactly help either.
Bergi
CC BY-SA 3.0
2018-01-11T15:05:46.867Z
@Bergi Thank you!!!  I re-wrote it significantly to try to make it more obvious.  Is it better now?
Ben I.
CC BY-SA 3.0
2018-01-11T16:24:15.710Z
Thanks, much better. However the core part of the recursion ("*Repeat the procedure as many times as*") still doesn't stand out over the clever sorting algorithm, so I'm not sure the students will grasp the difference between "recursion" and "divide-and-conquer".
Bergi
CC BY-SA 3.0
2018-01-09T22:13:27.710Z
2018-01-11T15:05:01.850Z
2018-01-11T15:05:01.850Z
Ben I.
<h1>Construct an immutable nested structure</h1>

<p>It's obvious (to us instructors) that in a purely functional language, recursion is the only way to create nested structures. And immutable data is imperative (pun intended) for proper semantical reasoning about values.</p>

<p>So what kind of examples lend themselves to an intuitive recursive approach where an imperative approach is much harder?</p>

<ul>
<li><p><strong>Nested data structures</strong> like linked lists, trees and graphs are most easily traversed and constructed recursively.</p>

<p>Linked lists are too simple, the tail recursion has the same idea as the equal imperative loop and can be written as such without involving an explicit stack. Graphs are too complicated as keeping state (e.g. to avoid infinite descend) and creating cycles is easiest to do using mutation, and many introductory graph algorithms <em>do</em> keep an explicit queue of nodes. Graphs without cycles are just trees. Here I would avoid n-ary trees where nodes keeps lists/arrays/vectors of children, as those again would typically be accessed in an (imperative) loop, which confuses the students (making the gist of recursion harder to recognise, and obfuscating the base case).</p>

<p>So binary trees it is. A simple tree of integers can be summed, scanned for its maximum and/or minimum, and mapped over with e.g. an incrementing or doubling transformation. It might even be filtered for odd/even numbers. Later you can introduce the respective abstractions (<code>fold</code>, <code>map</code>, <code>filter</code>) if you want.</p>

<p>I would recommend to avoid algorithms for balancing trees here, those are often rather unintuitive when expressed recursively or at least differ much from the imperative approach that is found in most teaching material.</p></li>
<li><p><strong>Immutable data structures</strong> cannot be re-initialised or changed during traversal. This again prevents imperative solutions e.g. in the <code>map</code> exercise.</p>

<p>If you are using a functional language in the course, this requirement is probably easy to place. However this doesn't satisfy imperative-minded students who will think "if I could just mutate the data (like in $favouriteLanguage) this task would be much easier".</p>

<p>If you are dealing with an imperative language, you will need to make up some excuses for why immutability is necessary. Constructing not a single but many distinct results helps here. They might be output as a side effect, but are going to get used later after the algorithm ended. Building an animation sequence that can be replayed later (and also rewinded, or run backwards) might be a good idea, which also provides the students with some visualisation.</p>

<p>Computing permutations <a href="https://cseducators.stackexchange.com/a/4144/660">as suggested by Ben I.</a> is a perfect take on this - instead of just printing all permutations (doable by mutating a sequence) many distinct arrays/lists need to be created. Computing the power set, the subsequences or substrings of an input are similar tasks (and don't even require loops because of the nature of the binary decisions). Here, the concept of sharing between data structures can be introduced as an advantage of immutability later in the course (demonstrated by memory requirements of responses to huge inputs).</p></li>
</ul>

CC BY-SA 3.0
2018-01-11T03:24:13.950Z
Excellent, helpful answer. Welcome back! :)
Ben I.
CC BY-SA 3.0
2018-01-11T03:15:49.470Z
2018-01-11T03:15:49.470Z
Bergi
<p>Since these did not need to be programming examples, here is another example that I like to use and have found illustrative.</p>

<p>When you need to write a method to solve some problem, you must write that method using the things that you already have: the statements in the language, and the methods already in the standard library or written by you. Your job is to find the right combination of these that will achieve the job.</p>

<p>For example, if you need to define the factorial function, you would do so with the definition</p>

<p>$F(n) = n * (n-1) * ... * 2 * 1$</p>

<p>where the right hand side contains a for-loop and a whole bunch of multiplications, two things that you already have in the language. So we can implement factorial using the things that we have.</p>

<p>But imagine this now as some fantasy type of setting, where this equation is a game of tug of war where the left hand side and the right hand side must pull with equal strength to balance each other out. On the left hand side, $F(n)$ is a big strong mountain giant. If the right hand side consists of little hobbits (each multiplication operation), we will necessarily need a large number of hobbits to be able to pull together as hard as the one mountain giant on the left side.</p>

<p>Spotting the self-similarity in the above definition allows us to turn this into an equivalent recursive definition</p>

<p>$F(n) = n * F(n-1)$</p>

<p>which at first seems like cheating, since we are borrowing the function $F$, the thing that we were supposed to define, from the future to be used in its own definition! What do we gain from doing this trick? Well, since $F(n-1)$ is now on the right hand side, it is now a big friendly giant that is pulling for us, instead of pulling against us, in this game of tug of war!</p>

<p>Nothing in that observation depends on the fact that $F$ is particularly the factorial function. In fact, the more complex and powerful the giant is when placed on the left hand side (for example, consider the problem of parsing), the more powerful it is also when it is working for us on the right hand side.</p>

<p>This realization allows us to solve arbitrarily complicated problems by using a slightly smaller version of those problems on the right hand side. In the game of tug of war between one giant and one slightly smaller giant, we only need to add a couple of small hobbits on the right hand side to balance the whole thing, instead of having to put down some large number of small things to balance one big thing. This is the power of recursion.</p>

CC BY-SA 3.0
2018-01-11T18:39:25.140Z
This some interesting hand-waving and analogy, but does nothing to change the fact that `prod *= i;` in a loop is just as easy to write, and runs faster (unless the compiler optimizes your recursion back into a loop).  The problem has no stack-like state that needs to be preserved for back-tracking, so recursion isn't helpful or necessary for factorial.  I know you didn't mention Fibonacci, but recursive Fib is even more dumb because it takes O(Fib(n)) time instead of O(n) time for a `a+=b; b+=a;` loop. Recursive Factorial doesn't make the complexity class worse, so it's not as bad an example.
Peter Cordes
CC BY-SA 3.0
2018-01-11T15:32:29.393Z
2018-01-11T15:59:56.403Z
2018-01-11T15:59:56.403Z
Ilkka Kokkarinen
<p>In my first programming class, I "discovered" the concept of recursion on my own, before it was introduced by the instructor.  It wasn't the typical use-case for recursion, but it was enough to jump start my thinking.</p>

<p>I was creating a really simple 2D tile based game, and was working on the graphics. I had a function that took an ID number that represented what kind of tile to draw, and the X,Y coords to draw it.  I had already implemented grass (ID 1), by simply drawing a green rectangle, with a few pixels of off-green.  When I went to draw a Tree (ID 2), the tree was supposed to have a grassy background behind it.  I didn't want to duplicate the grass drawing code again for the tree Tile, and after thinking about it for a while, I thought "Hey, I could just call the drawing function again, and tell it to draw the Grass tile at the current coordinates, then draw the tree over top of it."  </p>

<p>I asked the teacher if a function was allowed to call its self.  He got a strange look on his face, and asked me to show him what I was doing.  He explained a little bit about what was actually happening, and told me that what I was doing actually had a name. He said that it would be covered in a lot more detail in a few weeks.</p>

<p>For me, it was a simple way to see the <em>idea</em> of recursion as a real physical thing, without having to deal with the mathematical abstractions that things like the Fibonacci Sequence require.</p>

CC BY-SA 3.0
2018-01-12T13:16:05.557Z
Now that is a cool story. Welcome to CSEducators. There is a lot here that might interest you.
Buffy
CC BY-SA 3.0
2018-01-12T13:18:44.920Z
You didn't quite state this, but your answer brings up the possibility of seeding the field by simply utilizing recursion in front of the class at some prior time. The way I envision it, I would point it out, but leave it largely unexplained until we got to the proper unit.  This would serve to let them know that the possibility existed and feed their curiosity naturally, so that when we later get to the unit, they would be interested in exploring that oddity.  (If you like that, feel free to integrate it; it would also give a classroom tie-in, which you are currently missing.)
Ben I.
CC BY-SA 3.0
2018-01-12T13:07:58.620Z
2018-01-12T13:07:58.620Z
Bradley Uffner
<p>I think what makes Factorial and Fibonacci popular as teaching examples is that <strong>they have no input data</strong>.  This means student implementations can start from scratch, instead of being given some boiler-plate data declarations.  (Or requiring the students to write code to create a binary tree or something.)</p>

<p><a href="https://en.wikipedia.org/wiki/Ackermann_function" rel="nofollow noreferrer">The Ackermann–Péter function</a> <code>A(m,n)</code> has 2 integer inputs and one integer output so it's nice and simple like Factorial (no pointers or references to any data structures).  But its natural definition is recursive, and iterative implementation requires a stack of some sort, so a recursive implementation is easier than iterative.</p>

<p>It's not ideal (for testability over a range of inputs) that it grows so quickly, and you may need to introduce the concept of integer overflow (with wraparound, or undefined behaviour in languages like C for signed <code>int</code>).  On the other hand, students will probably think it's cool to have a function which can produce such large outputs from small inputs.  <code>A(4,2)</code> has 19,729 decimal digits.</p>

<p>But with <code>m=[0..3]</code>, the <a href="http://www.wolframalpha.com/input/?i=ackermann(3,n)%20for%20n%3D0..10" rel="nofollow noreferrer">result fits in a 32-bit integer for a wide range of <code>n</code></a>, so it's testable.</p>

<hr>

<p>IMO recursive Fibonacci is a really horrible example.  It has O(Fib(n)) complexity instead of O(n) time for an <code>a+=b; b+=a;</code> loop.  Recursive Factorial at least has the same complexity class as iterative, but it doesn't require keeping any state.</p>

<p>In an assembly-language assignment (especially when args are passed in registers), Factorial also fails to fully test recursion because no registers need to be saved/restored (except the return address for RISC architectures like MIPS that use a link register instead of x86-style <code>call</code>/<code>ret</code> pushing/popping a return address).  There's not much difference between an iterative loop and the body of a recursive implementation.  You could get implementations that recurse down to the bottom and then just multiply by an increasing counter while returning back up the call chain.</p>

<p>Recursive Fibonacci avoids this problem: needing to make two separate calls from the same function means it can't degenerate into a loop.  But we'd like to reject Fib because it makes recursion look like a stupid way to make programming harder, especially in assembly language.</p>

<p>(Do people really give recursive Fibonacci assignments in assembly language?  Yes, they do, and Stack Overflow has the questions from their students to prove it.  It is one of the simplest doubly-recursive functions (significantly simpler to implement in asm than Ackermann), but it's maybe so simple that it's not as obvious which state is the "important" state that needs to be saved/restored across child calls.)</p>

<p><a href="https://stackoverflow.com/questions/58127916/double-recursion-in-assembly-works-until-secondary-recursion-becomes-larger-than">A recent Stack Overflow question on MIPS assembly</a> (from a student assigned this homework) appears to have found some useful middle ground here with a function that has similar doubly-recursive structure to Fibonacci but is less trivial, making an iterative implementation less obvious.</p>

<p>And also simply not being a well-known function means that there aren't implementations of it all over the web in many languages, reducing the temptation to copy/paste.</p>

<ul>
<li><code>if n&gt;5</code> : <code>f(n) = n*f(n-1) - f(n-3) + n-23</code></li>
<li>else <code>n&lt;=5</code> basecase  <code>f(n) = 15 - 2n</code></li>
</ul>

<p>An iterative implementation is still easily possible and obviously more efficient, especially for large <code>n</code> without memoization.  But this has a couple useful features that make it better than Fib(n):</p>

<ul>
<li>The base case includes more <code>n</code> values, and is not totally trivial.  Initializing vars for an iterative implementation would take some care.</li>
<li>Using <code>f(n-3)</code> and skipping <code>f(n-2)</code> means iterative would have to keep more temporaries, but doesn't add complexity to a recursive case.</li>
<li>Using the original <code>n</code> <em>after</em> both of the recursive calls (to multiply the return value, or add to the total) motivates properly keeping it around.  (vs. maybe writing an asm function that preserves its input register, and just decrementing that again to create an input for the next call.  That would work but is totally non-standard for normal C calling conventions.)</li>
<li>Clever students will notice that <code>n</code> can be destroyed by the 2nd recursive call, doing <code>n - 23 + n*f(n-1)</code> early because integer <code>+</code> is associative.  Otherwise they'll have to save both the first return value <em>and</em> the original <code>n</code> if they evaluate the expression in the order written.</li>
<li>It's not Fibonacci so it's not recognizable as a well-known thing that can be looked up or that some students will already know about.</li>
</ul>

<hr>

<p><strong><a href="https://cseducators.stackexchange.com/questions/4143/what-are-good-examples-that-actually-motivate-the-study-of-recursion/4151#4151">Tree traversal</a></strong> is one of the best example use-cases for recursion, because you need to remember where you've been at each step of the problem, so any solution needs a stack data structure.  Using recursion lets you use the call-stack as your stack.</p>

<p>But you need a tree to traverse, so it's not as "simple" as Factorial.</p>

<p>And it's easy to see that it's a useful thing to do.</p>

CC BY-SA 3.0
2018-02-23T04:16:48.020Z
Excellent answer. Welcome to [cseducators.se]. I hope we see you around more. We have a few questions that broach the subject of [tag:assembly] language level thinking here as well. Maybe you will find them interesting and worth answering.
Gypsy Spellweaver
CC BY-SA 3.0
2018-02-26T02:03:54.967Z
@GypsySpellweaver: I had a look at some of the questions, but I don't know much about teaching asm to people who don't get it.  I literally don't understand why people find asm hard to learn, because it wasn't for me.  It's like building a robot; you put some pieces together to create a machine that does something useful one step at a time.  I know some people "don't get it", but I don't know how to put myself inside their head to understand why not, or if there's something you could tell them that would let them think about asm (and how computers work) in a useful way.
Peter Cordes
CC BY-SA 3.0
2018-02-26T02:45:39.810Z
It was worth a try anyway.
Gypsy Spellweaver
CC BY-SA 4.0
2018-02-23T03:45:57.913Z
2019-09-27T06:48:48.963Z
2019-09-27T06:48:48.963Z
Peter Cordes
<p>When i was introduced to recursion, i felt the same on why learning something i don't need but using iterative approach on complex situations like <strong>Tower of hanoi</strong> etc., using recursion seems to be more simpler in logic as well as programming.</p>

<p>The reason i like recursion:</p>

<p>You don't need to solve or think about whole solution. You can break the whole problem in smaller ones, and use those solution to solve the bigger problem. And this helps to think more clear logic for your problem.</p>

<p>Algorithms that makes sense using recursion: </p>

<ul>
<li>Tower of Hanoi</li>
<li>Quick sort</li>
<li>Graph traversal(Inorder, preorder, postorder)</li>
<li>and so on...</li>
</ul>

<p>If you want the students to feel interested in it, you can <em>try giving an assignment of solving tower of hanoi using iterative method</em>. And then using recursion, the students will themselves know which method to use where and why :)</p>

<p>Note: Look for <strong>ackermann function</strong> as well.</p>

CC BY-SA 3.0
2018-01-11T20:21:54.717Z
Welcome to CSEducators. I like this answer. If you want to improve it you could add a link or two, especially to a writeup of Ackerman's function. Better yet, explain a bit about why it is important.
Buffy
CC BY-SA 3.0
2018-01-12T18:28:04.303Z
This list of possible algorithms doesn't really add anything to the already existing answers. Can you add some depth so that your answer *adds* to the other answers rather than simply restating them?
thesecretmaster
CC BY-SA 3.0
2018-01-15T09:59:07.387Z
Well, better show recursion on example where the recursive approach is the _obviously_ simplest solution to a problem.
Not everybody comes quickly to a solution to the Hanoi problem, if ever. Same for sorting.
Michel Billaud
CC BY-SA 3.0
2018-01-11T18:58:28.467Z
2018-01-11T18:58:28.467Z
MIB
<p>From <a href="https://rads.stackoverflow.com/amzn/click/0465045669" rel="nofollow noreferrer">Douglas Hofstader's Metamagical Themas</a>, comes the idea of the Porpuquine. </p>

<p>A nine quilled porpuquine has nine quills, each of which is an eight quilled porpuquine. Of course an eight quilled porpuquine has exactly eight quills, each of which is a seven quilled porpuquine. Etc. </p>

<p>Of course, you can explore Quine. And you can do some computing. </p>

<p>The more complete story in the book is worth a look, of course. </p>

CC BY-SA 4.0
2018-12-28T18:11:59.220Z
2018-12-28T18:11:59.220Z
Buffy
<p>The answers are fantastic but what I see you looking for is a motivation for using recursion over other methods. The answer goes back to why one goes to school in the first place. Not to learn what we already know but what others know, which will in the long run prove valuable.</p>

<p>The reason we use recursion generally is not because it is the only solution (well trained CompSci grads can think of little else) but because it is what computers are good at. Particularly;
 1.Starting a problem. 
2.Putting it onto the stack in order to 
3. Go to another problem. 
This is done all the time. The point of recursion is that each of these steps is for the same purpose. It is not until all the processes are done that they look around to see that there was only one goal, not O sub n goals.</p>

<p>Using minor examples can show off the major achievement of this level of organization.</p>

CC BY-SA 3.0
2018-01-10T19:32:24.393Z
Welcome to CSEducators. We hope to see you back again.
Buffy
CC BY-SA 3.0
2018-01-10T19:33:03.960Z
There doesn't seem to be an example here responding to the question. Are you saying none are necessary? Can you clarify?
Buffy
CC BY-SA 3.0
2018-01-12T18:25:50.033Z
I agree with Buffy. This does not appear to actually answer the question. If you want to discuss the question's premise, feel free to do so in the chat room I mentioned in my comment on the question.
thesecretmaster
CC BY-SA 3.0
2018-01-14T19:07:37.423Z
I think the brief answer gave the structure of why recursion is useful based on what computers do well. This goes to the fundamental reason to teach it rather than more and more examples of it.
Elliot
CC BY-SA 3.0
2018-01-10T18:41:30.357Z
2018-01-10T18:41:30.357Z
Elliot
<p>Water is a good example, when you pour a jug of water compare it to the algorithim the algorithim or water is continually poured until there is no more water left or the base condition is satisfied, leaving you with a solution, comparing a water fall to a bad case of infinite recursion it just continues flowing. </p>

CC BY-SA 3.0
2018-01-12T23:18:31.310Z
Welcome to [cseducators.se]! How will the example of water illustrate to students why they need to *learn* recursion?
Ben I.
CC BY-SA 3.0
2018-01-13T01:12:34.100Z
To add to what Ben said, this same task could be accomplished with a `while` loop. Why would this example help students see the necessity of recusion?
thesecretmaster
CC BY-SA 3.0
2018-01-12T23:10:36.657Z
2018-01-12T23:10:36.657Z
hoffman
<p>I find a very easy to understand example for recursion is the folder structure on a computer.</p>
<p>Look through all folders (within a certain location) and... list all .doc files, for example.</p>
<blockquote>
<p>First, you look in the location you were given and see what you're looking for... or not, but you see more folders.</p>
<p>Then you take each of those folders, look into them and see what you're looking for... or not, but you see more folders.</p>
<p>Then you take each of those folders... (you get the idea)</p>
</blockquote>
<p>It's a simple function to write and understand (at least in pseudocode, actual implementations may vary^^) and a concept that's easy to grasp for even a complete beginner. Introducing the problem and the manual solution, it's already obvious that each time, the same thing happens again and again. Pseudocode implementation is equally simple to write and grasp:</p>
<pre><code>function findFiles(folder) {
  look for .doc files, if found add them to fileList.txt
  look for folders
  for each found folder: findFiles(foundFolder)
}
</code></pre>
<p>I've used this example to explain recursion several times, and never had trouble getting the person to understand it. Even non-programmers can grasp the concept like this.</p>

CC BY-SA 3.0
2018-01-10T11:31:44.810Z
Welcome to CSEducators. Come back often. I'll also note that this is recursion over a tree, not just a linear structure. Nice.
Buffy
CC BY-SA 3.0
2018-01-10T11:43:34.630Z
I think this is the best approach. Show recursive functions by processing recursive data structures (here: the folder structure)!
Other classical examples (like Fibonacci or Factorial) often trigger a reaction like "Nice, but why do I need that?" by the students. But every computer user has seen recursive data strucures at least once in their life (e.g. folders). Showing them that such structures can be processed elegantly by recursive functions gives often the desired "wow"effect.
trunklop
CC BY-SA 3.0
2018-01-10T12:40:46.237Z
+1. Depth-first tree traversal is the simplest example I can think of where the recursive approach is truly easier to understand than the iterative approach. And even students who are not familiar with trees will probably be familiar with folders in a filesystem.
BenM
CC BY-SA 3.0
2018-01-10T14:09:36.573Z
There's a good chance an iterative programmer will already know how to do this without recursion, by use of a stack
phflack
CC BY-SA 3.0
2018-01-10T14:27:07.367Z
I think a tree approach will work well, but perhaps getting the elements of a binary tree in different orders (preorder, inorder, and postorder)
phflack
CC BY-SA 3.0
2018-01-10T15:06:16.010Z
Another classical example for a recursive function: Raytracing with reflection. Requires some (very) basic knowledge of geometry and linear algebra. I am using that in one of my classes for CS students (who, indeed, have the required math background) as a kind of "fun" project.
trunklop
CC BY-SA 3.0
2018-01-10T23:26:01.613Z
@phflack My experience is that students that do not yet understand recursion are also bad at appropriate use of data structures. YMMV.
corsiKa
CC BY-SA 3.0
2018-01-11T15:34:47.183Z
This was literally how I discovered recursion many years ago!
JanErikGunnar
CC BY-SA 3.0
2018-01-11T16:45:27.097Z
As a (very) amateur programmer that just writes scripts for a data analysis, recursion has always baffled me and I've never had to implement it thus far. But I instantly understood it with this example. So here's at least one piece of anecdotal evidence that it works for a beginner.
syntonicC
CC BY-SA 3.0
2018-01-15T09:23:24.253Z
@PeterCooperJr. I think you're being silly; phones haven't *replaced* other computers for *any* generation, and any high-school-age kid these days is going to at least have experience with using Microsoft Office, which implies experience with saving files on a traditional file system. Pretty much the only people who are *only* familiar with phone and tablet OSes are a handful of tech-illiterate old folks whose families bought them a tablet because they thought it'd be easier to get the hang of (there's such a person in my family).
Mark Amery
CC BY-SA 3.0
2018-01-10T09:16:12.270Z
2018-01-10T09:16:12.270Z
2020-06-18T08:36:57.023Z
Syndic
<p>One good example is to make permutations of all of the letters in a word of arbitrary length.  It's quite tricky to do iteratively, since you essentially have to recreate the program stack to get it done.  The recursive solution, however, is clean and clear.</p>

<p>Let the students try to work in pairs on an iterative solution for just five minutes.  The goal would not be to actually implement it, but just to think through an approach.  Then show them the short and elegant recursive answer and help them to trace through it.</p>

CC BY-SA 3.0
2018-01-10T05:44:36.963Z
I think you've got it.  Actually, that's the *only* example on this page (so far) that can't be answered with just, "Okay, so what?  That's just as easy or easier without any recursion."
Wildcard
CC BY-SA 4.0
2019-09-16T06:30:31.177Z
Permutations may be tricky to do iteratively, but a common iterative approach for "next permutation" involves using an array, not anything that resembles a stack.
rcgldr
CC BY-SA 3.0
2018-01-09T21:40:03.747Z
2018-01-11T23:22:10.973Z
2018-01-11T23:22:10.973Z
Ben I.
<p>Writing recursive code to output the <a href="https://en.wikipedia.org/wiki/Koch_snowflake" rel="noreferrer">Snowflake Curve</a> (Koch snowflake) was something that definitely pushed my buttons early on.</p>
<p>It's formed as follows:</p>
<blockquote>
<p>The Koch snowflake can be constructed by starting with an equilateral triangle, then recursively altering each line segment as follows:</p>
<ul>
<li>divide the line segment into three segments of equal length.</li>
<li>draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.</li>
<li>remove the line segment that is the base of the triangle from step 2.</li>
</ul>
</blockquote>
<p>An <a href="https://upload.wikimedia.org/wikipedia/commons/f/fd/Von_Koch_curve.gif" rel="noreferrer">animation</a> is also available from Wikimedia which shows the snowflake after the first few iterations.</p>
<p>To generalize further, many <strong>Fractals</strong> are generated by recursive algorithms and are thus excellent visual representations of recursion in action. The Snowflake/Koch curve is an example of a fractal that is produced by a relatively simple and easily visualizable algorithm making it a great entree into the wider world of fractals.</p>

CC BY-SA 3.0
2018-01-10T11:33:59.300Z
Welcome to CSEducators. We hope to see you again. Note that we value longer posts over such short ones, especially posts that are just links that require navigating away from the site for explanation. It would be good if you could give a longer explanation of the curve, its algorithm, or why you think it is important pedagogically.
Buffy
CC BY-SA 3.0
2018-01-10T19:03:39.443Z
Whenever I see Koch snowflake it reminds me that in a math course we were asked to prove that snowflake curve is infinite but the area it encloses is finite.
Crowley
CC BY-SA 3.0
2018-01-10T23:58:19.247Z
The Sierpinski Triangle may also be a good one. To draw the triangle, draw 3 triangles (in the right places).
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-16T05:49:25.113Z
Fractals are the last thing I consider "motivating"...
user541686
CC BY-SA 3.0
2018-02-28T03:19:11.413Z
@mehrdad but they make cool t-shirts!
pojo-guy
CC BY-SA 3.0
2018-01-10T06:41:56.840Z
2018-01-10T18:51:25.400Z
2020-06-18T08:36:57.023Z
bruised reed
<p>Other than the obvious <a href="https://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">merge sort</a>, I really like the <a href="https://en.wikipedia.org/wiki/Minimax" rel="noreferrer">minimax algorithm</a>, especially when applied to creating a computer player of a simple game.</p>

<p>Start with something simple like tic-tac-toe. When it's your turn, you can think about putting an <code>X</code> on each of the 9 squares. Then you have to think about what your opponent would do in each case. Your opponent would then think about what <strong>you</strong> would do if they marked an <code>O</code> on each square...</p>

<p>To codify this in a computer player, you can create a pretty simple recursive algorithm that exhaustively searches the space, alternating between whose turn it is, and eventually choosing whichever move leads to the most possible wins, or the fewest losses, whatever. Bonus points for pitting student algorithms against each other.</p>

<p>Then apply that to something more complicated like checkers or chess (or just larger or multidimensional tic-tac-toe). Here, you apply the same basic idea, but you can no longer exhaustively search the whole space because it's too large. So you have to come up with a <a href="https://en.wikipedia.org/wiki/Heuristic" rel="noreferrer">heuristic</a> and maybe implement <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="noreferrer">alpha-beta pruning</a>.</p>

<p>My point is that the algorithm itself is simple to think about and fun to play with, but it leads to lots of cooler, more complicated topics as well.</p>

<p>See also: <a href="https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion">Analogy for teaching recursion</a></p>

CC BY-SA 3.0
2018-01-10T05:39:27.087Z
That doesn't seem to directly answer the question, as you *don't* solve such things with recursion.
Wildcard
CC BY-SA 3.0
2018-01-10T07:28:31.940Z
I prefer Quicksort for demonstrating recursion. I learned merge sort back in the days when it would be done non-recursively using sequential I/O streams and O(1) RAM, and I've in fact found it useful in an embedded system for storing records stored on a flash chip (the flash chip had more than enough space to hold two copies of all 5,000 records, but the system had less than 3840 bytes of RAM).
supercat
CC BY-SA 3.0
2018-01-10T17:31:07.233Z
@Wildcard Uhh, what? From Wikipedia: `"A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game"`
Kevin Workman
CC BY-SA 3.0
2018-01-10T19:13:40.877Z
@KevinWorkman I meant the part about heuristics and such, but I see your point.  Makes sense.
Wildcard
CC BY-SA 3.0
2018-01-10T19:15:52.160Z
@Wildcard Yeah, my point is that things like heuristics and alpha-beta pruning are more advanced topics that the basic recursive algorithm leads to. Programming is extremely interconnected, and I think the more connections you make from the basics to the more complicated stuff, the better.
Kevin Workman
CC BY-SA 3.0
2018-01-11T18:15:40.867Z
@Wildcard: I had a Tic-Tac-Toe assignment I still remember in a first-year CS course.  The week after the assignment, our instructor asked who had used recursion to solve it.  IIRC, I was the only person to put up their hand.  If there was a move that forced a win, my program made it.  Otherwise it would play the first (or one of, I forget) the moves that would lead to a draw against best play.  I remember adding a random-first-move option so it wouldn't spend a couple seconds fully solving the game before making a move on an empty board :P
Peter Cordes
CC BY-SA 3.0
2018-01-09T22:04:51.723Z
2018-01-10T18:12:27.760Z
2018-01-10T18:12:27.760Z
Kevin Workman
<p>I'm going to focus on student's understanding recursion at a fairly deep level, rather than coding.</p>
<p>First, to really understand recursion you need a sense of its parts. There is the <em>base case</em>, of course and most teachers spend time working on that, but students often miss it. But Before the process hits the base case there is a <em>winding phase</em> working toward the base case and after the base case is reached there is an <em>unwinding phase</em> in which all of the recursive &quot;calls&quot; unwind. In the execution of the algorithm, the winding phase is associated with the execution stack increasing in &quot;height&quot; and the unwinding case is associate with its subsequent shrinking.</p>
<p>One point often missed by novices is that the winding phase has just exactly as many steps as the unwinding phase.</p>
<p>Another point often missed by novices is that <em>work</em> can be done on both the winding and unwinding phases as well as in the base case.</p>
<p>Therefore, to teach recursion you need a set of examples or exercises in which the student can examine all of these in detail.</p>
<p>Complicating this learning is that most students learn recursion in an environment in which they have already learned to count, both upwards and downwards, and that knowledge, while useful in general, can inhibit learning about recursion if the ideas of recursion and counting (by incrementing or decrementing integers) get merged into a single idea.</p>
<p>Therefore, I propose a sequence of active learning exercises, that don't involve coding, but in which the students play roles (stack frames, actually, though you needn't discuss that until later), and which lend themselves to immediate discussion and analysis.</p>
<p>To do these you will want a deck of index cards on which to write instructions of the various roles. The recursions will all be &quot;list-like&quot; so a subset of your students will stand in front of the room in a row. Each student will have a card for the current exercise. Your role is to keep things moving so that the &quot;execution&quot; corresponds to that of a computer. I assume that the students are arranged &quot;left to right&quot; at the front, with the &quot;base-case&quot; person at the right furthest from you.</p>
<h2>Exercise one - Work only in the base case.</h2>
<p>This is a fairly odd example, not likely to be part of a real program, but it can be instructive. One student's instruction card says that when they are given another card they just read aloud what is on it and then pass it back to the person that gave it to them (This person is the base case). A few others (maybe zero) each have an instruction card that says that when they receive another card they just pass it to the next person in the line, though if it is passed from the left it needs to pass to the right. You have one additional card that says &quot;All Done&quot;. You pass this card to the first person, who passes it on, and it should eventually reach the base case and be read aloud. You should then get the card passed back to you.</p>
<p>Talk with the students about the phases (winding, unwinding, base) and how the number of times the card passed in is the same as the number passed out.</p>
<p>Run the &quot;simulation&quot; more than once, with at least one &quot;run&quot; with only the base case. Later you can run it again with a missing base case to see the error that arises.</p>
<h2>Exercise two - Work on Winding Phase - Tail Recursion</h2>
<p>The instruction card for the base case is that when handed a card he or she should announce how many marks are on the card and then pass it back.</p>
<p>The other student's instructions are that when passed a card &quot;from the left&quot; they just put a mark on it and pass it to the person on the right, but when passed a card from the right they just pass it to the left.</p>
<p>Start the simulation by passing a blank card to the first person (who might be the base case in some &quot;runs&quot;. The base-case person should announce the number of people prior to the base case and return the card, through the line, back to you.</p>
<p>At some point you can talk about how this might be mapped to a while loop and avoid all of the return steps: unwinding tail recursion.</p>
<p>As before, have an immediate discussion about what happened to make sure that the students got the points.</p>
<p>You can discuss the fact that the number of marks on the card is like a parameter to the function, also.</p>
<h2>Exercise three: Work on the unwind phase only.</h2>
<p>The base case instruction is that when handed a card, simply hand it back. The others have instructions that say that they should simply pass on a card if they receive it from the left, but mark it if they receive it from the right and pass it left.</p>
<p>Pass a blank card to the first person and you should get back a card with one mark for each person, but no announcements. You will need to make the announcement of the number of marks.</p>
<h2>Exercise four: Work on both winding and unwinding phases.</h2>
<p>Here the base-case instruction is that when given a card (from the left) with a certain number of ticks, just write the number of ticks on the card (perhaps on its back) and return it to the person who gave it.</p>
<p>The other student's instruction is that when passed a card from the left just put a tick on it but when passed a card from the right find the largest number on it, double that number, write it on the card and pass it back toward the right. Pass the first person an empty card and make sure you get back the correct result.</p>
<p>Again, a short discussion question/answer session will help solidify the ideas.</p>
<p>While the discussion here was long, these things move quite quickly and only a few minutes are required for each exercise and its retrospective.</p>
<p>However, expect that the students will get it wrong as you go, so your job is to be a coach to make sure it works ok and that the appropriate lessons are learned. Emphasize that the &quot;data card&quot; passed through exactly as many hands on the winding phase as on the unwinding phase.</p>
<hr />
<p>If you want to emphasize the stack-frame idea a bit more, then in each of the exercises, don't line up the students initially, but pick on them one at a time when you need a new &quot;frame&quot;. Give each student their instruction card when they stand up to join. This will require a bit more time, of course, but is more realistic and viewers won't know the depth of recursion beforehand.</p>
<hr />
<p>I expect that, with the above guidance, you could also devise simple coding exercises with the same characteristics, letting students learn to carefully distinguish the phases of recursion as well as the symmetry.</p>

CC BY-SA 3.0
2018-01-10T05:37:41.947Z
Bonus points if you use card instructions to implement the passing out of cards.  ;)  Actually, that would probably get a LOT more interest than just passing out the cards in the usual manner and then beginning the exercise.
Wildcard
CC BY-SA 3.0
2018-01-10T13:40:49.397Z
When you noted `base case` I was expecting to see a follow-up with induction which didn't occur. So now I have to ask, when you say base case are alluding to induction or it is just a coincidence of words?
Guy Coder
CC BY-SA 3.0
2018-01-10T13:52:01.060Z
Recursion and induction are related, of course. So the use of `base case` seems pretty natural to me. You need a base case to avoid infinite recursion, just as you need a base case to avoid infinitely recursive definitions when using induction.
Buffy
CC BY-SA 3.0
2018-01-10T23:57:04.907Z
I don't agree that studying the base case, winding phase and unwinding phase is motivating at all! It feels like overly-abstract gibberish. The point is not to study how recursion works abstractly, the point is to demonstrate how it's useful. Passing cards around also feels too artificial to be a meaningful demonstration.
Criticize SE actions means ban
CC BY-SA 3.0
2018-01-11T00:10:42.700Z
I think you missed the point. The phases and the base case are essential to know and understand. You need a set of tailored exercises that solidify the knowledge of all those parts to be sure the student gets it. The instructor also needs to be explicit about how each exercise uses the parts. With an incomplete understanding it is harder to be an effective program designer. This is especially true in languages that do effective tail recursion elimination.
Buffy
CC BY-SA 3.0
2018-01-13T23:04:42.680Z
Excercise 3 looks like it would have one mark too few?
Paŭlo Ebermann
CC BY-SA 3.0
2018-01-13T23:21:00.190Z
That depends on whether you want to "count" the base case or not. If you do, the base case should also mark the card.
Buffy
CC BY-SA 3.0
2018-01-09T21:51:58.657Z
2018-01-10T12:38:00.667Z
2020-06-18T08:36:57.023Z
Buffy
<p>One of the traps of imperative-first is how difficult it becomes to help students make sense of recursion when they finally encounter it.  And if those kids are fairly competent iterative programmers, they may also resist the new technique, as they feel perfectly comfortable solving problems without it. Many of the obvious examples of recursion (such as Fibonacci numbers) are either faster or cleaner when done iteratively.  </p>

<p>What examples, then, cleanly motivate recursion?  To be honest, they don't have to even be coding examples.  What I want is for students to intuitively understand the <em>purpose</em> of this new (to them) technique.</p>

<p>(I am aware of <a href="https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion">this question</a> of course, but, while it is helpful, is is after an explanatory analogy to <em>clarify</em> recursion, while this question is about finding a clear motivation to study it in the first place.)</p>

CC BY-SA 3.0
2018-01-10T11:10:36.803Z
This [stack exchange question](https://cseducators.stackexchange.com/q/4143/2311) is quite motivating.
AncientSwordRage
CC BY-SA 3.0
2018-01-10T16:17:42.003Z
Possible duplicate of [Analogy for teaching recursion](https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion)
Ubi.B
CC BY-SA 3.0
2018-01-12T18:17:56.480Z
Please do not attempt to answer the question in the comments. Answers in the comment section break mechanisms that are vital to how SE works such as voting, editing, and accepting. In addition, comments are meant not to be permanent. Please do not engage in extended discussion in the comments, comments are meant for requests for clarification or suggested improvements to the question. This conversation has been [moved to chat](http://chat.stackexchange.com/rooms/71597/discussion-on-question-by-ben-i-what-are-good-examples-that-actually-motivate-t).
thesecretmaster
CC BY-SA 3.0
2018-01-13T10:58:48.267Z
Mergesort is one algorithm that's very easy to understand recursively, but a bit harder to get if you do it iteratively.
Clearer
CC BY-SA 3.0
2018-01-14T01:25:13.213Z
@Pureferret I was expecting that to link to StackOverflow... you trolled me!
Chris Cirefice
CC BY-SA 3.0
2018-01-14T07:29:16.637Z
How to motivate them?  "If you don't study recursion, you're going to fail the test on recursion and also do bad on the parts of the semester exam that are on recursion."
RonJohn
CC BY-SA 3.0
2018-01-15T13:49:49.807Z
@RonJohn This is the worst teaching approach ever.
csha
CC BY-SA 3.0
2018-01-15T14:00:02.233Z
@m93a Some people are motivated by fear of failure.
RonJohn
CC BY-SA 3.0
2018-01-15T14:15:22.953Z
@RonJohn Yes, fear motivates some, but this kind of motivation will never make them like or enjoy the subject. Good programmers are creative and think for themselves – obeying your rules will never teach them the skill of problem-solving, which is crucial. Furthemore, the point of teaching is preparing students for real-life problems. By not showing scenarios where recursion is beneficial, you would teach them nothing, as they wouldn't recognise recursion as a good tool.
csha
CC BY-SA 3.0
2018-01-15T14:30:54.397Z
@m93a the question was about *motivation*.  A teacher can say, "here are important real world examples" until he's blue in the face, but **that's not motivation**.  Recursion was interesting *to me* as a student because some algorithms were "cleaner" to implement that way.  Of course I also thought, "this is all academic, since it'll just blow the stack when the problem gets realistically big."  So... "wanting to keep my grades up" is why I **really** learned recursion, and have *rarely* used it since.
RonJohn
CC BY-SA 3.0
2018-01-19T15:59:36.507Z
Love is a better motivator than fear.
Theodore Norvell
CC BY-SA 3.0
2018-03-15T19:24:14.880Z
How about introducing everything through the lens of recursion? Addition of 'n' numbers for example? What's the point? Take a detour into Fibonnaci and show how the "recurrence relation" led to a closed form solution - perhaps they can come up with one for something simple too? The NO recursion and NO iteration and some points bonus? Also a good seguey would be showing how recursiveness and "computability" are sort of connected and why was it "natural" to be recursive at one point and then our move to iterative...
PhD
CC BY-SA 4.0
2019-02-22T20:51:23.550Z
At my university, the first language we were taught was Haskell, a pure functional language where literally everything is recursive (no loops, everything is immutable, no side-affecting code). Teach them such a language, and in particular solve problems that use useful recursive data structures such as trees. Show them how simple and effective recursion can be - this will become especially apparent to those of them who are more (pure-)mathematically inclined. Get them to start thinking with portals - they will start to see recursive solutions all the time, and then they will have 'got it'.
otah007
CC BY-SA 4.0
2020-10-11T15:14:38.327Z
Wondering about this »Fibonacci can be done faster... iteratively« What's your preferred O(log(n)) version of fibonacci, especially if you don't use heavy artillery math like generating functions?
Rushi
CC BY-SA 4.0
2020-10-12T19:06:16.430Z
@Rusi I was unaware of the log-n recursive version, so thank you for bringing that to my attention!!  Though if we're not so concerned with clarity and simply want efficiency, we may as well use the O(1) version, which is certainly not recursive in the slightest.  :D
Ben I.
CC BY-SA 4.0
2020-11-19T20:13:33.030Z
`fib = 1 : 1 : zipWith(+) fib (1 : fib)`. Here's an O(n) solution, recursive, for generating a list of Fibonacci numbers (because it generates a list, O(n) is the most efficient possible time complexity). AS someone who has also learned Haskell, it's enjoyable to see how elegant some algorithms are when written in a recursive way.
Carson Graham
CC BY-SA 4.0
2021-02-20T11:34:39.697Z
This [blog post](https://computethought.blog/2019/11/11/a-case-of-recursion/) has something to say on it.
ctrl-alt-delor
<lesson-ideas><recursion>
What are good examples that actually motivate the study of recursion?
# What are good examples that actually motivate the study of recursion?

(Asked by: username_0 on 2018-01-09)

One of the traps of imperative-first is how difficult it becomes to help students make sense of recursion when they finally encounter it. And if those kids are fairly competent iterative programmers, they may also resist the new technique, as they feel perfectly comfortable solving problems without it. Many of the obvious examples of recursion (such as Fibonacci numbers) are either faster or cleaner when done iteratively.

What examples, then, cleanly motivate recursion? To be honest, they don't have to even be coding examples. What I want is for students to intuitively understand the *purpose* of this new (to them) technique.

(I am aware of [this question](https://username_20ducators.stackexchange.com/questions/17/analogy-for-teaching-recursion) of course, but, while it is helpful, is is after an explanatory analogy to *clarify* recursion, while this question is about finding a clear motivation to study it in the first place.)

**Tags:** lesson-ideas, recursion

> **Comments:**
> **username_1**: This [stack exchange question](https://username_20ducators.stackexchange.com/q/4143/2311) is quite motivating.  
> **username_2**: Possible duplicate of [Analogy for teaching recursion](https://username_20ducators.stackexchange.com/questions/17/analogy-for-teaching-recursion)  
> **username_3**: Please do not attempt to answer the question in the comments. Answers in the comment section break mechanisms that are vital to how SE works such as voting, editing, and accepting. In addition, comments are meant not to be permanent. Please do not engage in extended discussion in the comments, comments are meant for requests for clarification or suggested improvements to the question. This conversation has been [moved to chat](http://chat.stackexchange.com/rooms/71597/discussion-on-question-by-ben-i-what-are-good-examples-that-actually-motivate-t).  
> **username_4**: Mergesort is one algorithm that's very easy to understand recursively, but a bit harder to get if you do it iteratively.  
> **username_5**: @Pureferret I was expecting that to link to StackOverflow... you trolled me!  
> **username_6**: How to motivate them?  "If you don't study recursion, you're going to fail the test on recursion and also do bad on the parts of the semester exam that are on recursion."  
> **username_7**: @username_6 This is the worst teaching approach ever.  
> **username_6**: @m93a Some people are motivated by fear of failure.  
> **username_7**: @username_6 Yes, fear motivates some, but this kind of motivation will never make them like or enjoy the subject. Good programmers are creative and think for themselves – obeying your rules will never teach them the skill of problem-solving, which is crucial. Furthemore, the point of teaching is preparing students for real-life problems. By not showing scenarios where recursion is beneficial, you would teach them nothing, as they wouldn't recognise recursion as a good tool.  
> **username_6**: @m93a the question was about *motivation*.  A teacher can say, "here are important real world examples" until he's blue in the face, but **that's not motivation**.  Recursion was interesting *to me* as a student because some algorithms were "cleaner" to implement that way.  Of course I also thought, "this is all academic, since it'll just blow the stack when the problem gets realistically big."  So... "wanting to keep my grades up" is why I **really** learned recursion, and have *rarely* used it since.  
> **username_8**: Love is a better motivator than fear.  
> **username_9**: How about introducing everything through the lens of recursion? Addition of 'n' numbers for example? What's the point? Take a detour into Fibonnaci and show how the "recurrence relation" led to a closed form solution - perhaps they can come up with one for something simple too? The NO recursion and NO iteration and some points bonus? Also a good seguey would be showing how recursiveness and "computability" are sort of connected and why was it "natural" to be recursive at one point and then our move to iterative...  
> **username_10**: At my university, the first language we were taught was Haskell, a pure functional language where literally everything is recursive (no loops, everything is immutable, no side-affecting code). Teach them such a language, and in particular solve problems that use useful recursive data structures such as trees. Show them how simple and effective recursion can be - this will become especially apparent to those of them who are more (pure-)mathematically inclined. Get them to start thinking with portals - they will start to see recursive solutions all the time, and then they will have 'got it'.  
> **username_11**: Wondering about this »Fibonacci can be done faster... iteratively« What's your preferred O(log(n)) version of fibonacci, especially if you don't use heavy artillery math like generating functions?  
> **username_0**: @Rusi I was unaware of the log-n recursive version, so thank you for bringing that to my attention!!  Though if we're not so concerned with clarity and simply want efficiency, we may as well use the O(1) version, which is certainly not recursive in the slightest.  :D  
> **username_12**: `fib = 1 : 1 : zipWith(+) fib (1 : fib)`. Here's an O(n) solution, recursive, for generating a list of Fibonacci numbers (because it generates a list, O(n) is the most efficient possible time complexity). AS someone who has also learned Haskell, it's enjoyable to see how elegant some algorithms are when written in a recursive way.  
> **username_13**: This [blog post](https://computethought.blog/2019/11/11/a-case-of-recursion/) has something to say on it.  

---

## 21 answers

### Answer by username_37 on 2018-01-10. Score: 101

I find a very easy to understand example for recursion is the folder structure on a computer.
Look through all folders (within a certain location) and... list all .doc files, for example.

First, you look in the location you were given and see what you're looking for... or not, but you see more folders.
Then you take each of those folders, look into them and see what you're looking for... or not, but you see more folders.
Then you take each of those folders... (you get the idea)

It's a simple function to write and understand (at least in pseudocode, actual implementations may vary^^) and a concept that's easy to grasp for even a complete beginner. Introducing the problem and the manual solution, it's already obvious that each time, the same thing happens again and again. Pseudocode implementation is equally simple to write and grasp:
function findFiles(folder) {
  look for .doc files, if found add them to fileList.txt
  look for folders
  for each found folder: findFiles(foundFolder)
}

I've used this example to explain recursion several times, and never had trouble getting the person to understand it. Even non-programmers can grasp the concept like this.

> **Comments:**
> **username_32**: Welcome to CSEducators. Come back often. I'll also note that this is recursion over a tree, not just a linear structure. Nice.  
> **username_38**: I think this is the best approach. Show recursive functions by processing recursive data structures (here: the folder structure)! Other classical examples (like Fibonacci or Factorial) often trigger a reaction like "Nice, but why do I need that?" by the students. But every computer user has seen recursive data strucures at least once in their life (e.g. folders). Showing them that such structures can be processed elegantly by recursive functions gives often the desired "wow"effect.  
> **username_39**: +1. Depth-first tree traversal is the simplest example I can think of where the recursive approach is truly easier to understand than the iterative approach. And even students who are not familiar with trees will probably be familiar with folders in a filesystem.  
> **username_40**: There's a good chance an iterative programmer will already know how to do this without recursion, by use of a stack  
> **username_40**: I think a tree approach will work well, but perhaps getting the elements of a binary tree in different orders (preorder, inorder, and postorder)  
> **username_38**: Another classical example for a recursive function: username_18tracing with reflection. Requires some (very) basic knowledge of geometry and linear algebra. I am using that in one of my classes for CS students (who, indeed, have the required math background) as a kind of "fun" project.  
> **username_41**: @username_40 My experience is that students that do not yet understand recursion are also bad at appropriate use of data structures. YMMV.  
> **username_42**: This was literally how I discovered recursion many years ago!  
> **username_43**: As a (very) amateur programmer that just writes scripts for a data analysis, recursion has always baffled me and I've never had to implement it thus far. But I instantly understood it with this example. So here's at least one piece of anecdotal evidence that it works for a beginner.  
> **username_44**: @PeterCooperJr. I think you're being silly; phones haven't *replaced* other computers for *any* generation, and any high-school-age kid these days is going to at least have experience with using Microsoft Office, which implies experience with saving files on a traditional file system. Pretty much the only people who are *only* familiar with phone and tablet OSes are a handful of tech-illiterate old folks whose families bought them a tablet because they thought it'd be easier to get the hang of (there's such a person in my family).  

---

### Answer by username_0 on 2018-01-09. Score: 26

One good example is to make permutations of all of the letters in a word of arbitrary length. It's quite tricky to do iteratively, since you essentially have to recreate the program stack to get it done. The recursive solution, however, is clean and clear.

Let the students try to work in pairs on an iterative solution for just five minutes. The goal would not be to actually implement it, but just to think through an approach. Then show them the short and elegant recursive answer and help them to trace through it.

> **Comments:**
> **username_28**: I think you've got it.  Actually, that's the *only* example on this page (so far) that can't be answered with just, "Okay, so what?  That's just as easy or easier without any recursion."  
> **username_45**: Permutations may be tricky to do iteratively, but a common iterative approach for "next permutation" involves using an array, not anything that resembles a stack.  

---

### Answer by username_46 on 2018-01-10. Score: 21

Writing recursive code to output the [Snowflake Curve](https://en.wikipedia.org/wiki/Koch_snowflake) (Koch snowflake) was something that definitely pushed my buttons early on.

It's formed as follows:

> The Koch snowflake can be constructed by starting with an equilateral triangle, then recursively altering each line segment as follows:
>
> * divide the line segment into three segments of equal length.
> * draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.
> * remove the line segment that is the base of the triangle from step 2.

An [animation](https://upload.wikimedia.org/wikipedia/commons/f/fd/Von_Koch_curve.gif) is also available from Wikimedia which shows the snowflake after the first few iterations.

To generalize further, many **Fractals** are generated by recursive algorithms and are thus excellent visual representations of recursion in action. The Snowflake/Koch curve is an example of a fractal that is produced by a relatively simple and easily visualizable algorithm making it a great entree into the wider world of fractals.

> **Comments:**
> **username_32**: Welcome to CSEducators. We hope to see you again. Note that we value longer posts over such short ones, especially posts that are just links that require navigating away from the site for explanation. It would be good if you could give a longer explanation of the curve, its algorithm, or why you think it is important pedagogically.  
> **username_47**: Whenever I see Koch snowflake it reminds me that in a math course we were asked to prove that snowflake curve is infinite but the area it encloses is finite.  
> **username_29**: The Sierpinski Triangle may also be a good one. To draw the triangle, draw 3 triangles (in the right places).  
> **username_48**: Fractals are the last thing I consider "motivating"...  
> **username_49**: @mehrdad but they make cool t-shirts!  

---

### Answer by username_50 on 2018-01-09. Score: 20

Other than the obvious [merge sort](https://en.wikipedia.org/wiki/Merge_sort), I really like the [minimax algorithm](https://en.wikipedia.org/wiki/Minimax), especially when applied to creating a computer player of a simple game.

Start with something simple like tic-tac-toe. When it's your turn, you can think about putting an `X` on each of the 9 squares. Then you have to think about what your opponent would do in each case. Your opponent would then think about what **you** would do if they marked an `O` on each square...

To codify this in a computer player, you can create a pretty simple recursive algorithm that exhaustively searches the space, alternating between whose turn it is, and eventually choosing whichever move leads to the most possible wins, or the fewest losses, whatever. Bonus points for pitting student algorithms against each other.

Then apply that to something more complicated like checkers or chess (or just larger or multidimensional tic-tac-toe). Here, you apply the same basic idea, but you can no longer exhaustively search the whole space because it's too large. So you have to come up with a [heuristic](https://en.wikipedia.org/wiki/Heuristic) and maybe implement [alpha-beta pruning](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning).

My point is that the algorithm itself is simple to think about and fun to play with, but it leads to lots of cooler, more complicated topics as well.

See also: [Analogy for teaching recursion](https://username_20ducators.stackexchange.com/questions/17/analogy-for-teaching-recursion)

> **Comments:**
> **username_28**: That doesn't seem to directly answer the question, as you *don't* solve such things with recursion.  
> **username_51**: I prefer Quicksort for demonstrating recursion. I learned merge sort back in the days when it would be done non-recursively using sequential I/O streams and O(1) RAM, and I've in fact found it useful in an embedded system for storing records stored on a flash chip (the flash chip had more than enough space to hold two copies of all 5,000 records, but the system had less than 3840 bytes of RAM).  
> **username_50**: @username_28 Uhh, what? From Wikipedia: `"A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game"`  
> **username_28**: @KevinWorkman I meant the part about heuristics and such, but I see your point.  Makes sense.  
> **username_50**: @username_28 Yeah, my point is that things like heuristics and alpha-beta pruning are more advanced topics that the basic recursive algorithm leads to. Programming is extremely interconnected, and I think the more connections you make from the basics to the more complicated stuff, the better.  
> **username_19**: @username_28: I had a Tic-Tac-Toe assignment I still remember in a first-year CS course.  The week after the assignment, our instructor asked who had used recursion to solve it.  IIRC, I was the only person to put up their hand.  If there was a move that forced a win, my program made it.  Otherwise it would play the first (or one of, I forget) the moves that would lead to a draw against best play.  I remember adding a random-first-move option so it wouldn't spend a couple seconds fully solving the game before making a move on an empty board :P  

---

### Answer by username_32 on 2018-01-09. Score: 13

I'm going to focus on student's understanding recursion at a fairly deep level, rather than coding.

First, to really understand recursion you need a sense of its parts. There is the *base case*, of course and most teachers spend time working on that, but students often miss it. But Before the process hits the base case there is a *winding phase* working toward the base case and after the base case is reached there is an *unwinding phase* in which all of the recursive "calls" unwind. In the execution of the algorithm, the winding phase is associated with the execution stack increasing in "height" and the unwinding case is associate with its subsequent shrinking.

One point often missed by novices is that the winding phase has just exactly as many steps as the unwinding phase.

Another point often missed by novices is that *work* can be done on both the winding and unwinding phases as well as in the base case.

Therefore, to teach recursion you need a set of examples or exercises in which the student can examine all of these in detail.

Complicating this learning is that most students learn recursion in an environment in which they have already learned to count, both upwards and downwards, and that knowledge, while useful in general, can inhibit learning about recursion if the ideas of recursion and counting (by incrementing or decrementing integers) get merged into a single idea.

Therefore, I propose a sequence of active learning exercises, that don't involve coding, but in which the students play roles (stack frames, actually, though you needn't discuss that until later), and which lend themselves to immediate discussion and analysis.

To do these you will want a deck of index cards on which to write instructions of the various roles. The recursions will all be "list-like" so a subset of your students will stand in front of the room in a row. Each student will have a card for the current exercise. Your role is to keep things moving so that the "execution" corresponds to that of a computer. I assume that the students are arranged "left to right" at the front, with the "base-case" person at the right furthest from you.

## Exercise one - Work only in the base case.

This is a fairly odd example, not likely to be part of a real program, but it can be instructive. One student's instruction card says that when they are given another card they just read aloud what is on it and then pass it back to the person that gave it to them (This person is the base case). A few others (maybe zero) each have an instruction card that says that when they receive another card they just pass it to the next person in the line, though if it is passed from the left it needs to pass to the right. You have one additional card that says "All Done". You pass this card to the first person, who passes it on, and it should eventually reach the base case and be read aloud. You should then get the card passed back to you.

Talk with the students about the phases (winding, unwinding, base) and how the number of times the card passed in is the same as the number passed out.

Run the "simulation" more than once, with at least one "run" with only the base case. Later you can run it again with a missing base case to see the error that arises.

## Exercise two - Work on Winding Phase - Tail Recursion

The instruction card for the base case is that when handed a card he or she should announce how many marks are on the card and then pass it back.

The other student's instructions are that when passed a card "from the left" they just put a mark on it and pass it to the person on the right, but when passed a card from the right they just pass it to the left.

Start the simulation by passing a blank card to the first person (who might be the base case in some "runs". The base-case person should announce the number of people prior to the base case and return the card, through the line, back to you.

At some point you can talk about how this might be mapped to a while loop and avoid all of the return steps: unwinding tail recursion.

As before, have an immediate discussion about what happened to make sure that the students got the points.

You can discuss the fact that the number of marks on the card is like a parameter to the function, also.

## Exercise three: Work on the unwind phase only.

The base case instruction is that when handed a card, simply hand it back. The others have instructions that say that they should simply pass on a card if they receive it from the left, but mark it if they receive it from the right and pass it left.

Pass a blank card to the first person and you should get back a card with one mark for each person, but no announcements. You will need to make the announcement of the number of marks.

## Exercise four: Work on both winding and unwinding phases.

Here the base-case instruction is that when given a card (from the left) with a certain number of ticks, just write the number of ticks on the card (perhaps on its back) and return it to the person who gave it.

The other student's instruction is that when passed a card from the left just put a tick on it but when passed a card from the right find the largest number on it, double that number, write it on the card and pass it back toward the right. Pass the first person an empty card and make sure you get back the correct result.

Again, a short discussion question/answer session will help solidify the ideas.

While the discussion here was long, these things move quite quickly and only a few minutes are required for each exercise and its retrospective.

However, expect that the students will get it wrong as you go, so your job is to be a coach to make sure it works ok and that the appropriate lessons are learned. Emphasize that the "data card" passed through exactly as many hands on the winding phase as on the unwinding phase.

---

If you want to emphasize the stack-frame idea a bit more, then in each of the exercises, don't line up the students initially, but pick on them one at a time when you need a new "frame". Give each student their instruction card when they stand up to join. This will require a bit more time, of course, but is more realistic and viewers won't know the depth of recursion beforehand.

---

I expect that, with the above guidance, you could also devise simple coding exercises with the same characteristics, letting students learn to carefully distinguish the phases of recursion as well as the symmetry.

> **Comments:**
> **username_28**: Bonus points if you use card instructions to implement the passing out of cards.  ;)  Actually, that would probably get a LOT more interest than just passing out the cards in the usual manner and then beginning the exercise.  
> **username_52**: When you noted `base case` I was expecting to see a follow-up with induction which didn't occur. So now I have to ask, when you say base case are alluding to induction or it is just a coincidence of words?  
> **username_32**: Recursion and induction are related, of course. So the use of `base case` seems pretty natural to me. You need a base case to avoid infinite recursion, just as you need a base case to avoid infinitely recursive definitions when using induction.  
> **username_29**: I don't agree that studying the base case, winding phase and unwinding phase is motivating at all! It feels like overly-abstract gibberish. The point is not to study how recursion works abstractly, the point is to demonstrate how it's useful. Passing cards around also feels too artificial to be a meaningful demonstration.  
> **username_32**: I think you missed the point. The phases and the base case are essential to know and understand. You need a set of tailored exercises that solidify the knowledge of all those parts to be sure the student gets it. The instructor also needs to be explicit about how each exercise uses the parts. With an incomplete understanding it is harder to be an effective program designer. This is especially true in languages that do effective tail recursion elimination.  
> **username_22**: Excercise 3 looks like it would have one mark too few?  
> **username_32**: That depends on whether you want to "count" the base case or not. If you do, the base case should also mark the card.  

---

### Answer by username_16 on 2018-01-11. Score: 8

Operating on the key word, motivate, I do believe that Andrew T. had the best choice with Tower of Hanoi. Yes, it's an old one, and it does not lead to anything useful once it's done, (the code is not reusable for some other "real world" problem.) Yet it remains a classic for some reason. I'm going to speculate that the reason is that when presented properly it motivates the students to think about using recursion for other purposes. As to what the motivation is - simple: less work! AKA - unmitigated self-interest. Who doesn't like the idea of getting something done fast and easy, preferring instead to do it the long and hard way while getting the exact same results? That suggests that the motivation comes from the presentation, not from the example used.
With the Tower of Hanoi example, adding in the "legend" of the back story can help with interest, but it can also be a waste of classroom time. Using the legend, or not, is a judgment call for your class and your style. (I have encountered at least three versions of the legend, and I am partial to the version that mentions the walls of the temple crumbling into dust and the world vanishing.)
The key to the presentation is to begin with solving it using an iterative approach. Preferably even before you raise the idea of recursion, leaving the alternative as a way out of the maze later. In a comment, Eric Lippert states that it is easier to solve with an iterative algorithm using these steps and rules: "number the disks in order of size; never move a larger disk onto a smaller disk, never move an odd disk onto an odd disk or an even disk onto an even disk, and never move the same disk twice in a row." That sounds good, and you can present it, just as given, in the classroom. Before trying to code it, however, give it a try physically. Using that rule-set with 5 disks I get the following:

Only disk available is 1, move 1 from A to B.
Disks 1 and 2 are available, just moved 1 so only 2 is left. It cannot go on top of 1 (reverse sizes) so move 2 from A to C.
Disks 1, 2, and 3 are now available. 2 just moved, and 3 cannot go on top of 1 (reverse sizes) or 2 (reverse sizes), so 1 must move. 1 cannot go on 3 (odd on odd), so move 1 from B to C.
Disks 1 and 3 are available. Disk 1 just moved so we must move 3. It cannot go on 1 (reverse sizes) so move 3 from A to B.
Disks 1, 3 and 4 are available. Disk 3 just moved, so only 1 and 4 can move. 4 cannot go anywhere (reverse sizes) so 1 moves. 1 cannot go on 3 (odd on odd), so move 1 from C to A.
Disks 1, 2, and 3 are available. 1 just moved, 3 cannot go anywhere (reverse sizes) so 2 moves. 2 cannot go on 1 (reverse sizes), so move 2 from C to B.
Disks 1 and 2 are available. 2 just moved, so 1 is next. 1 Can go on top of 2, OR to the empty post.

The given rules offer no guidance for the next move, and computers must have rules to follow.
There is another iterative approach, which does work for creating an algorithm. It has a setup rule, a movement rule and a cycle to repeat. The puzzle usually does not give the arrangement of the posts, only that there are three of them. It is commonly displayed, or presented, with the posts being in a straight line. It can, however, be presented as an arrangement of three posts in a triangular formation, like the image below. In either case, working this iterative approach needs to treat the set of posts as a wrap-around collection, being able to move between the posts infinitely in either direction. The triangular formation makes that easier to visualize than the linear formation.

If we consider the top-left as post "A" (the source post), the top-right as post "B" (the target post), and the bottom-center as post "C" (the working post), then the setup rule is:

For an odd number of disks, the smallest disk moves clockwise, and for an even number of disks the smallest disk moves counter-clockwise.

The movement rule is:

With the disks numbered from smallest, as zero, to largest, disks with an even parity always move the same direction as the smallest disk, and disks with an odd parity always move in the reverse direction.

Finally, the cycle for the moves is:


Move the smallest disk.
2. Move the only other "legal" move.


Using that two-move cycle, following the movement rule, will solve the puzzle in the smallest possible set of moves. Performing that in class with a 6-disk set shouldn't take very long (about 90 seconds without commentary, 2 or 3 minutes with decision commentary). Especially true if you have previously labeled the disks with their numbers, and marked them in some fashion to show which way they move so that you don't get confused during the demonstration. (Overheads, projector, or animation on screen works as well, but physical objects may have an enhanced long-term effect.)
Now, you have the students primed to learn the power of recursion. The rules for the iterative solution are oh, so simple. Turning those rules into an actual no-fail algorithm, with decisions mapped out, is not so simple after all. As humans, we can see, instantly, where the smallest disk is, which disks are able to move, and almost instantly reject the illegal moves when there are two open disks at the same time. Setting all that human ability into formal codified logic that can be followed blindly and achieve the desired result turns out to be much more difficult than it sounds.
Having not dealt with Hanoi since the middle 1980s, I think I can consider myself as having an almost fresh perspective on the problem. Trying to codify the algorithm for the above rules took up quite a bit of my spare time. I cannot put an amount of clock time to it since it was a "between-times" progress when other issues weren't pressing. Still, it took me the better part of a day to be confident in my algorithm and put it into code. With that in mind, I'm not sure if you should task the students with converting the above rules into a formal algorithm or not. Perhaps you can walk the class through developing one or two of the decisions within the algorithm to give them a sense of the work involved.
The main objective of the presentation up to this point is to help them to see, or experience, how much effort goes into creating the solution using the coding skills they have. Then they are ready to see the power that recursion can give them when the situation is right. Re-address the Hanoi puzzle to show that is can be reduced to a collection of smaller sub-problems that are the same as the original problem, except for size. Any solution that works for the main problem also works for the smaller sub-problems, and any solution that works for the smaller sub-problems also works for the main problem. Use that recognition to design a recursive approach to the solution. Hopefully, the amount of time spent finding the (un-coded) recursive solution is nearly the same as was spent finding the (un-coded) iterative solution, showing that finding the basics for the solution is pretty much the same for either approach. Then the magic happens when the un-coded recursive solution is written into pseudo code, or live code in the chosen language. If you have a coded version of the iterative solution to present, and then they write, or are shown, the recursive solution, they will see that dozens of lines have been reduced to about a dozen (depending on the language used). Reduced lines, with simpler logic means less typing, less chance for bugs and errors, and less work for them.
Once they see the benefits of recursion, you can also deliver the caveats (with examples if you have them) which includes:

The recursive solution may not be the shortest
The recursive solution may not be the fastest
A recursive solution may not exist for a given problem
A recursive solution might take longer to create than an iterative vesrion
Recursive solutions can create issues with the stack, and memory management
Recursion is not, by itself, faster or slower, than iteration
Recursion has to have the base case built in to the model, there is no outside decision maker


This is also a case where the recursive solution is faster, significantly, than the iterative solution. Running a series of time trials, with the output comment out and disk count set to 25 (33,554,431 moves), the iterative solution averaged 1m22.4s and the recursive solution averaged 0m28.4s.
Granted, my code is in Perl, and most of your classes are in Java, C++, or a functional language, so it would have to be converted for use in your languages. I took advantage of a few of the patterns inherent in the puzzle solution, and stated the "tricks" used in the comments. I did not, however, try for serious optimization or other forms of code cleaning. In spite of that, this is the final version of a tested, and timed, version of the Hanoi puzzle using an iterative approach:
#!/usr/bin/perl
use strict;
use warnings;
use 5.10.0;
my $disks = 20; # How many disks to use for the game.
sub move_tower_iterative { # (height of tower, souce post, destination post, spare post)
    my ($height, @names) = @_; # Collect the parameters
    my @posts =  ([reverse (0 .. $height-1)], [], []); # The post, to track the state of the game
    my $rotation = ($height % 2)? 1 : -1; # Direction the smallest disk moves
        # 1 is source -> destination -> spare -> source ...
        # -1 is source -> spare -> destination -> source ...
    my ($disk, $from, $to) = (0) x 2; # Temporary data, pre-loaded for the first move
    do {
        # Figure out where the disk to be moved will go
        $to = ($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3;
        # Take the disk off the top of one post
        $disk = pop $posts[$from];
        # Add it to the top of the other post
        push $posts[$to], $disk;
        # Say what we did
        printf "\tMove disk from %s to %s\n", $names[$from], $names[$to];
        # Find the next legal move
        if ( 0 != $posts[$to][-1] ) { # Was the smallest disk NOT the last move? Then move it.
            # It will be found where the just moved disk would move to, if it was to move again.
            $from = ($to + $rotation * (($posts[$to][-1] % 2)? -1 : 1) + 3) % 3;
        }
        else { # Not moving the smallest disk means finding the one other legal move
            while ( # Starting with the same post we just moved from check if ...
                    ( -1 == $#{$posts[$from]} ) # The post is empty 
                    || ( # OR both
                        ( -1 != $#{@posts[($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3]} ) # The destination post is not empty
                        && ($posts[$from][-1] > $posts[($from + $rotation * (($posts[$from][-1] % 2)? -1 : 1) + 3) % 3][-1]) # AND has a smaller disk
                    )
                    || ( # OR both
                        ( 0 == $posts[$from][-1]) # The post has the smallest disk
                        && ($#{$posts[$from]} != $height-1) # AND the post is not full
                    )
            ) { # Keep looking for by cycling to the next post
            $from = ++$from % 3;
            }
        }
    } until ($#{$posts[1]} == $height-1); # Stop when the destination post is full
}
move_tower_iterative $disks, "Back-left", "Back-right", "Front" ; # Start moving.
1;

To balance that out, and to show the difference, here is the recursive version, also tested and timed. In this case I've removed the comments, just as a visual enhancement of the difference between the two versions:
#!/usr/bin/perl
use strict;
use warnings;
use 5.10.0;
my $disks = 20;
sub move_tower_recursive { 
    my ($height, $source, $dest, $spare) = @_;
    if ( 1 <= $height) {
        move_tower_recursive($height-1, $source, $spare, $dest);
        printf "\tMove disk from %s to %s\n", $source, $dest;
        move_tower_recursive($height-1, $spare, $dest, $source);
    }
}
move_tower_recursive $disks, "Left side", "Right side", "Center" ;
1;

> **Comments:**
> **username_17**: This is the best answer for motivating recursion, in my opinion.  
> **username_16**: @username_17 Welcome to [username_20ducators.se]. I hope we see you around here often. I don't like Tower of Hanoi puzzle as a project because the work, or the solution to it, cannot be reused. Yet, when presented well, it can show the power of recursion and motivate students to explore the technique and develop the mental muscles to use recursion when appropriate.  
> **username_17**: Which is exactly what the question is about! =) And I said your answer is great, not just the Tower of Hanoi.  

---

### Answer by username_18 on 2018-01-10. Score: 8

Tree Traversal
Let's compare the recursive and iterative approaches to doing an in-order traversal of a binary search tree.
Recursive approach
void orderedTraversal(const Node *node, void (*f)(int)) {
    if (!node) return;
    orderedTraversal(node->left, f);
    f(node->val);
    orderedTraversal(node->right, f);
}

Iterative approach
typedef struct StackNode {
    Node *node;
    int state;
    struct StackNode *next;
} StackNode;

StackNode *push(StackNode *stack, Node *node, int state) {
    StackNode *newNode = malloc(sizeof *newNode);
    assert(newNode);
    newNode->next = stack;
    newNode->node = node;
    newNode->state = state;
    return newNode;
}
StackNode *pop(StackNode *node) {
    StackNode *next = node->next;
    free(node);
    return next;
}

void orderedTraversalIterative(Node *node, void (*f)(int)) {
    int state = 0;
    StackNode *stack = NULL;

    for (;;) {
        switch (state) {
            case 0:
                if (!node) {
                    state = 2;
                    continue;
                }

                stack = push(stack, node, 1);
                state = 0;
                node = node->left;
                continue;
            case 1:
                f(node->val);

                stack = push(stack, node, 2);
                state = 0;
                node = node->right;
                continue;
            case 2:
                if (!stack) return;
                node = stack->node;
                state = stack->state;
                stack = pop(stack);
                continue;
        }
    }
}

Of course, with a few macros, we can make the logic a bit clearer...
#define CALL(NODE) \
    stack = push(stack, node, __LINE__); \
    state = 0;     \
    node = NODE;   \
    goto start;    \
    case __LINE__: \

#define RETURN do {       \
    if (!stack) return;   \
    node = stack->node;   \
    state = stack->state; \
    stack = pop(stack);   \
    goto start;           \
} while (0)

void orderedTraversalIterative(Node *node, void (*f)(int)) {
    int state = 0;
    StackNode *stack = NULL;

    start: switch (state) {
    case 0:
        if (!node) RETURN;
        CALL(node->left);
        f(node->val);
        CALL(node->right);
        RETURN;
    }
}

...and reveal that the iterative approach to this problem is to manually build a call stack mechanism so we can go back to using the recursive approach.

> **Comments:**
> **username_14**: Now all we need is a motivating example for using a tree structure.  
> **username_19**: Anything where you need a stack data structure to implement iteratively is a potential candidate, including the https://en.wikipedia.org/wiki/Ackermann_function (which has the advantage of not needing a data structure as input.)  
> **username_18**: @StigHemmer Lookup over ordered sets (e.g. std::map) or sets with string keys (usually in the form of a trie), abstract syntax trees, network flow (minimum spanning trees), pathfinding (really, almost anything involving graphs will have a tree somewhere), hierarchical clustering, minimax, suffix trees...  It's like asking when you'd use an array, or a variable; I'm almost not sure where to start.  Of course, some of these also have non-tree-based ways to do them, and the exact functions will differ from the binary search tree example, but they'll all use recursion somewhere.  

---

### Answer by username_14 on 2018-01-11. Score: 6

Several answers have said things like "We need recursion to handle tree structures." The problem with this type of answer is that the student then asks "Why would we have a tree structure in the first place?"

@username_37's example of handling directories with subdirectories is probably the best answer, but there are others.

My favorite example where recursion feels natural is **Parsing**. For many parsing tasks, a [recursive descent parser](https://en.wikipedia.org/wiki/Recursive_descent_parser) is the easiest approach to take.

For example, parsing [JSON](https://en.wikipedia.org/wiki/JSON):

The top level will something like `ParseItem`, a function that takes an input stream and returns an data item corresponding to the JSON found there.

This function looks at the first characer to find out what type of item it should parse. Depending on this, it will call `ParseObject`, `ParseNumber`, `ParseArray`, `ParseString` or whatever.

Now, `ParseArray` will set up an array and starts parsing items to fill it with. How does it do that? Why, it calls `ParseItem`! Recursion!

> **Comments:**
> **username_3**: Thank you for coming back to improve your answer! I hope that you'll continue to share your knowledge here at [username_20ducators.se].  
> **username_15**: Whatever language they are *coding* in, their understanding/definition of *it* is recursive.  

---

### Answer by username_20 on 2018-01-11. Score: 4

Show them how they use recursion in solving puzzles in their civilian life.
Sudoku
Ask them how to solve Sudoku.
What's the naive way? You have to iterate through all (roughly) 9^81 numbers, checking each board.
Assuming each check takes on plank second (we're not even close to that in real life), it will take about 3.35843803 × 10^26 years years to solve each Sudoku puzzle.
That's way after the earth falls into a black dwarf sun.
So how do we solve it?
Recursion. Find the "easiest" block to solve (meaning, the one with the least possible variation). Let's say it's the next small board:
| _ | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |

So you that first blank could be a 4, 3, 1 or 1.
So what do you do?
You fill a four.
Then you check the board:
| 4 | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |

Does it work?
No. There are two fours in the first column. 
Try the next, and the next... until you get a one.
| 1 | 3 || 4 | _ |
| 2 | _ || _ | 1 |
--------++--------
| 3 | 2 || 1 | _ |
| 4 | _ || 2 | 3 |

Hey, that works!!
Let's move to the next blank. And you recursively [1] check each square.
How does it work?
Because each problem is a subset of the previous problem.
Here is a sample solver of a given Sudoku board (The website I found it labeled it as "very difficult"). 
The program solved it in less than a second, going through only 40,000 iterations.

In reality, that's  how most people actually solve the problem (ever seen people writing small numbers in each square, erasing ones that don't work? That's your stack!)
[1] In this case you don't need recursion, because the board is too simple. But if you take a real board with moderate difficulty, you need to take steps in, check if they work, and if not, pop out until there's another way to solve it. In short, you push and pop solutions, which is easiest to do with recursion.
A Maze
How do you solve a maze?
You go down one path? If it doesn't work you pop back to the last state where there's hope and try again.
Solving arithmetic problems
How would you solve (1-2)/((1+2)/(3-4))?
Let's assume for a moment that all order-of-operations have been taken care of through parenthesis.
The simplest way would be a recursive-descent parser.

Lex it. You now have the following lexical array: [( 1 - 2 ) / ( ( 1 + 2 ) / ( 3 - 4 ) )]
Start at position 0.
Go block by block:

If it's a regular block (a number): do something like: 
DoMath(curVal[pos],curVal[pos+1],curVal[pos+2])
pos = pos+2
If it's a 'control character' (a parenthesis in our example):

Recurse back to 3, with the 'end control character' being a 'close parenthesis'.
Replace 'n' characters (the length of the inner parenthesis expression) with the the return value.


If it's an 'end control character' (a 'close parenthesis' or an 'end-of-string tag'):
Return the value that's left after all that work.

> **Comments:**
> **username_3**: This is a really interesting first answer! Welcome to [username_20ducators.se], @username_20! I hope to see you around more!  
> **username_21**: You can do the naive way easily with recursion as well though :D  
> **username_18**: @username_21 Well, you wouldn't want to spend too much time on an algorithm that would never work in reality.  With the recursive approach, you've only wasted about 10 minutes of your life writing the naive version. :-)  
> **username_20**: @username_21 anything done with recursion could be done iteratively (through a stack data type stored in heap), and anything done iteratively can be done with recursion (as is typically done in languages without mutable variables). The real point is where is recursion more _elegant_ (especially for beginners, especially if you're teaching them a language which supports mutable variables - which 99% popular languages do - R and MATLAB (I may be wrong as I don't know them at all) seem to be the only exception in [TIOBE](https://www.tiobe.com/tiobe-index/)'s index).  
> **username_21**: @username_20 Yes I know. Generally with method calls behind the scenes a stack is operating anyway, so the recursion will indirectly be translated to an iterative approach. The point I was trying to make, but failed to do, is that for me it seems like you could interpret the answer as recursion being a whole different beast, automagically opening up a vastly improved way to  solve the Sudoku. I do not however see how recursion is more elegant with languages containing mutable variables. Isn't it the other way around? Why are most functional languages built on using recursion?  
> **username_20**: @username_21 Sorry, the opposite. In languages with only non-mutable variables, you _must_ use recursion for everything, even a simple `for` loop. The question is where could recursion be useful in a regular imperative or OOP language.  
> **username_22**: Isn't the naive approach 9^81 instead of 10^81?  
> **username_23**: That's not how you solve sudoku. It's not recursive. It's iterative and even that's not true. There are algorithms, which are neither iterative nor recursive.  
> **username_20**: @PaŭloEbermann True. You're going from 111... to 9999..., not 000... to 999...  
> **username_20**: @username_23 [This](https://play.rust-lang.org/?gist=84f488360abe78ff6a74e9301727081d&version=undefined) is my implementation of my algorithm. How is it not recursive?  

---

### Answer by username_24 on 2018-01-11. Score: 4

When teaching recursion, it is important to emphasize that the true power of recursion comes from its ability to branch. This rules out all the factorial and other similarly silly recursion examples much better written as for-loops.

Have your students write a function that, given an open tile in Minesweeper whose value is zero, opens all the tiles in the neighbourhood that are safe to open. I have used this example for about 15 years in intro to Java course, and think it is the best way to show the usefulness of recursion in a first year course.

Solving the subset sum problem in an integer array is another great example of branching recursion that is only three lines of code using recursion, and a lot more without it.

> **Comments:**
> **username_0**: This is not only a gorgeous problem, but would also work very well in an Objects-first curriculum.  
> **username_0**: Oh, and welcome to [username_20ducators.se].  I hope you'll join us in our mission here!  

---

### Answer by username_0 on 2018-01-09. Score: 4

Another approach, entirely different from my other answer, is to ask students how they might approach the following real-life scenario: they have just been given 1400 paper forms, all filled out by potential enrollees for a program. The forms arrived in the mail and are in no particular order, but they must be sorted into one of 4 geographical regions, and then alphabetically by last name/first name.

The student has been situated in a meeting room with a giant, empty table, and boxes full of forms. The student is told that the sorting needs to be done before the end of the work day. Of course, the activity itself is boring, and the student would love to get out of there as soon as possible. What approach might the student take to the task itself in order to get it done accurately and on time?

Typically, someone will almost immediately suggest sorting the sheets into subpiles. One logical number of subpiles for this first case is 4: divide into 4 piles by geographic region. Now repeat the procedure, dividing into further subpiles. While a true computer algorithm might use 4 piles again, a person would more likely use 26 piles (for the letters of the alphabet). At that point, look at the size of the piles. Repeat the procedure as many times as you need on any piles that are large enough to still be unwieldy.

At some point, you will have a series of tiny piles. A person would probably sort these small piles using some form of insertion or selection sort.

We would now reverse the process, taking our tiny sorted piles, and recombining them into larger and larger fully sorted files. These would be our recursive unwinding steps.

This entire procedure is not dissimilar from a standard mergesort (or, really, a recursive bucket sort). Divide the problem, conquer the smaller pieces, and then recombine. Breaking the problem into smaller subproblems is what makes the entire enterprise more manageable.

What's nice about this procedure as a motivator for examining recursion is that it, with only minor variations, is the natural solution that most people arrive at when faced with such a daunting sorting task because the benefits are clear and natural.

> **Comments:**
> **username_27**: I don't have problems thinking of recursive methods, but I do struggle to see how this will help. From a code POV, it will look something like: `for (s in sheets) { switch (s.region) { a: region[a].append(s) ...} }; parallel for (r in region) { for (s in r) { switch (s.name[0]) {...} } }`, and the students will still see it as imperative, though it can be written in a recursive form more easily.  
> **username_28**: Hmmm, I'm not entirely certain that students would grasp that sorting on more than one key by sorting first on one key and then on another key actually IS an example of recursion.  That sounds a little funny even to me.  
> **username_29**: You just proposed an iterative approach.  
> **username_0**: @immibis How so? I'm not seeing how breaking a big problem repeatedly into smaller subsections, fully solving the small problems, and recombining at the end is iterative. It's basically a mergesort.  
> **username_29**: @BenI. Putting the forms into 4 piles is an iterative loop. Putting the forms from those 4 piles into 26*4 piles is just two nested loops. It's not recursive because you are just saving up all the work from one step until you're done with that step. See username_27's comment.  
> **username_0**: @immibis I see that others agree with you from the upticks, but nevertheless, I still see it as subdividing and then re-merging, which is recursive. (FWIW, I am [not alone](https://en.wikipedia.org/wiki/Sorting_algorithm#Popular_sorting_algorithms) in calling this a [merge sort](https://stackoverflow.com/a/105983/4151129).) If anything, I might describe it as a recursive bucket sort.  
> **username_29**: Oh now I see what you were getting at. For some reason it seems hard to understand your example.  
> **username_0**: @immibis Do you see any way to fix my description?  Apparently I'm being unclear to many folks, but I'm unsure about how.  
> **username_29**: Perhaps it's because the intuitive way to do this is non-recursive (it's essentially a breadth-first search made with two nested loops).  
> **username_30**: @BenI. I think the major problem of the algorithm is the fixed recursion depth of only two levels. If you had done something like "*split by 4 regions. Every pile higher than 10 sheets, split by first letter of name. Every pile higher than 10 sheets, split by second letter of name. Every pile still higher than 10 sheets…*" the recursive approach (with "*small enough pile*" as base case) would have been clearer. Using different things (4 regions and 26 letters) in the two first steps didn't exactly help either.  
> **username_0**: @username_30 Thank you!!!  I re-wrote it significantly to try to make it more obvious.  Is it better now?  
> **username_30**: Thanks, much better. However the core part of the recursion ("*Repeat the procedure as many times as*") still doesn't stand out over the clever sorting algorithm, so I'm not sure the students will grasp the difference between "recursion" and "divide-and-conquer".  

---

### Answer by username_30 on 2018-01-11. Score: 4

# Construct an immutable nested structure

It's obvious (to us instructors) that in a purely functional language, recursion is the only way to create nested structures. And immutable data is imperative (pun intended) for proper semantical reasoning about values.

So what kind of examples lend themselves to an intuitive recursive approach where an imperative approach is much harder?

* **Nested data structures** like linked lists, trees and graphs are most easily traversed and constructed recursively.

  Linked lists are too simple, the tail recursion has the same idea as the equal imperative loop and can be written as such without involving an explicit stack. Graphs are too complicated as keeping state (e.g. to avoid infinite descend) and creating cycles is easiest to do using mutation, and many introductory graph algorithms *do* keep an explicit queue of nodes. Graphs without cycles are just trees. Here I would avoid n-ary trees where nodes keeps lists/arrays/vectors of children, as those again would typically be accessed in an (imperative) loop, which confuses the students (making the gist of recursion harder to recognise, and obfuscating the base case).

  So binary trees it is. A simple tree of integers can be summed, scanned for its maximum and/or minimum, and mapped over with e.g. an incrementing or doubling transformation. It might even be filtered for odd/even numbers. Later you can introduce the respective abstractions (`fold`, `map`, `filter`) if you want.

  I would recommend to avoid algorithms for balancing trees here, those are often rather unintuitive when expressed recursively or at least differ much from the imperative approach that is found in most teaching material.
* **Immutable data structures** cannot be re-initialised or changed during traversal. This again prevents imperative solutions e.g. in the `map` exercise.

  If you are using a functional language in the course, this requirement is probably easy to place. However this doesn't satisfy imperative-minded students who will think "if I could just mutate the data (like in $favouriteLanguage) this task would be much easier".

  If you are dealing with an imperative language, you will need to make up some excuses for why immutability is necessary. Constructing not a single but many distinct results helps here. They might be output as a side effect, but are going to get used later after the algorithm ended. Building an animation sequence that can be replayed later (and also rewinded, or run backwards) might be a good idea, which also provides the students with some visualisation.

  Computing permutations [as suggested by username_0](https://username_20ducators.stackexchange.com/a/4144/660) is a perfect take on this - instead of just printing all permutations (doable by mutating a sequence) many distinct arrays/lists need to be created. Computing the power set, the subsequences or substrings of an input are similar tasks (and don't even require loops because of the nature of the binary decisions). Here, the concept of sharing between data structures can be introduced as an advantage of immutability later in the course (demonstrated by memory requirements of responses to huge inputs).

> **Comments:**
> **username_0**: Excellent, helpful answer. Welcome back! :)  

---

### Answer by username_25 on 2018-01-10. Score: 3

I'd suggest some version of string length, implemented recursively.  It's even simpler than factorial.  You just break one character off the string, feed it to a recursive call and add one to the result.  With that we can teach the essence of recursion.
I find programmers often get confused by trying to "be the computer" working out the recursion to depth rather than working abstractly.  So, one trick is to get the aspiring programmers to look at the recursive invocation as a black box rather than to try to think of what's happening at depth.  Within the implementation of a recursive function, we want to be able to use the recursive function as if we are merely a client consuming some other function (that already exists and provides some usable capability) with little to no concern about the actual recursion itself.
We always have to switch our hats from provider of an implementation to consuming client.  The trick with recursion is to be able to do that with the same function as its implementation is itself a consuming client (of itself).
One approach is to start something like this:
int string_length(char *str) {
    if (*str == '\0')
        return 0;
    return 1 + strlen(str+1);
}

With the objective of looking at strlen() as a black box that just works (here: just what it does for us, not how), and then understanding how this string_length() works (e.g. just those three lines of implementation).
Then introduce the idea that since we have confidence that string_length() works — that it does the same thing as strlen() — we can use it in our own implementation: substituting string_length() for strlen().

> **Comments:**
> **username_0**: This is a nice, clear example of recursion, but is it a good *motivating* example for the entire process?  The iterative version (such as the simple `for` loop) is both more efficient and simpler to write.  

---

### Answer by username_26 on 2018-01-11. Score: 3

If the students have learned object-oriented programming then network-traversal or tree-exploration works well because it is easier to visualize one node calling another than to visualize a method calling itself. Start with a directed graph with no cycles so you don't get infinite loops.
//returns true of this is part of the path
public boolean findLastNode(List pathSoFar)
{
    if (this.isLastNode())
    {
        path.add(this);
        return true;
    }
    for (Node aNeighbor:this.getNeighbors)
    {
        if (aNeighbor.findLastNode())
        {
            path.add(this);
            return true;
        }
    }
    return false;
}

The code is easy to visualize and draw on the whiteboard because each recursive call moves you across the graph, and you can visualize each node having its own copy of the findLastNode method so you don't have to think of the flow of control reusing variables that are already holding other data.

> **Comments:**
> **username_23**: Welcome to [username_20ducators.se]! This is a very interesting answer.  

---

### Answer by username_24 on 2018-01-11. Score: 2

Since these did not need to be programming examples, here is another example that I like to use and have found illustrative.

When you need to write a method to solve some problem, you must write that method using the things that you already have: the statements in the language, and the methods already in the standard library or written by you. Your job is to find the right combination of these that will achieve the job.

For example, if you need to define the factorial function, you would do so with the definition

$F(n) = n \* (n-1) \* ... \* 2 \* 1$

where the right hand side contains a for-loop and a whole bunch of multiplications, two things that you already have in the language. So we can implement factorial using the things that we have.

But imagine this now as some fantasy type of setting, where this equation is a game of tug of war where the left hand side and the right hand side must pull with equal strength to balance each other out. On the left hand side, $F(n)$ is a big strong mountain giant. If the right hand side consists of little hobbits (each multiplication operation), we will necessarily need a large number of hobbits to be able to pull together as hard as the one mountain giant on the left side.

Spotting the self-similarity in the above definition allows us to turn this into an equivalent recursive definition

$F(n) = n \* F(n-1)$

which at first seems like cheating, since we are borrowing the function $F$, the thing that we were supposed to define, from the future to be used in its own definition! What do we gain from doing this trick? Well, since $F(n-1)$ is now on the right hand side, it is now a big friendly giant that is pulling for us, instead of pulling against us, in this game of tug of war!

Nothing in that observation depends on the fact that $F$ is particularly the factorial function. In fact, the more complex and powerful the giant is when placed on the left hand side (for example, consider the problem of parsing), the more powerful it is also when it is working for us on the right hand side.

This realization allows us to solve arbitrarily complicated problems by using a slightly smaller version of those problems on the right hand side. In the game of tug of war between one giant and one slightly smaller giant, we only need to add a couple of small hobbits on the right hand side to balance the whole thing, instead of having to put down some large number of small things to balance one big thing. This is the power of recursion.

> **Comments:**
> **username_19**: This some interesting hand-waving and analogy, but does nothing to change the fact that `prod *= i;` in a loop is just as easy to write, and runs faster (unless the compiler optimizes your recursion back into a loop).  The problem has no stack-like state that needs to be preserved for back-tracking, so recursion isn't helpful or necessary for factorial.  I know you didn't mention Fibonacci, but recursive Fib is even more dumb because it takes O(Fib(n)) time instead of O(n) time for a `a+=b; b+=a;` loop. Recursive Factorial doesn't make the complexity class worse, so it's not as bad an example.  

---

### Answer by username_31 on 2018-01-12. Score: 2

In my first programming class, I "discovered" the concept of recursion on my own, before it was introduced by the instructor. It wasn't the typical use-case for recursion, but it was enough to jump start my thinking.

I was creating a really simple 2D tile based game, and was working on the graphics. I had a function that took an ID number that represented what kind of tile to draw, and the X,Y coords to draw it. I had already implemented grass (ID 1), by simply drawing a green rectangle, with a few pixels of off-green. When I went to draw a Tree (ID 2), the tree was supposed to have a grassy background behind it. I didn't want to duplicate the grass drawing code again for the tree Tile, and after thinking about it for a while, I thought "Hey, I could just call the drawing function again, and tell it to draw the Grass tile at the current coordinates, then draw the tree over top of it."

I asked the teacher if a function was allowed to call its self. He got a strange look on his face, and asked me to show him what I was doing. He explained a little bit about what was actually happening, and told me that what I was doing actually had a name. He said that it would be covered in a lot more detail in a few weeks.

For me, it was a simple way to see the *idea* of recursion as a real physical thing, without having to deal with the mathematical abstractions that things like the Fibonacci Sequence require.

> **Comments:**
> **username_32**: Now that is a cool story. Welcome to CSEducators. There is a lot here that might interest you.  
> **username_0**: You didn't quite state this, but your answer brings up the possibility of seeding the field by simply utilizing recursion in front of the class at some prior time. The way I envision it, I would point it out, but leave it largely unexplained until we got to the proper unit.  This would serve to let them know that the possibility existed and feed their curiosity naturally, so that when we later get to the unit, they would be interested in exploring that oddity.  (If you like that, feel free to integrate it; it would also give a classroom tie-in, which you are currently missing.)  

---

### Answer by username_19 on 2018-02-23. Score: 2

I think what makes Factorial and Fibonacci popular as teaching examples is that **they have no input data**. This means student implementations can start from scratch, instead of being given some boiler-plate data declarations. (Or requiring the students to write code to create a binary tree or something.)

[The Ackermann–Péter function](https://en.wikipedia.org/wiki/Ackermann_function) `A(m,n)` has 2 integer inputs and one integer output so it's nice and simple like Factorial (no pointers or references to any data structures). But its natural definition is recursive, and iterative implementation requires a stack of some sort, so a recursive implementation is easier than iterative.

It's not ideal (for testability over a range of inputs) that it grows so quickly, and you may need to introduce the concept of integer overflow (with wraparound, or undefined behaviour in languages like C for signed `int`). On the other hand, students will probably think it's cool to have a function which can produce such large outputs from small inputs. `A(4,2)` has 19,729 decimal digits.

But with `m=[0..3]`, the [result fits in a 32-bit integer for a wide range of `n`](http://www.wolframalpha.com/input/?i=ackermann(3,n)%20for%20n%3D0..10), so it's testable.

---

IMO recursive Fibonacci is a really horrible example. It has O(Fib(n)) complexity instead of O(n) time for an `a+=b; b+=a;` loop. Recursive Factorial at least has the same complexity class as iterative, but it doesn't require keeping any state.

In an assembly-language assignment (especially when args are passed in registers), Factorial also fails to fully test recursion because no registers need to be saved/restored (except the return address for RISC architectures like MIPS that use a link register instead of x86-style `call`/`ret` pushing/popping a return address). There's not much difference between an iterative loop and the body of a recursive implementation. You could get implementations that recurse down to the bottom and then just multiply by an increasing counter while returning back up the call chain.

Recursive Fibonacci avoids this problem: needing to make two separate calls from the same function means it can't degenerate into a loop. But we'd like to reject Fib because it makes recursion look like a stupid way to make programming harder, especially in assembly language.

(Do people really give recursive Fibonacci assignments in assembly language? Yes, they do, and Stack Overflow has the questions from their students to prove it. It is one of the simplest doubly-recursive functions (significantly simpler to implement in asm than Ackermann), but it's maybe so simple that it's not as obvious which state is the "important" state that needs to be saved/restored across child calls.)

[A recent Stack Overflow question on MIPS assembly](https://stackoverflow.com/questions/58127916/double-recursion-in-assembly-works-until-secondary-recursion-becomes-larger-than) (from a student assigned this homework) appears to have found some useful middle ground here with a function that has similar doubly-recursive structure to Fibonacci but is less trivial, making an iterative implementation less obvious.

And also simply not being a well-known function means that there aren't implementations of it all over the web in many languages, reducing the temptation to copy/paste.

* `if n>5` : `f(n) = n*f(n-1) - f(n-3) + n-23`
* else `n<=5` basecase `f(n) = 15 - 2n`

An iterative implementation is still easily possible and obviously more efficient, especially for large `n` without memoization. But this has a couple useful features that make it better than Fib(n):

* The base case includes more `n` values, and is not totally trivial. Initializing vars for an iterative implementation would take some care.
* Using `f(n-3)` and skipping `f(n-2)` means iterative would have to keep more temporaries, but doesn't add complexity to a recursive case.
* Using the original `n` *after* both of the recursive calls (to multiply the return value, or add to the total) motivates properly keeping it around. (vs. maybe writing an asm function that preserves its input register, and just decrementing that again to create an input for the next call. That would work but is totally non-standard for normal C calling conventions.)
* Clever students will notice that `n` can be destroyed by the 2nd recursive call, doing `n - 23 + n*f(n-1)` early because integer `+` is associative. Otherwise they'll have to save both the first return value *and* the original `n` if they evaluate the expression in the order written.
* It's not Fibonacci so it's not recognizable as a well-known thing that can be looked up or that some students will already know about.

---

**[Tree traversal](https://username_20ducators.stackexchange.com/questions/4143/what-are-good-examples-that-actually-motivate-the-study-of-recursion/4151#4151)** is one of the best example use-cases for recursion, because you need to remember where you've been at each step of the problem, so any solution needs a stack data structure. Using recursion lets you use the call-stack as your stack.

But you need a tree to traverse, so it's not as "simple" as Factorial.

And it's easy to see that it's a useful thing to do.

> **Comments:**
> **username_16**: Excellent answer. Welcome to [username_20ducators.se]. I hope we see you around more. We have a few questions that broach the subject of [tag:assembly] language level thinking here as well. Maybe you will find them interesting and worth answering.  
> **username_19**: @GypsySpellweaver: I had a look at some of the questions, but I don't know much about teaching asm to people who don't get it.  I literally don't understand why people find asm hard to learn, because it wasn't for me.  It's like building a robot; you put some pieces together to create a machine that does something useful one step at a time.  I know some people "don't get it", but I don't know how to put myself inside their head to understand why not, or if there's something you could tell them that would let them think about asm (and how computers work) in a useful way.  
> **username_16**: It was worth a try anyway.  

---

### Answer by username_33 on 2018-01-11. Score: 1

When i was introduced to recursion, i felt the same on why learning something i don't need but using iterative approach on complex situations like **Tower of hanoi** etc., using recursion seems to be more simpler in logic as well as programming.

The reason i like recursion:

You don't need to solve or think about whole solution. You can break the whole problem in smaller ones, and use those solution to solve the bigger problem. And this helps to think more clear logic for your problem.

Algorithms that makes sense using recursion:

* Tower of Hanoi
* Quick sort
* Graph traversal(Inorder, preorder, postorder)
* and so on...

If you want the students to feel interested in it, you can *try giving an assignment of solving tower of hanoi using iterative method*. And then using recursion, the students will themselves know which method to use where and why :)

Note: Look for **ackermann function** as well.

> **Comments:**
> **username_32**: Welcome to CSEducators. I like this answer. If you want to improve it you could add a link or two, especially to a writeup of Ackerman's function. Better yet, explain a bit about why it is important.  
> **username_3**: This list of possible algorithms doesn't really add anything to the already existing answers. Can you add some depth so that your answer *adds* to the other answers rather than simply restating them?  
> **username_34**: Well, better show recursion on example where the recursive approach is the _obviously_ simplest solution to a problem. Not everybody comes quickly to a solution to the Hanoi problem, if ever. Same for sorting.  

---

### Answer by username_32 on 2018-12-28. Score: 1

From [Douglas Hofstader's Metamagical Themas](https://rads.stackoverflow.com/amzn/click/0465045669), comes the idea of the Porpuquine.

A nine quilled porpuquine has nine quills, each of which is an eight quilled porpuquine. Of course an eight quilled porpuquine has exactly eight quills, each of which is a seven quilled porpuquine. Etc.

Of course, you can explore Quine. And you can do some computing.

The more complete story in the book is worth a look, of course.


---

### Answer by username_35 on 2018-01-10. Score: 0

The answers are fantastic but what I see you looking for is a motivation for using recursion over other methods. The answer goes back to why one goes to school in the first place. Not to learn what we already know but what others know, which will in the long run prove valuable.

The reason we use recursion generally is not because it is the only solution (well trained CompSci grads can think of little else) but because it is what computers are good at. Particularly;
1.Starting a problem.
2.Putting it onto the stack in order to
3. Go to another problem.
This is done all the time. The point of recursion is that each of these steps is for the same purpose. It is not until all the processes are done that they look around to see that there was only one goal, not O sub n goals.

Using minor examples can show off the major achievement of this level of organization.

> **Comments:**
> **username_32**: Welcome to CSEducators. We hope to see you back again.  
> **username_32**: There doesn't seem to be an example here responding to the question. Are you saying none are necessary? Can you clarify?  
> **username_3**: I agree with username_32. This does not appear to actually answer the question. If you want to discuss the question's premise, feel free to do so in the chat room I mentioned in my comment on the question.  
> **username_35**: I think the brief answer gave the structure of why recursion is useful based on what computers do well. This goes to the fundamental reason to teach it rather than more and more examples of it.  

---

### Answer by username_36 on 2018-01-12. Score: -1

Water is a good example, when you pour a jug of water compare it to the algorithim the algorithim or water is continually poured until there is no more water left or the base condition is satisfied, leaving you with a solution, comparing a water fall to a bad case of infinite recursion it just continues flowing.

> **Comments:**
> **username_0**: Welcome to [username_20ducators.se]! How will the example of water illustrate to students why they need to *learn* recursion?  
> **username_3**: To add to what Ben said, this same task could be accomplished with a `while` loop. Why would this example help students see the necessity of recusion?  

---

