Preface
Unfortunately, this isn’t a guide on making anything specific in gimkit but how to use Recursion effectively. Recursion isn’t a gimkit-specific concept, it’s mainly used in math and other coding languages. This guide will look at what recursion is and why we would need to use it.
RECAP Portion
Note: This section is entirely optional.
In our last episode of cooking with wired, we made a pseudo-waypoint mechanism. But this time, we’re not going to be specifically making anything, but uh learning a cool technique. Anyways, welcome to episode 2 (or 1.5) of cooking with wired!!!
Okay anyways…
What is Recursion?
Let’s let Wikipedia define this one. Recursion is:
“The process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself”
Mathematical functions or sequences that use previous terms as inputs are recursive functions. An example of a famous sequence that can be defined using recursion is the Fibonacci sequence. If you don’t know the Fibonacci sequence, the first two terms are 1 and 1. Every term after is the sum of the previous two terms. Here are a few terms of the Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
See how it works?
Using math notation, you’d write this as:
An = An - 1 + An - 2
This readout is “Every nth term of this sequence is the sum of the two previous terms.” So the sequence is defined by the previous few terms.
Another (simpler) example of a recursive sequence is this:
An = An - 1 + 1
This is just a sequence that adds one to itself forever.
Hold up, it’s a good time to mention this. Most recursive sequences need a base case (or multiple). Using the above sequence, it’s difficult to determine even the second term in the sequence without defining a base case. If the first term is 29, then the second would be 30. But if the first term is 0, then the second term is 1. This is why you would need to specify something like “A1 = 0”. This means that the first term is 1, so there’s no ambiguity.
You can write recursive sequences in function notation too. You’d write the above scenario as “F(n) = F(n - 1) + 1” and F(1) = 0, where F is your function, n is your input, and F(1) = 0 is your base case.
Simple Applications of Recursion
How do you make a timer in gimkit? You increase the count of a counter by 1 every second (or some unit of time). So basically, the count of the counter is 1 more than its previous count every second. Hey, that sounds like our sequence before!
Consider the following - You need to increase a property by some amount, maybe its value is 347 now and you want it to be 355 next. Using a counter would be annoying since it’s very annoying to make it count 8 times in a moment. What most gimkit creative users do instead is go make some blocks and place these down:
This looks like something illegal that gimkit will never run. But it actually works. This fits into our definition of recursion because it is self-referential. Cool, right?
Example: Generation Using Recursion
I took inspiration from a TUG I’ve seen in the past involving this. A gun (let’s say gadget) game is a game where there is a randomly generated “path” of gadgets. Here’s a simple example:
Gadget 1: Rare Wooden Wand
Gadget 2 (achieved after knocking out a player using Gadget 1): Common Evil Eye
Gadget 3: Legendary Quantum Portal
Gadget 4: Legendary Slingshot
Gadget 5: Uncommon P.M.L
This topic is NOT about random item generation, so we won’t discuss how you would choose which gadget to get.
So, to have every player have the same gadget path, one might think of using a global property to store the name of each gadget. For example, you could call a common zapper that’s 3rd on the path “3CommonZapper”.
If your GADGET game path is 25 gadgets long, you must generate 25 gadgets in one property. You can do this by progressively appending more and more names to a long string and then finding the string using text objects. How do you generate 25 different items? Recursion! The trigger that begins the generation process will add 1 to a property every time a new gadget is generated, indicating the gadget’s position.
Example: Definition of Factorial
What is a factorial? The factor of a positive integer n is the product of all integers less than n (to 1). 3! would be 3 x 2 x 1 = 6. You normally don’t need to include the 1 as any integer multiplied by 1 is itself.
Things you need to know: 0! is 1. You just have to accept that for this guide, if you want to know why then look it up. The notation for a factorial is also an exclamation mark. In the above paragraph 3! would be read as “3 factorial”.
To simulate a factorial, you can use recursion. Why? For any integer n, n * (n - 1)! = n!. Think about this, it’ll make sense.
What is 10!? It is 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2. It is also 10 * 9!. What is 9!? It is 9 x 8!.
10! = 10 x 9!
9! = 9 x 8!
8! = 8 x 7!
7! = 7 x 6!
6! = 6 x 5!
5! = 5 x 4!
4! = 4 x 3!
3! = 3 x 2!
2! = 2 x 1!
1! = 1 x 0!
0! = 1.
If you substitute EVERYTHING back, you’ll get “10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2” again.
This means that a recursive definition of a factorial is F(n) = n x (n - 1)!, where the base case is F(0) = 1.
How could you implement this into gimkit? It’d be annoying and you’d take a lot of memory, but yes, there is a factorial function in gimkit that is possible to make.
Conclusion
If I made a mistake please tell me :D
Catalan numbers are cool. If you want to know how to use recursion in competition math, see INTERMEDIATE COUNTING AND PROBABILITY Chapter 10.
One more problem. If I can climb a flight of 10 stairs using either 1 or 2 steps at a time, how many ways can I get up? You can solve this with recursion. Tell me in the replies and I’ll give you a prize or something.
I hope I did justice to this concept as a dummy around here…