Applications of Recursion¶
We will now provide examples of a few ways in which recursion can be applied.
Factorial¶
In the cell below, we use recursion to write a function that calculates the factorial of a positive integer.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
We will now test our factorial() function by calling it on the first 10 positive integers.
for i in range(1, 11):
print(factorial(i))
1
2
6
24
120
720
5040
40320
362880
3628800
Sum Elements¶
Suppose that you are provided with several integers, but that the integers are stored in a collection of nested lists. We will write a recursive function named sum_nested() to calculate the sum of the elements in such a structure.
def sum_nested(x):
total = 0
for item in x:
if type(item) == list:
total += sum_nested(item)
else:
total += item
return total
We will now test the function on several examples.
print(sum_nested([1, 2, 3]))
print(sum_nested([1, [2], 3]))
print(sum_nested([1, [2], [1, 2, 3]]))
print(sum_nested([1, [2, [5, 6, [4, 9]]], [1, 2, 3]]))
6
6
9
33
Palindrome Checker¶
The function below accepts a string as an argument, and then checks to see if that string is a palindrome. It accomplishes that using recursion. At each step, the function checks to see if the first and last character are equal. If so, then it calls itself on the substring that omits those two characters. The recursion ends when we arrive at a string with a lenth of 1 or less.
def is_palindrome(text):
if len(text) <= 1:
return True
if text[0] != text[-1]:
return False
return is_palindrome(text[1:-1])
We will now test our function on several examples.
print(is_palindrome('abcba'))
print(is_palindrome('abgfcfgba'))
print(is_palindrome('abfgcfgba'))
print(is_palindrome('aaa'))
print(is_palindrome('aa'))
print(is_palindrome('a'))
True
True
False
True
True
True