This is the start of some more collated ideas on recursion 
It won’t be super precise.
— A diagram illustrating how the code flows when you call a function/ability inside itself. In Hopscotch, abilities can be used.
When you call the function inside itself (step 2), the ‘outer function’ stops running and then the inner function starts running on its own, from the top again (step 3).
When the inner function has been executed completely, the rest of the code in the outer function is executed (step 4).
Definitions
Recursion is when:
- When you call a function inside itself
- You refer to the function itself inside its definition
- You keep decreasing the problem size until the case becomes small enough that you can solve it directly, and each sub-problem can be approached similarly to the original problem.
Example with factorial:
Factorial can be defined as:
factorial(x) = x * factorial(x - 1) where factorial(0) = 1
Say you want to work out factorial of 3. Substitute x = 3 and you get:
factorial(3) = 3 * factorial(2)
Now in order to proceed, it seems you need to calculate factorial of 2. Substitute x = 2 and you get:
factorial(2) = 2 * factorial(1)
‘Now in order to proceed, it seems you need to calculate factorial of 1. Substitute x = 1 and you get:’
factorial(1) = 1 * factorial(0)
‘Now in order to proceed, it seems you need to calculate factorial of 0. Substitute x = 0 and you get:’
factorial(0) = 1 // from our definition
Finally 
(pausing to explain so far) This was to illustrate that each new sub-problem is solved similarly to the previous problem, with the same steps 
That is, until you reach a base case, where the problem can be solved directly.
In this example, the problem was to calculate the factorial of any number, and here the case for factorial of 0 could be solved directly. (1 also works but I chose 0 here)
Continuing, we now have the answer to factorial(0) to substitute into the step preceding it.
factorial(1) = 1 * factorial(0)
factorial(1) = 1 * 1
factorial(1) = 1
We now have the answer to factorial(1) to substitute into the step preceding it.
factorial(2) = 2 * factorial(1)
factorial(2) = 2 * 1
factorial(2) = 2
‘We now have the answer to factorial(2) to substitute into the step preceding it.’
factorial(3) = 3 * factorial(2)
factorial(3) = 3 * 2
factorial(3) = 6
And there were no steps preceding this, so this is the final result to our initial problem of factorial(3)
Local arguments, by undoing
This is a note with using this method of implementing functions in Hopscotch. Using this, when you call a function inside a function, you set a new value for the argument each time.
However, you would want the value of the argument to be local to each function call particularly for recursion.
The problem is, by the time execution returns to the outer function call, the value of the argument will be different to what it was supposed to be in the outer function.
So you need to undo it after each function call:
-
You can do this by ‘undoing’ the operation of the argument after each call, so the value remains the same for the previous call. (This is particularly important if you have a unique value for each of multiple calls.)
-
Or you can undo the operation at the end of the ability — which means it will be undone the same way for all calls. (It won’t work if you have multiple calls where the argument is set to a unique value for each)
In factorial function and combinations function topic, I used this undoing for the factorial function:
[I would like to revisit this]
When to recurse:
If you put an ability inside itself, it will keep calling itself forever.
If you want it to recurse only under a specific condition, you can use an If.
if level > 0:
// what you want to happen when it recurses
else:
// what you want to happen otherwise
If you are using recursion to solve a problem, the case or condition under which you don’t recurse is often referred to as the base case. This is where the sub-problem can be solved directly.
Example of recursion with Fibonacci numbers (no code, just manual steps):
Originally I was going to put this as the original example but I think factorial is better suited for first illustration purposes.
Let’s look at an example of the Fibonacci sequence, where each new term is the sum of the two previous terms.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...
New term = (the term in the position before it) + (the term in the two positions before it)
(Or in more precise mathematical terms:)
tn = tn-1 + tn-2 where tn is the nth Fibonacci number, and t1 = 0, t2 = 1
Say you want to work out the 5th Fibonacci number using this approach.
tn = tn-1 + tn-2
-
Substitute n = 5 into the equation and you get:
t5 = t4 + t3
Now you need to work out both t4 and t3. -
t4 is first. Substitute n = 4 and you get:
t4 = t3 + t2
Now you work out both t3 and t2. -
t3 is first. Substitute n = 3 and you get:
t3 = t2 + t1
Now you work out both both t2 and t1.
and so on… do you see that in each new call, the steps you’re taking are essentially the same as the original That is until you get to t2 and t1. This is now small enough that you know that these values are (the first number in the Fibonacci sequence is 0, and the second is 1, according to what we defined earlier.)
If you continued the example, you would get:
- t2 is first. Substitute n = 2 and you get:
t2 = 1 (this was defined)
Now we can substitute t2 = 1 in the preceding step:
t3 = t2 + t1
t3 = 1 + t1
Now we need to work out t1:
t1 = 0 (this was defined)
Now we can substitute it back in the previous step:
t3 = 1 + t1
t3 = 1 + 0
t3 = 1
Now you would be able to use this in the step that preceded this, for working out t4:
t4 = t3 + t2
t4 = 1 + t2 (you now have the value for t3)
And now you need to work out t2 again…I am emulating the steps a computer program would take, following the equation we put 
By the way these are open, free ideas. I’ve come across them a bit from what I’ve learnt a little more formally, a little bit individually, a little bit from looking at the code of Dr. Em on Hopscotch particularly I’m absolutely sure lots of people could come across this independently.
Let me know if there is anything that needs to be fixed — these are ideas I am still working through too 