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 you can assign variables to functions, then proceed to apply said function). Yet any computation possible with Scratch is possible in Scheme due to recursion.

 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
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:

To store values during recursive calculations, we 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
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
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.

 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

 This article or section documents a feature 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 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, you must implement another script 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
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)
set pen color to [#5cbf12] // colour 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
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] //
set [tree_size v] to ((tree_size) * (0.75))
set [depth v] to ((depth) - (1))
else
if <(IP) = (1)> then
turn right (35) degrees
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)>
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

 Warning: Projects which crash Scratch are against the Community Guidelines. Do not add this code to your public projects.

You can crash/hang scratch with this script, as it calls itself forever.

```define crash
crash
```