A recursive function that is called with an input that requires too many iterations will cause the call stack to get too large, resulting in a stack overflow error. In these cases, it is more appropriate to use an iterative solution. A recursive solution is only suited for a problem that does not exceed a certain number of recursive calls.
For example, myfunction() below throws a stack overflow error when an input of 1000 is used.
def myfunction(n):if n == 0:return nelse:return myfunction(n-1)myfunction(1000) #results in stack overflow error
A Fibonacci sequence is a mathematical series of numbers such that each number is the sum of the two preceding numbers, starting from 0 and 1.
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
A call stack with execution contexts can be constructed using a while loop, a list to represent the call stack and a dictionary to represent the execution contexts. This is useful to mimic the role of a call stack inside a recursive function.
In Python, a binary search tree is a recursive data structure that makes sorted lists easier to search. Binary search trees:
5/ \/ \3 8/ \ / \2 4 7 9
A nested list can be traversed and flattened using a recursive function. The base case evaluates an element in the list. If it is not another list, the single element is appended to a flat list. The recursive step calls the recursive function with the nested list element as input.
def flatten(mylist):flatlist = []for element in mylist:if type(element) == list:flatlist += flatten(element)else:flatlist += elementreturn flatlistprint(flatten(['a', ['b', ['c', ['d']], 'e'], 'f']))# returns ['a', 'b', 'c', 'd', 'e', 'f']
Computing the value of a Fibonacci number can be implemented using recursion. Given an input of index N, the recursive function has two base cases – when the index is zero or 1. The recursive function returns the sum of the index minus 1 and the index minus 2.
The Big-O runtime of the Fibonacci function is O(2^N).
def fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)
One can model recursion as a call stack with execution contexts using a while loop and a Python list. When the base case is reached, print out the call stack list in a LIFO (last in first out) manner until the call stack is empty.
Using another while loop, iterate through the call stack list. Pop the last item off the list and add it to a variable to store the accumulative result.
Print the result.
def countdown(value):call_stack = []while value > 0 :call_stack.append({"input":value})print("Call Stack:",call_stack)value -= 1print("Base Case Reached")while len(call_stack) != 0:print("Popping {} from call stack".format(call_stack.pop()))print("Call Stack:",call_stack)countdown(4)'''Call Stack: [{'input': 4}]Call Stack: [{'input': 4}, {'input': 3}]Call Stack: [{'input': 4}, {'input': 3}, {'input': 2}]Call Stack: [{'input': 4}, {'input': 3}, {'input': 2}, {'input': 1}]Base Case ReachedPopping {'input': 1} from call stackCall Stack: [{'input': 4}, {'input': 3}, {'input': 2}]Popping {'input': 2} from call stackCall Stack: [{'input': 4}, {'input': 3}]Popping {'input': 3} from call stackCall Stack: [{'input': 4}]Popping {'input': 4} from call stackCall Stack: []'''
In Python, a recursive function accepts an argument and includes a condition to check whether it matches the base case. A recursive function has:
def countdown(value):if value <= 0: #base caseprint("done")else:print(value)countdown(value-1) #recursive case
To build a binary search tree as a recursive algorithm do the following:
BASE CASE:
If the list is empty, return "No Child" to show that there is no node.
RECURSIVE STEP:
1. Find the middle index of the list.
2. Create a tree node with the value of the middle index.
3. Assign the tree node's left child to a recursive call with the left half of list as input.
4. Assign the tree node's right child to a recursive call with the right half of list as input.
5. Return the tree node.
def build_bst(my_list):if len(my_list) == 0:return "No Child"middle_index = len(my_list) // 2middle_value = my_list[middle_index]print("Middle index: {0}".format(middle_index))print("Middle value: {0}".format(middle_value))tree_node = {"data": middle_value}tree_node["left_child"] = build_bst(my_list[ : middle_index])tree_node["right_child"] = build_bst(my_list[middle_index + 1 : ])return tree_nodesorted_list = [12, 13, 14, 15, 16]binary_search_tree = build_bst(sorted_list)print(binary_search_tree)
A binary search tree is a data structure that builds a sorted input list into two subtrees. The left child of the subtree contains a value that is less than the root of the tree. The right child of the subtree contains a value that is greater than the root of the tree.
A recursive function can be written to determine the depth of this tree.
def depth(tree):if not tree:return 0left_depth = depth(tree["left_child"])right_depth = depth(tree["right_child"])return max(left_depth, right_depth) + 1
Summing the digits of a number can be done recursively. For example:
552 = 5 + 5 + 2 = 12def sum_digits(n):if n <= 9:return nlast_digit = n % 10return sum_digits(n // 10) + last_digitsum_digits(552) #returns 12
A palindrome is a word that can be read the same both ways - forward and backward. For example, abba is a palindrome and abc is not.
The solution to determine if a word is a palindrome can be implemented as a recursive function.
def is_palindrome(str):if len(str) < 2:return Trueif str[0] != str[-1]:return Falsereturn is_palindrome(str[1:-1])
A Fibonacci sequence is made up adding two previous numbers beginning with 0 and 1. For example:
0, 1, 1, 2, 3, 5, 8, 13, ...A function to compute the value of an index in the Fibonacci sequence, fibonacci(index) can be written as an iterative function.
def fibonacci(n):if n < 0:raise ValueError("Input 0 or greater only!")fiblist = [0, 1]for i in range(2,n+1):fiblist.append(fiblist[i-1] + fiblist[i-2])return fiblist[n]
The multiplication of two numbers can be solved recursively as follows:
Base case: Check for any number that is equal to zero.
Recursive step: Return the first number plus a recursive call of the first number and the second number minus one.def multiplication(num1, num2):if num1 == 0 or num2 == 0:return 0return num1 + multiplication(num1, num2 - 1)
To compute the factorial of a number, multiply all the numbers sequentially from 1 to the number.
An example of an iterative function to compute a factorial is given below.
def factorial(n):answer = 1while n != 0:answer *= nn -= 1return answer
We can use recursion to find the element with the minimum value in a list, as shown in the code below.
def find_min(my_list):if len(my_list) == 0:return Noneif len(my_list) == 1:return my_list[0]#compare the first 2 elementstemp = my_list[0] if my_list[0] < my_list[1] else my_list[1]my_list[1] = tempreturn find_min(my_list[1:])print(find_min([]) == None)print(find_min([42, 17, 2, -1, 67]) == -1)