Intermediate scripting tutorial: recursion

Resources Community Tutorials
,
#1

What is recursion?

According to wikipedia:

“Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself.” Recursion - Wikipedia)

In programming terms, a recursive function uses itself to calculate the result. A good example function, as illustrated on the wikipedia page, is calculating a factorial.

Factorial of n

A factorial of n is essentially every number multiplied up to n. So if n is 5, the factorial is 1 * 2 * 3 * 4 * 5 = 120.

We can make this a recursive function, quite easily: the factorial of 5 is just the factorial of 4 multiplied by 5. Factorial of 4 is just the factorial of 3 multiplied by 4. And so on.

((((1) * 2)) * 3)) * 4) * 5

So essentially factorial (n) = n * factorial (n - 1).

Here, however, we run into one of the caveats of recursion. Recursive functions can result in infinite loops, which can crash your program. In our case, this program would keep running indefinitely. We need to stop recursing when n reaches 0, or it will keep going indefinitely multiplying by negative numbers. So when we reach 0 we’ll just return 1. This is what’s called the “Base case”

function factorial(n : number)
	if n > 0 then
		return n * factorial(n - 1) -- Recursive case.
	else
		return 1 -- Base case. If n == 0, we return 1. 
	end
end

print(factorial(5)) -- 120

Fibonacci sequence

This one is very similar to factorial, so it'll be a good exercise for you. In a fibonacci sequence every number is the sum of the 2 numbers that came before it. Starting at 1, we then get 1, 1, 2, 3, 5, 8, 13 etc.

Your job is to write a recursive function that calculates the value at a specific position.
Note: our base case is 1. Keep that in mind when deciding what n should be smaller than in order to recurse.

function fibonacci(n)
end

print(fibonacci(6)) -- 8

The answer:

Summary 
function fibonacci(n)
	if n > 2 then
		return fibonacci(n-1) + fibonacci(n-2)
	else
		return 1
	end
end

print(fibonacci(6)) -- 8

Reversing a string

Using recursion, we can reverse a string. We can do this by keeping track of 2 strings: the initial string, from which we will grab 1 character every iteration, and the result (to which we will add that grabbed character). Our base case will thus be when the initial string is out of characters, so it's equal to "".

Here’s a step by step guide, you should try write the code yourself before checking the answer. I’ll start you out with the function definition.

  1. Grab the last character of the input string.
  2. If that character is “”, return result (or “” if result doesn’t exist, in case someone inputs “” as string)
  3. If that character is anything other than “”, append it to the end of result (or if result is nil, set it to that character). Return the function using the parameters string (but without the last character) and the result.
function reverseString(str : string, res : string?)

end

print(reverseString('hello!')) -- elloh!
print(reverseString('')) --

Answer:

Summary 
-- Longified
function reverseString(str: string, res: string?)
	-- Get the last character of the string
	local last_char = str:sub(-1, -1)

	-- If the string isn't empty, continue reversing
	if last_char ~= "" then
		-- Append the last character to the result and call the function recursively
		res = (res or "") .. last_char
		return reverseString(str:sub(1, -2), res) -- Remove the last character from the input string
	else
		-- If the string is empty, return the result
		return res or ""
	end
end

-- Shortified
function reverseString(str : string, res : string?)
	local last_char = str:sub(-1,-1)
	return last_char~="" and reverseString(str:sub(1,-2),res and res .. last_char or last_char) or res and res or ""
end

print(reverseString('hello!')) -- elloh!
print(reverseString('')) --

Palindromes

Palindromes are strings that, when reversed, are the same word.
  • radar
  • racecar
  • level
  • civic

To check if str is a palindrome, we evaluate the first and last character of the string. Are they the same? Then remove them from the string and check again with the new string. Are they not the same? Return false. Are they equal to our base case ('')? Return true.

  1. Check if the first and last characters are the same.
  2. Remove them and check the remaining substring.
  3. If the string is empty or has one character, it’s a palindrome (base case).
  4. If the first and last characters differ, it’s not a palindrome.
function isPalindrome(str : string)
	
end

print(isPalindrome('hello!')) -- false
print(isPalindrome('racecar')) -- true

Answer:

Summary 
function isPalindrome(str : string)
	local first_char = str:lower():sub(1,1)
	local last_char = str:lower():sub(-1,-1)
	
	if first_char == ''  then
		return true
	end
	if first_char == last_char then
		
		return isPalindrome(str:sub(2,-2))
	else
		return false
	end
end

print(isPalindrome('hello!')) -- false
print(isPalindrome('racecar')) -- true
1 Like