Recursion

Recursion is a form of looping, where a function calls itself, usually until a condition is met. Although recursion can be somewhat difficult to understand at first, it can result in much cleaner code. In the example below, a factorial function has two sections: the base step, and the recursive step. Keep in mind that if you do not have a base step, and only a recursive step, your function will run endlessly, causing stack overflow.

The base step simply returns a value of one when n is one or zero. Since we know that the factorial of 1 equals 1, we know that the factorial of two equals two times the factorial of one. In code, factorial(2) == 2*factorial(1) = 2*1 = 2.

It follows that the factorial of three is three times the factorial of two. In code, factorial(3) == 3*factorial(2) = 3*2*factorial(1) = 3*2*1 = 6.

Generalizing, the factorial of n is n times the factorial of n+1. In code, factorial(n) = n*factorial(n-1).

function factorial(n)
	if n <= 1 then -- base case
		return 1
	else
		return n * factorial(n-1) -- recursive step
	end
end

print(factorial(5))