Shashi Krishna Computer Science, Education

A case of recursion

The What?

A few weeks ago I ran into this hilarious tweet,

The same tweet – as the perfect illustrative homage to the concept – was retweeted thousands of times with the same message quoted within each new tweet. This got me thinking about the complex nature of this specific concept in Computer Science. For students who master and effectively use looping structures for a long time before being introduced to recursion, it may seem like an extension to loops, albeit a pointless one. The question – “Why are we learning this, again? When will I ever use it?” or “Why cant we just use a loop for this? Isn’t that better for memory?” is a commonplace student voice in the classroom. (As an aside: I did run into an interesting 1999 research paper that argues that recursion as a concept should be taught before iterations. In fact, a Computing teacher in Malaysia works with recursive methods to introduce functions via data input validation with his students.)

A few days ago I ran into another recursion related tweet.

Despite the understandably cynical take on the list, there are few interesting examples on there of how recursion can be understood/appreciated by students. As a way to educate myself further on the state of things, as it were, I explored a few ways in which a range of resources – unplugged hands on activities included – came my way.

But before we get into the How? let us take a quick look at the Why? since anything that is worth learning needs a context. If we expect students to appreciate any concept in any subject, having a strong (and interesting!) rationale for that is critical. Who would want to learn something that is neither engaging nor useful? If teachers do not then students definitely will not. So let us try and address that for recursion first.

The Why?

The primary reasons recursion has a role and presence in computing.

  • To reduce the complexity of a problem
    There are some problems so complex that an iterative solution cannot fix. Traversing a tree structure is a common example cited for this given its dynamic nature. Recursive seems simpler for such problems purely because of it reductive nature.

    This Medium article advocates for recursion by demonstrating an array sum and tree navigation examples. While the argument can be made that an array can easily be traversed with a loop without needing recursion, condensing a problem so that it meets a natural end (as in supplying a function with a lesser value so that eventually it stops) is an approach worth noting. As far as the tree is concerned, navigating in different directions of a data structure is most efficient when done with recursion. The dynamic nature of a recursive method allows for movement up, down, left and right whereas a looping structure usually goes one way at a time (hence needing more workflows to accomplish something as complex as tree traversal).

    A question that may arise at this point is: Why do we need trees? Tree structures in software development have a wide range of applications. From file compression to network routing algorithms. All of them use tree structures to hold and process data. So if the focus is on such high performance algorithms then recognizing recursion’s impact on it is equally vital.
  • Shorter (cleaner?) code
    Shorter does not always mean better, I know. This is especially true for recursion since even though the function may contain 4-5 lines, depending on what it is doing tracing multiple calls for the same function can be a complicated thing (including how well it is managing memory). Even for seasoned developers and experienced teachers, spotting a recursive method to trace for the first time requires time and focus. All concepts need this but something that is as layered as recursion even more so.

    To illustrate from a coding perspective let us take a simple example where a function needs to build a word by collecting characters sent to it via an array. First, we will see the looping version of it. This is meant to be an algorithmic representation so actual syntax/approach may vary.

    function buildWord(char[] array) {
    String word; //to hold final word
    int N = array.size() //to know how far we loop
    for i in 0 to N
    loop
    word = word + array[i] attach each character
    end loop //loop ends here
    return word //return final word back
    }

    Now, let us consider this recursive method to do the same thing.

    function buildWord(char[] array) {
    if (array.size()==1) return array[0]; //base case for termination
    return array[0] + buildWord(array minus first character) //recursive case to keep going
    }

    Notice how base case (which terminates the function) comes first. If the array has only 1 character return just that and it is done. Else, attach it with a decreasing form of the array. So, if the array had [‘h’,’e’,’y’] originally, the return calls will be:

    ‘h’ + buildWord([‘e’,’y’])
    ‘h’ + (‘e’ + buildWord([‘y’])) //this makes base case come true
    ‘h’ + (‘e’ + (‘y’)) //values stored in memory wrapped up
    ‘h’ + (‘ey’)
    ‘hey’

    While this may seem like an overly simple rationale to use a recursive method, the idea is to build a solution that can do more with less. That said, every programming construct does have its place but recursive methods are powerful when it comes handling dynamic and large data structures. Then there is looking at memory management too. Quality trumps quantity, indeed, but not at the cost of needless memory overheads.

    You will find plenty of literature on the web that sums up the differences between iterations and recursion – such as here, here, here and here. At the end of the day the problem at hand will decide which approach is best.

The How?

Inspired by some of my recent conversations with the SEACSTA group of educators who have tried different methods in their classrooms surrounding this topic, I tried to collect some resources that could help trigger both the mindset and scaffold the learning for both teachers and students.

Hands On Activities
In addition to the popular Fibonacci sequence, Factorial, Hanoi Towers or Binary Search examples, here is a list of other activities I found.

Pass the Candy : Students get into groups and 3-4 and get N candies to start with. Then they halve it and pass it on to the partner on their left. Tracing the candy passes results in some interesting results.
Frogs in a Pond : A short collection of activities that allow students to explore the idea of recursive processing using unplugged approaches.
LEGO towers : Part of this research paper contains a LEGO tower based word activity that uses recursion.
Khan Academy Russian Doll : Tutorial that highlights different aspects of recursion with some word challenges.
Robot Maze challenge: A robot and maze activity replicable as hands on before the coding element.
The Cat in the Hat comes back : A classic by Dr.Seuss the story of cats A to Z is a good activity to read aloud, enact and try in class.
Exploring Recursion Through Art : Activities with nested drawings.

The Where?

Finally, a quick list of other interesting resources I found that address different aspects of recursion.

The bottomline

As mentioned earlier, recursions are always complex. Like any programming construct the more time one spends with it the better one can get at it. One of the biggest challenges students have is to be presented code/algorithm and asked to trace it. Activities like ‘Pass the candy!’ encourages using printed trace tables which needs to be a constant companion to be able to carefully and slowly follow the algorithm to see what it is doing. Putting students in small groups also helps since cognitive loads can be better managed.

Found this lovely little piece from a StackOverflow question on recursion. Thought it had a place here.