|
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
when I receive [draw v] wait (0.5) seconds 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
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
