In other languages

Help the wiki!

The Scratch Wiki is made by and for Scratchers. Do you want to contribute?

Learn more about joining as an editor!

See discussions in the Community Portal

Recursion

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 varables can be assigned to procedures, then proceed to apply said procedure). Yet any computation possible with Scratch is possible in Scheme due to recursion.

Warning Note: By "any computation", computational expression evaluation is intended, only. 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

when I receive [create fractal v]
wait (0.5) secs
move (10) steps
turn cw (15) degrees
move (5) steps
turn ccw (5) degrees
broadcast [create fractal v]
Using the alternative broadcasting method of recursion in Scratch 2.0.

In Scratch 2.0 has 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, shift-click the definition: Add-input-to-block.png

Add input to custom block.png

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 (last v) of [Factorial-stack v])) to [Factorial-stack v]
end

when gf clicked
delete (all v) of [Factorial-stack v]
factorial (10)
say (item (last v) of [Factorial-stack v])


The stack after evaluating 10 factorial. Notice how each item is the factorial of its index minus 1.

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 (last v) 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.

Warning Tip: With a fictional (pop [list v]) block, one would be able to further optimize the above script by simply multiplying the popped value of Factorial-stack with n.

Recursion in Scratch 1.4

Archive.png This article or section documents a feature not included in the current version of Scratch (2.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 is the last block in the script. It wouldn't 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
clear
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:

BYOB tree fractal.png

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, s/he hires 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 his or her 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's 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

Main article: Making Scratch Close
Warning Warning: Like what it says on the tin, projects should not be shared that at least uses this block in a part of the project, as it violates the Terms of Use. It is best to save work before using this block.

Scratch can be crashed or frozen with this script, as it calls itself forever. It is best run without screen refresh.

define crash
crash

See Also

  • This page was last modified on 25 September 2017, at 12:38.