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/

Windows Phone 8 Emulator running in VMWare Player

A couple of evenings ago, I decided to build a Windows 8 64 bit virtual machine with Visual Studio 2012 and the Windows Phone 8 SDK, so I could have a look at writing apps for Windows Phone. The main tool I use for creating and running VM’s is VMWare Player, its free and does exactly what I need. Now, its certainly possible to build a Windows 8 VM through VMWare Player as long as you have Version 5. I downloaded the latest version which is 5.0.2 build-1031769.

I went ahead and built my Windows 8 VM. Installed Visual Studio 2012 which went fine, and then installed Windows Phone 8 SDK. This is where I did have problems, the installation did fail with the usual unfriendly error message we have come to know with some software. After a search on Google, I did find some instructions on how to do this for VMWare Workstation, so thought I would give it a try for VMWare Player, and with a little modification, I’m pleased to say I now have a VM through Player working happily allowing me to test Windows Phone 8 apps through the emulator. I have detailed below exactly what I have done to build the virtual, so if you have had the same problem, following these instructions should sort out your problems.

Make Sure your Host system is good enough

The first thing you need to do is make sure your host system is up to the job. You need to have Hyper V running on your Windows 8 virtual, so your host systems needs to support SLAT – Intel Extended Page Tables. The easiest way to find this out is to use the Coreinfo.exe application. You can download this from the link http://technet.microsoft.com/en-gb/sysinternals/cc835722.aspx. Run a command prompt as administrator and from the directory that has Coreinfo.exe in it, run the command Coreinfo -v. If all goes well, you should see something like the following:

coreinfo

Looking at the last line, if this says Supports Intel extended page tables (SLAT) all is looking good. If SLAT is not supported, don’t continue with this, as I would say it isn’t going to work. Note: The asterisks are important here, if you see a hyphen instead of an asterisk it means the feature is not supported.

Creating the Virtual Machine

Ensure you have VMWare Player V5, as this will allow you to create Windows 8 VM’s. From within VMWare Player, select the option to create a new Virtual Machine, and make sure your dialog looks like the following:

Create VM

Click Next > and for the Guest Operating System select Windows 8 x64. Click Next > and give your VM a machine name. For the disk capacity, keep whats been offered (60 Gb for the disk size). Click Next > again and then click the Customize Hardware button.

For memory select, select 4 Gb if you can, this is what I have used and is what has been recommended in various posts I have read. Hopefully you will be able to allocate this much space. If you can’t select an amount that you can allow, but bare in mind that you should ideally have 4 Gb as a minimum. An example of this is shown below.

VM Memory

The from the list configuration options, select Processors. Select the number of cores you want to allocate, I have selected 2 and then ensure that the option Virtualize Intel VT-x/EPT or AMD-V.RVI is selected. The screen shot below shows my settings.

Processor SettingsClick Finish to save your new VM. Don’t start your VM yet!!!

Editing the VMX File

Before we carry on and start our VM, we need to edit the vmx file that has just been created. Navigate to where you have saved your VM files and look for the vmx file. Mine was called Windows8VM.vmx but yours will be called whatever you have called your VM. Open the vmx file in an editor like Notepad, and add the following line:

hypervisor.cpuid.v0 = “FALSE”

The v0 is a v and a zero.

My vmx file looks as follows. The added line is circled.

vmx file

Save your vmx file. We are now ready to start the VM.

Before you start the VM

Before you start the VM, select it in VMWare Player and edit the virtual machine settings. Select the CD/DVD (IDE) settings and for the Connection, either point this to the ISO for Windows 8 or a physical drive. As I’m installing from an ISO, my setting looked as follows:

CDDVD Settings

Click on OK and then start your VM. The Windows 8 installation should then start. When your Windows 8 installation has finished, you will need to install Visual Studio 2012 and then download and install the Windows Phone 8 SDK. You can get the SDK from this link http://dev.windowsphone.com/en-us/downloadsdk.

Conclusion

The above worked for me fine. It’s a mixture of installing for VMWare workstation and a bit of bespoking for VMWare Player through trial and error, hopefully this will work for you too and get you on the road to using the Windows Phone 8 emulator for testing your apps.