For more information, see Recursion on Wikipedia.
Recursion occurs when an expression (in Scratch, a script) includes a call to itself. Recursion is a very versatile programming technique; it can provide simple looping mechanisms, like the Repeat or Forever blocks, and it can also generate intricate fractal graphics (shapes that include smaller versions of themselves). Recursion is a basic computational building block. Many structures such as repeat, while, for, etc. can be simply constructed with recursion. In fact, some functional languages like Scheme and Lisp do not provide these control structures; they provide just procedures and calls (functional programming; in Scratch; programming with just "reporters" and "booleans." This is possible because everything is like Snap! in the way that variables can be assigned to procedures, then proceed to apply said procedure). Yet any computation possible with Scratch is possible in Scheme due to recursion.
 Note: | By "any computation", computational expression evaluation is intended. Recursion does not help with hardware problems like drawing graphics, it only enables all computational operations, such as concatenation, addition, etc. to be performed. |
Recursion in Scratch 2.0/3.0
when I receive [draw v] wait (0.5) secs move (10) steps turn cw (15) degrees move (5) steps turn ccw (5) degrees broadcast (draw v)
method of recursion
Scratch 2.0 added the ability to create custom stack blocks. These can be recursive since they can have inputs. This allows more advanced recursion than Scratch 1.4, allowing things like creating fractals and finding the factorial of a number more easily. The lack of custom reporters can be overcome by using global variables to store temporary data. To add an input to a block, first right-click the definition:
Clicking the "edit" option here will open a menu with buttons to add inputs:
To store values during recursive calculations, use stacks. This script, designed to calculate the factorial of a number, illustrates the principle:
- A stack is maintained, containing the current calculations
- The last item of the stack (which can be obtained by popping it off) is the last calculation's value
define factorial (n) if < (n) = [0] > then add [1] to [factorial-stack v] else factorial ( (n) - (1) ) add ( (n) * (item (length of [factorial-stack v]::list) of [factorial-stack v])) to [factorial-stack v] end when gf clicked delete all of [factorial-stack v] factorial (10) say (item (length of [factorial-stack v]::list) of [factorial-stack v])
This can be optimized to delete previous calculations:
define factorial (n) if < (n) = [0] > then add [1] to [factorial-stack v] else factorial ( (n) - (1) ) add ((n) * (item (length of [factorial-stack v]::list) of [factorial-stack v])) to [factorial-stack v] delete ((length of [factorial-stack v]) - (1)) of [factorial-stack v] end
Thus, the list will only have the result of the calculation stored in it. This script requires only one variable:
define factorial (n)
if <(n) > [0]> then
factorial ((n) - [1])
set [factorial v] to ((n) * (factorial))
else
set [factorial v] to [0]
end
Recursion in Scratch 1.4
|
This article or section documents something not included in the current version of Scratch (3.0). It is only useful from a historical perspective. |
Recursion is generally implemented in programming languages with a stack of expressions to evaluate. Scratch, however, does not implement recursion with the stack mechanism.
Scratch 1.4 provides a limited type of recursive call, namely tail recursive calls, in which the recursive call is the last thing done in the script. This is accomplished in Scratch by using the broadcast () block, programming the Broadcast to call on itself as shown on the right.
Note that the broadcast () blockis the last block in the script. It would not work to broadcast the message that starts this script partway through the script, because when Scratch gets a message that triggers an already-running script, it "forgets" where it was (rather than stacking it) and begins it from the beginning again. To make a script continue a process after calling a tail recursive call in Scratch, another script must be implemented which is launched (separate thread) by the original script:
when I receive [tail-call v] say [Hi!] broadcast [continuation v] // continuation call broadcast [tail-call v] // (Tail) Recursive call say [Bye!] // never evaluated when I receive [continuation v] move (10) steps
One might assume using an inline call (broadcast () and wait) would preserve the recursive call's origin. However, this is not true in Scratch.
Iteration (doing something repeatedly) can also be simply done, without recursion, by using the forever block.
Emulating recursion in Scratch 1.4
Using a list, recursion can be emulated with the stack mechanism.
With the following script, a tree of an arbitrary size and depth can be drawn by using three variables: depth, tree_size and IP; and a list called stack.
when gf clicked
pen up
erase all
go to x: (0) y: (-154)
point in direction (0 v)
set pen color to [#5cbf12] // color for rendering tree
delete (all v) of [stack v]
set [depth v] to (6) // Here goes tree depth
set [tree_size v] to (60) // Here goes tree size
add (tree_size) to [stack v]
add [-1] to [stack v]
set [IP v] to (0)
repeat until <(IP) = (-1)>
if <not <(depth) = (0)>> then // Recursive stuff
if <(IP) = (0)> then
move (tree_size) steps
turn left (15) degrees
add (tree_size) to [stack v]
add [1] to [stack v]
set [tree_size v] to ((tree_size) * (0.75))
set [depth v] to ((depth) - (1))
else
if <(IP) = (1)> then
turn right (35) degrees
add (tree_size) to [stack v] // Push size and return address
add [2] to [stack v]
set [tree_size v] to ((tree_size) * (0.6))
set [depth v] to ((depth) - (1))
set [IP v] to (0) // Go to the code above
else
if <(IP) = (2)> then
turn left (20) degrees
move ((-1) * (tree_size)) steps
end
end
end
if <<(depth) = (0)> or <(IP) = (2)>> then // Return to caller
set [IP v] to (item (last v) of [stack v]) // Restore return address
delete (last v) of [stack v]
change [depth v] by (1)
set [tree_size v] to (item (last v) of [stack v])
delete (last v) of [stack v]
end
end
Recursion in Snap!
Snap! is a Scratch modification in which true embedded (non-tail) recursion is possible, because of procedures.
Here is an example of a fractal (self-similar) picture that cannot easily be drawn in Scratch 1.4:
That picture consists of a tree trunk (the vertical segment at the bottom), a smaller tree tilted to the left, and another smaller tree tilted to the right. Here is the definition of the Tree block in Snap! that generates the picture:
define Tree (depth) deep, size (size of tree) if <(depth) > (0)> then move (size of tree) steps turn left (15) degrees tree ((depth) - (1)) deep, size ((size of tree) * (0.75)) turn right (35) degrees tree ((depth) - (1)) deep, size ((size of tree) * (0.6)) turn left (20) degrees move ((-1) * (size of tree)) steps end
Base Case
Notice that there are two recursive calls to the Tree block within the script that defines it. One way to understand a recursive process is what's called the "little people model": inside the computer are a large number of little people. Each person knows how to do one block, but more than one person knows about each block. When a little person is running a script, they hire other little people to carry out the blocks within the script. For the Tree script, this means that a Tree specialist will hire two more Tree specialists, and each of them will hire two more, and so on.
Why does not this hiring of little people go on forever? A recursive script must have a base case that it can handle without any recursive calls. In the case of the Tree script, the base case is depth=0, which means if the tree has size 0 (i.e. does not exist), it is not drawn.
This works only because the two recursive calls provide a smaller value for depth. There is an iteration involved: every time the call is stacked, the "depth" value is decremented. Remember, each little person has their own depth variable; the recursive call does not change the caller's value of depth. This is called lexical scoping. Scope is the access of variables by their name. For example, though the evaluator at any given stage will have many "depth" variables defined in its environment, each stack only accesses its own "depth". Scoping is a common problem when debugging. Thus, many graphical debuggers provide the local declarations of each variable in each stacked level. Scoping creates many problems when code is not written clearly. For example, if a Snap! block has a script variable called "foo" and, the project has another called "foo", accidentally placing a global "foo" instead of a local "foo" will give an unexpected result, and is obviously extremely tough to debug later.
It is also important that this script leaves the sprite at the same position, and pointing in the same direction, as at the beginning of the script. If drawing the left branch of the tree left the sprite somewhere else, the script could not go on to draw the right branch in the correct place.
Crashing Scratch Using Recursion
- Main article: Making Scratch Crash
 Warning: | Projects that use this should not be shared to the Scratch Website, as they violate the Terms of Use. It is best to save work before using this block. |
Scratch can be crashed or frozen with this script using recursion, as it calls itself forever.
define crash//run without screen refresh crash
