What is recursion? And what are recursive algorithms.

Recursion is mostly identified as a function calling itself. A lot of recusive functions haves a Base Case to get out of it or else it becomes an infinite loop. Recursion is essencially a different type of loop.

They work similarly to how you would traverse an array, but with enhanced capability. For example if you had a Model full of parts, you could loop through that like so:

for i,v in pairs(model:GetChildren()) do
	print(i,v)
end

Now making it more complicated what if a child of that model had children of it's own? How do do you also get those?

That's where recursion can come in handy, here is an example:

function recurse(obj)
	for i,v in pairs(obj:GetChildren()) do
		print(i,v)
		if #v:GetChildren() > 0 then
			recurse(v)
		end
	end
end

for i,v in pairs(model:GetChildren()) do
	print(i,v)
	if #v:GetChildren() > 0 then
		recurse(v)
	end
end

Explaining how this works... The loop starts iterating through the model's children, and it will do so until it hits a child who has children of it's own. From there it will call the recurse() function and start iterating through the child's children. And the same process happens there. If one of the child's children has children it will call the function again, going another step deeper. This is just 1 example. (It does not require a Base Case since it's not really getting or setting anything, it's just looking at the contents).

Another example could be use to find and get a particular instance called "GetMe":

function recurse(obj)
	for i,v in pairs(obj:GetChildren()) do
		if v.Name == "GetMe" then
			return v
		end
		if #v:GetChildren() > 0 then
			return recurse(v)
		end
	end
	return false
end

return recurse(model)

Let's say that the recurse() function has now been called 3 times, that means it is 3 layers deep in children of the Model. So how the return works is that the 3rd recurse() will return to the 2nd, and the 2nd will return to the first which would be the return recurse(model) statement.

For your factorial problem, you would use that principal:

function multiply(n)
	if n >= 1 then
		return n*multiply(n-1)
	end
	return 1
end

print(multiply(5))
-- Output
120

Basically each time it iterates through multiply(), it will take 1 off of n until you get to the base case which is just return 1, that's where it ends and start's is returns back the way it came. Return 1, return 2x1, return 3x2, return 4x6, return 5x24.