Tutorial On Recursion

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 -

1. Define what recursion is.
2. Where it can be used.
3. Difference between Direct and Indirect Recursion
4. 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!

1. Print numbers from 1 to N (An Integer Variable) without using a loop.

2. Print your name 20 times using recursion.

3. Print elements of a table using recursion.

4. Using Indirect recursion print numbers from 10 to 0.

5. 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!

13 Likes

I think you should include this beyond just the looping aspect of recursion:

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.

6 Likes

Thank you for adding that to the tutorial!

I went for an easy to understand and a basic Recursion Tutorial!

I have added the content you provided, to the tutorial!

1 Like

Thank you for the tutorial! It was very simple to understand and helped me out a lot!

1 Like

Missing in the tutorial in my opinion:

• Recursion must have a stopping condition. This should be the first thing when thinking about using recursion, when to stop. It is important to think of all possible outcomes of a function, especially when using recursion because some edge cases might not reach a stop and will cause stack overflow.
• Anything that can be done with recursion can be done with loops, but not the other way around. The motivation to use it is to have a more elegant code and have a more simplistic solution than looping (if possible, +some languages do not support loops but theyâ€™re usually old ones and not commonly in use). Therefore, I donâ€™t think you should use recursion if the solution is not simplistic/shorter than looping.
2 Likes

Thank you for adding that to the tutorial! Though the first point is mentioned in the tutorial.