Hey fellow Developers!
This is a simple, fun and updated tutorial on Recursion.
To the ones who are new and also to the ones that are already experience. Recursion can sometimes be difficult for a lot of developers.
At the end of this tutorial you will be able to -
- Define what recursion is.
- Where it can be used.
- Difference between Direct and Indirect Recursion
- Common errors while using recursion.
This Tutorial also consists of code examples with explanation and practice problems.
What is Recursion?
Recursion is the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Recursion can also be used in place of while loops!
Look at this piece of Code and try to figure out what exactly happens because of it before moving ahead in the tutorial
local a = 0
local function pattern(a)
if a == 10 then
print(a)
return
end
print(a)
pattern(a + 1)
end
pattern(a)
Did you have a look at the program above? Did you try to figure out what it does?
Here is the Output:
22:09:58.571 0 - Server - Script:8
22:09:58.572 1 - Server - Script:8
22:09:58.573 2 - Server - Script:8
22:09:58.573 3 - Server - Script:8
22:09:58.573 4 - Server - Script:8
22:09:58.574 5 - Server - Script:8
22:09:58.574 6 - Server - Script:8
22:09:58.574 7 - Server - Script:8
22:09:58.575 8 - Server - Script:8
22:09:58.575 9 - Server - Script:8
22:09:58.575 10 - Server - Script:5
What the program does, is that it prints numbers from 0 to 10. Initially we took a variable named “a” and assigned it a value that is 0. Then we moved on to create a function pattern() in which we passed an argument that is the variable “a”. We checked if the value of “a” is equal to 10. If yes, then print the value of “a” and stop the function by simply writing “return”. If a was not equal to 0 then it would have printed the value.
The segment of code where we check if a is equal to 10 is also known as the Base Case
Now, look closely at this particular line of code that we wrote inside the function.
pattern(a + 1)
What do you think it does?
Yes! You guessed right! It calls the function we created earlier and sends a + 1 as argument. If a was 0 and we called the function as “pattern(a + 1)” it sends the value integer value "1 " to the function. This is how the cycle repeats and 10 numbers are printed in the specific order.
Lets Look At Another Example
Look at this piece of Code and try to figure out what exactly happens because of it before moving ahead in the tutorial
local a = "Peter"
local b = 0
local function pattern(a,b)
if b == 10 then
print(a)
return
end
print(a)
pattern(a,b + 1)
end
pattern(a,b)
Did you have a look at the program above? Did you try to figure out what it does?
Here is the Output:
22:18:30.849 â–Ľ Peter (x10) - Server - Script:9
22:18:30.849 Peter
22:18:30.851 Peter
22:18:30.851 Peter
22:18:30.851 Peter
22:18:30.852 Peter
22:18:30.852 Peter
22:18:30.852 Peter
22:18:30.852 Peter
22:18:30.853 Peter
22:18:30.853 Peter - Server - Script:6
Here we declare two variables. A string named “a” and an integer named “b”. Variable a contains the string “Peter” and variable b initially contains 0 as its value. We create a similar function pattern() and pass both variables in it. We check if b is equal to 10. If yes, then print the string and return. If b is not equal to 10 then we print the string and we pass in two arguments. The string variable “a” and the integer variable “b” but we add 1 to it.
Hope you understood how the above program works.
What is the difference between Direct Recursion and Indirect Recursion?
A function pattern() is called direct recursive if it calls the same function pattern(). A function pattern() is called indirect recursive if it calls another function say pattern2().
Example of Direct Recursion -
local a = 0
local function pattern(a)
if a == 10 then
print(a)
return
end
print(a)
pattern(a + 1)
end
pattern(a)
Example of Indirect Recursion
local a = 0
function pattern(a)
print(a)
pattern2(a)
end
function pattern2(a)
if a == 10 then
return
end
pattern(a + 1)
end
pattern(a)
Extra Examples. Special Thanks to @TheCarbyneUniverse
Say that you have nested table where you can’t tell how many levels it’s nested:
local t = {
Fruits = {
'Apples',
'Bannas',
'Oranges'
},
Type = 'Food',
Quantity = 12,
Nutrition = {
Apples = {
GrannySmith = 12,
Macintosh = 7
},
Bananas = 9472,
Oranges = 141
}
}
The easiest way to print every value is via recursion:
local function deepSearch(tab)
for i, v in pairs(tab) do
if type(v) == 'table' then --repeat the process until it's not a table
deepSearch(v)
else
print(v)
end
end
end
deepSearch(t)
--it prints everything
This can be especially useful in serialization where you’re trying to break down un-savable datatypes into basic, savable data. Like for CFrame , you need to first break it down into individual Vector3 s, then break those vectors down into individual numbers. This means that the serialization function needs to run twice.
Common Errors
Here are some of the most common errors faced using recursion.
StackOverFlow Error - It occurs when the recursive attempt is never ending and is endlessly being run. This can also lead to the crashing of Roblox Studio or in other words where base case is not provided.
Syntax Error While Passing Arguments to the Function - This may happen if you do not pass the correct variables, you don’t pass any variables or you pass too many variables that are not required by the function.
Practice Recursion
Here are some problems you shall try to solve yourself to practice recursion!
-
Print numbers from 1 to N (An Integer Variable) without using a loop.
-
Print your name 20 times using recursion.
-
Print elements of a table using recursion.
-
Using Indirect recursion print numbers from 10 to 0.
-
Using Recursion print the first 10 powers of the number 2.
Hope you enjoyed the tutorial on Recursion 
Feel Free to reply down below with doubts, more code examples, answers to the practice questions and feedback!
Happy Coding!