Recursion in Scratch 2

With the release of Scratch 2 came the ability to create your own blocks, which in programming terms is the ability to create your own procedures or methods. One thing you can’t do with custom blocks is to return values from any computation performed in your block. You need to assign the result of any computation to a variable.

In this post we are going to look at recursion. The first question you may ask is “what is recursion?” — Simply put, recursion is the ability for a function/method (I tend to use the term method, but in the context of this post, they mean the same thing) to call itself. Now, with the advent of custom blocks in Scratch, recursion becomes possible. Before custom blocks, a form of recursion was possible in Scratch using broadcast blocks. There is a complete article on the Scratch Wiki about recursion, and I would recommend you read it. it can be found at http://wiki.scratch.mit.edu/wiki/Recursion.

So, first, lets have a simple recursion example. Consider you want to be able to count backwards from a specific number down to 1, easy, just use a loop, and to be honest that would be the best way to do this, but this simple example does give a good, simple introduction to recursion. First, lets have a look at how we would do this in a loop, defining a custom block.

Count Loop

We can then call this by simply using the CountLoop block and providing a parameter, say 10, and this will count down from 10 to 0, nothing particularly difficult here. Now consider the version below.

Recursive Count
The first thing to notice is that there is quite a lot less ‘code’ in this version. The second thing to notice is the last line in the IF block, our block is calling itself, and this is where the recursion happens. So, consider what happens when we first call the block, this is what happens:

1. We call the block with the parameter 10
2. The IF block checks if the value passed in is greater than 0. If it is, we display the value of n.
3. After displaying the value, we call the block again, using the value of the parameter that was originally passed in (10) minus 1. So the block is called with the value 9, and the whole process starts again.

This will continue to happen until the value passed in is 0 and then it will end.

Base Case

The IF block in our recursive block is very important. In programming terms, this is called the base case. The base case determines when the recursion will end. If there was no base case, the block would call itself forever, the same as an infinite loop (think forever block!).

Recursive Case

The opposite to the base case, is the recursive case. The recursive case is what happens when the base case has not been satisfied, in our example, its what happens within the IF block.

A More Realistic Example

Whilst the example above was perfectly valid to introduce the concept of recursion, you would usually use the loop construct to achieve the desired result. Lets look at something more valid. Very often, recursion examples use calculating the Fibonacci Sequence as an example. I’m not going to use this, I am going to use the calculating the factorial of a number, this lends itself well to explaining issues with recursion and also lends itself well to explaining an issue with recursion in Scratch 2.

Calculating the factorial of a number is easy, its the product of all the numbers (positive numbers) less than or equal to the number you provide. So the factorial of 5 is equal to 5x4x3x2x1, which equals 120, so the factorial of 5 is 120. So first how would we use a loop in Scratch to calculate the factorial of a number. Well we could do the following:

Factorial Loop
A fairly simple piece of code to calculate the factorial of a number. You will see if you call this block with the parameter 5, the variable result will contain 120, which is what we want. So, how do we do this recursively? Before I explain how to do this in Scratch 2, I want to move on to a little bit of programming theory, stick with me here, hopefully this won’t be too bad!!

If I was asked to implement a recursive factorial method in a programming language of my choice, I would use C# (designed and developed by Microsoft and part of the .NET Framework). I’ve used many languages over the years, but all my coding now (both home projects and work) is mainly in C#. This code will be easy to understand, so don’t worry. So, how could I implement this in C#, well I could do the following (for any programmers looking at the method below, you probably would replace the int with a long):

public int factorial(int n)
{

    if(n <= 1)
        return 1;
    else
        return n * factorial(n – 1);
}

We can then use the method as follows int result = factorial(5); and you should get the answer 120.

Right, so how does this work ‘under the covers’ when the method is called. Firstly, unlike Scratch, we can return values from our method, and this is a blessing, but in recursion, it can also be a nightmare. When a program is running and a method is called, it needs to know where to return back to when the method call has completed. An area of memory called the stack is used to hold this information. With recursion, each time the method calls itself, information is saved on the stack, so when the call finishes, it knows where to go back to. The stack is not infinite in size, so if you make a large amount of calls, the stack can become full up and you will get an error. When using C# (or any other language for the .NET Framework), you will receive StackOverflowException and you then have to go and fix this. I can remember having to fix someone elses recursive method where the stack was getting full up and it was a nightmare, the method was huge and there was no real documentation on what was going on. The eaasiest thing to do was to refactor the code to use a loop as there was no real need for it to be recursive. To show an example of what happens when the recursive method above runs, under the covers something like the following is happening when you calculate the factorial of 5:

1. factorial(5)
2. 5 * factorial(4)
3. 5 * 4 * factorial(3)
4. 5 * 4 * 3 * factorial(2)
5. 5 * 4 * 3 * 2 * factorial(1)
6.                                   returns 1
7                    returns 2 * 1 = 2
8.                 returns 3 * 2 = 6
9.             returns 4 * 6 = 24
10.    returns 5 * 24 = 120

As you can see, there is a lot going on here to calculate. The reason this is happening is because of this line of code in the method: return n * factorial(n – 1); The factorial method is being recursively called, but we also need to multiply the result of the recursive call by the previous value of n. You can see how this could cause stack problems should you wish to calculate the factorial of a large number. So, whats the recursive alternative? Well, there is an alternative, its called tail recursion and this is the type of recursion that you would ideally need to implement in Scratch 2 to recursively calculate the factorial of a number, as we have no version of the return statement in Scratch. Tail recursion may sound complicated, but to be honest, its an awful lot easier to understand whats going on than the example above.

Tail Recursion

A method is said to be tail recursive, when the last action performed by the method is to simply call itself. Looking at our example above, the recursive call is not the last action, the multiplication of the call to the method is the last action, so to be tail recursive, the last action needs to be factorial(n-1). How can we do this? Well, what we need to do is actually perform the multiplication in our method and return this back each time we call, so we need to keep a running total. Going back to my roots in assembly language programming, I’ll call this an accumulator. So we would have another parameter in our factorial method, so the declaration of the method would be int factorial(int n, int accumulator). Our method would then look like this:

int factorial(int n, int accumulator)
{
     if(n<2)
         return accumulator;
     else
         factorial(n-1, n*accumulator);
}

We would then call our method like this factorial(5, 1); You see that when we call the factorial method each time, we are sending over the result of the previous calculation. The benefit of this in languages such as C# is that the stack does not get filled up, essentally ‘under the covers’ the following happens:

1. factorial(5, 1)
2. factorial(4, 5)
3. factorial(3, 20)
4. factorial(2, 60)
5. factorial(1, 120);
6. returns 120

And because our base case says if the value of n passed in is less than 2, we return the value of accumulator, which will be 120, which is the factorial of 5. I’m sure you will agree, this looks an awful lot easier to understand than the first version!!

How do we do this in Scratch?

Some of you may be saying, well this still implements a return, how can we do this in Scratch. Well, with the single return, to do this in Scratch we would just assign the value of accumulator to a variable, as this is done in the base case, so there is nothing else needed to be done in the recursive method. So here goes, here is the recursive block that implements the tail recursive version of our method.

Recursive Factorial
As you can see, the only difference between our Scratch version and the C# version is that when the base case condition is met, we assign the result to a variable and not return it.

Conclusion

If you have got this far reading, thanks for sticking with it!! Recursion is interesting and one worth learning. As you can see, there are always ways of getting around issues with Scratch, and this also demonstrates the power of some of the new features of Scratch 2.

I have put together all the Scratch code used in the post into a Scratch solution that you can go and have a look at it. Should you find it useful feel free to use the code in your programs or teaching. The link to the solution is http://scratch.mit.edu/projects/11610916/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s