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

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 Vector3s, 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.