Follow the i, and you shall find the meaning of life.
From previous topics, we know that the value of the parameter in a recursive function changes as it approches the stopping condition. Additionally, we know that the value of "i" or the variable of a "for" loop changes. Can you see some similarites here.
Lets try going over a list with having the changing values of i in mind.
def printList(i):
if i == len(names):
print("completed")
else:
print(i)
printList(i+1)
printList(0)If you don’t put a return value it will by default return None, as for the stopping condition in this case.
Using a for loop.
for i in range(len(names)):
print(i)Mapping the changing values to changing indexes in a list
In a loop, a variable i is changed with every iteration. Typically, this variable is an index, which applies to both while and for loops. We can use these changing indexes to map to indexes of a list and print the corresponding values.
Print a certain index in a list
# i : index in the list names
print(names[i])Using a while loop
i = 0
while i < len(names):
print(names[i])
i += 1
Using a for loop
for i in range(len(names)):
print(names[i])Using recursion
def printList(i):
if i == len(names):
print("completed")
else:
print(names[i])
printList(i+1)
printList(0)
In all the solutions above we are leveraging the changing values of i to print the changing values over a list. This can be done.
Passing a condition up Some similar examples. To drive it home
Similar to returning a sum at a particular value of n up the recursion tree, if the condition isfound to be true or false, that is passed up across the recursion tree.
This is an example of using recursion to determine if a number exists in an array by changing indexes. If a value is found at any stage or index, we no longer call the function recursively. Instead, we pass the Boolean value "True" up to the recursive functions. If the length of the array is exceeded, we do the same. We can be sure that the function returns either true or false, and does not continue infinatly.
def findNumber(arr, i, target):
if i == len(arr): # base condition
return False
elif arr[i] == target: # found condition
return True
else:
return findNumber(arr, target, i+1)
arr = [1, 2, 3, 4, 5]
target = 3
findNumber(arr, target, 0)Here is an example of how you can turn the code into a function in Python:
def findNumber(arr, target):
for num in arr:
if num == target:
return "The number exists in the array."
return "The number does not exist in the array."
arr = [1, 2, 3, 4, 5]
target = 3
findNumber(arr, target)
Fn(index, target)
Disclaimar: The code visualization software didn't allow passing arr as an argument. So, the array was used as a global variable instead.
arr = [1, 2, 3, 4, 5]
fn(0,5)fn(0,3)The quicker the number is found the shorter the recursive tree, target equal to 3
Not found, know by arr if i == len(arr): we are outside the bounds of the array.
fn(0,6)
some other operations with similarites.Each function called recursively runs the same code repeatedly, with changing values.
Some other examples of using recursion
- Computing factorials involves changing the value of n as mapped in the equation n! = n x (n-1) x (n-2) x ... x 2 x 1. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120.
- Traversing a binary tree requires printing the entire tree by passing the node through the parameters. As the parameters(nodes) change with each function, different values of the tree are printed. Recursive solutions are often more elegant and easier to understand, especially when there are more than two recursive calls in one function. As Leigh Caldwell wrote on Stack Overflow, "Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!”
- Fibonacci sequence is generated by adding two previous numbers together. The values of n change,n this case, the sequence is generated using two recursive functions. The value of n is changed with each recursive call to n-1 and n-2. And adding these numbers together.Since we are having the same calls made twice this solution has the makings of dynamic programming. Which is a beast of its own and will disccus it in detail in its own roadmap. So for now just enjoy the solution!
#recursive
factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
#iterative
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
factorial(5)
#recursive
inorder(node):
if node is not None:
inorder(node.left)
print(node.value)
inorder(node.right)# iterative
def inorderTraversal(root):
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
print(root.val)
root = root.right
# recursive
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
fibonacci(10)
def fibonacci(n):
if n <= 1:
return n
else:
prev1, prev2 = 0, 1
for i in range(2, n+1):
current = prev1 + prev2
prev1 = prev2
prev2 = current
return prev2
fibonacci(10)