The subproblems are the same as the bigger problem
Problems which require an arbitrary number of nested loops.
- i.e. you don’t know the number of loops the problem will require.
- use recursion when iterating through a graph or a tree, finding all permutations of a string, etc
solving the problem via the solution of the smaller version of the same problem
Break down a complex problem into a simpler one
Solve the simpler one, and then use that result to go up and solve the bigger problem.
Recursive tree is often useful
Solving a problem with recursion:
- Think of a base case (usually an empty list, what happens when its at 0, or len(object) == 0, etc.)
- Assume your function works on a smaller case than the bigger one.
- Knowing that you have your smaller answer solved, how do you solve the one you’re at?
# Example:
def is_in_list(num, lst):
""" Find out if the number is in the list recursively """
if len(lst) == 0:
return False
else:
return num == lst[0] or is_in_list(num, lst[1:])
