Recursive Functions Part 2

Every recursive function has the same two parts:

1. The base case says when to stop.
2. The recursive step calls the function with a smaller input.

The factorial of n is n * (n - 1) * ... * 1, so the factorial of n is n times the factorial of n - 1:

func factorial(n: int) -> int:
	if n == 1: # base case
		return 1
	return n * factorial(n - 1) # recursive step

factorial(5) calls factorial(4), which calls factorial(3), down to factorial(1), which returns 1. On the way back, each call multiplies: the result is 120.

A smaller input does not have to be a smaller number. A shorter string works too. This function reverses a string:

func reverse_text(text: String) -> String:
	if text.length() <= 1: # base case
		return text
	return reverse_text(text.substr(1)) + text[0]

text.substr(1) is the string without its first character. The function reverses that shorter string and adds the first character at the end. A string of zero or one character is already reversed, so it is the base case.

print(reverse_text("hello"))

olleh