Coding challenges which compare and contrast iterative solutions with recursive solutions.

Recursion vs. Iteration - Coding Throwdown

This lesson will provide a series of algorithms and an iterative or recursive implementation. 

Anything we write iteratively, we can also write recursively, and vice versa. Often, the difference is substituting a loop for recursive calls. 

Your mission is to recreate the algorithm using the alternative strategy. If the example is recursive, write the algorithm using iteration. If the algorithm uses iteration, solve the problem using recursion.

By the end of this lesson, you'll have gained a better understanding of the different strategies to implement an algorithm, and along the way, we'll discuss the big O runtimes of each algorithm.

Each exercise will have a single checkpoint. You can implement the algorithm however you like as long as you're following the prescribed approach (iterative or recursive).

If you're feeling stuck, the hint will give a detailed breakdown of how to implement the algorithm.

We'll start with a classic recursive example, `factorial()`. This function returns the product of every number from 1 to the given input.

```py
# runtime: Linear - O(N)
def factorial(n):  
  if n < 0:    
    return ValueError("Inputs 0 or greater only") 
  if n <= 1:    
    return 1  
  return n * factorial(n - 1)

factorial(3)
# 6
factorial(4)
# 24
factorial(0)
# 1
factorial(-1)
# ValueError "Input must be 0 or greater"
``` 

This is a linear implementation, or `O(N)`, where `N` is the number given as input.

Rules of the Throwdown

Fantastic! Now we'll switch gears and show you an iterative algorithm to sum the digits of a number. 

This function, `sum_digits()`, produces the sum of all the digits in a positive number as if they were each a single number:

```py
# Linear - O(N), where "N" is the number of digits in the number
def sum_digits(n):
  if n < 0:
    ValueError("Inputs 0 or greater only!")
  result = 0
  while n is not 0:
    result += n % 10
    n = n // 10
  return result + n

sum_digits(12)
# 1 + 2
# 3
sum_digits(552)
# 5 + 5 + 2
# 12
sum_digits(123456789)
# 1 + 2 + 3 + 4...
# 45
```

Let's Give'em Sum Digits To Talk About

We'll use an iterative solution to the following problem: find the minimum value in a list.

```py
def find_min(my_list):
  min = None
  for element in my_list:
    if not min or (element < min):
      min = element
  return min

find_min([42, 17, 2, -1, 67])
# -1
find_mind([])
# None
find_min([13, 72, 19, 5, 86])
# 5
```
This solution has a linear runtime, or `O(N)`, where `N` is the number of elements in the list.

It Was Min To Be

Nice work! We'll demonstrate another classic recursive function: `fibonacci()`.

`fibonacci()` should return the `N`th Fibonacci number, where `N` is the number given as input. The first two numbers of a Fibonacci Sequence start with `0` and `1`. Every subsequent number is the sum of the previous two.

Our recursive implementation:

```py
# runtime: Exponential - O(2^N)

def fibonacci(n):
  if n < 0:
    ValueError("Input 0 or greater only!")
  if n <= 1:
    return n
  return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(3)
# 2
fibonacci(7)
# 13
fibonacci(0)
# 0
```

When Fibs Are Good

All programming languages you're likely to use will include arithmetic operators like `+`, `-`, and `*`.

Let's pretend Python left out the multiplication, `*`, operator. 

How could we implement it ourselves? Well, multiplication is repeated addition. We can use a loop!

Here's an iterative approach:

```py
def multiplication(num_1, num_2):
  result = 0
  for count in range(0, num_2):
    result += num_1
  return result

multiplication(3, 7)
# 21
multiplication(5, 5)
# 25
multiplication(0, 4)
# 0
```
This implementation isn't quite as robust as the built-in operator. It won't work with negative numbers, for example. We don't expect your implementation to handle negative numbers either!

What is the big O runtime of our implementation?

Multiplication? Schmultiplication!

Palindromes are words which read the same forward and backward. Here's an iterative function that checks whether a given string is a palindrome:

```py
def is_palindrome(my_string):
  while len(my_string) > 1:
    if my_string[0] != my_string[-1]:
      return False
    my_string = my_string[1:-1]
  return True 

palindrome("abba")
# True
palindrome("abcba")
# True
palindrome("")
# True
palindrome("abcd")
# False
```
Take a moment to think about the runtime of this solution. 

In each iteration of the loop that doesn't return `False`, we make a copy of the string with two fewer characters. 

Copying a list of `N` elements requires `N` amount of work in big O. 

This implementation is a quadratic solution: we're looping based on `N` and making a linear operation for each loop!

Here's a more efficient version:

```py
# Linear - O(N)
def is_palindrome(my_string):
  string_length = len(my_string)
  middle_index = string_length // 2
  for index in range(0, middle_index):
    opposite_character_index = string_length - index - 1
    if my_string[index] != my_string[opposite_character_index]:
      return False  
  return True
```
**Note these solutions do not account for spaces or capitalization in the input!**

Taco Cat

<a href="https://en.wikipedia.org/wiki/Binary_tree" target="_blank">Binary trees</a>, trees which have at most two children per node, are a useful data structure for organizing hierarchical data.

It's helpful to know the depth of a tree, or how many levels make up the tree.

```py
# first level
root_of_tree = {"data": 42}
# adding a child - second level
root_of_tree["left_child"] = {"data": 34}
root_of_tree["right_child"] = {"data": 56}
# adding a child to a child - third level
first_child = root_of_tree["left_child"]
first_child["left_child"] = {"data": 27}
```
Here's an iterative algorithm for counting the depth of a given tree. 

We're using Python dictionaries to represent each tree node, with the key of `"left_child"` or `"right_child"` referencing **another** tree node, or `None` if no child exists.

```py
def depth(tree):
  result = 0
  # our "queue" will store nodes at each level
  queue = [tree]
  # loop as long as there are nodes to explore
  while queue:
    # count the number of child nodes
    level_count = len(queue)
    for child_count in range(0, level_count):
      # loop through each child
      child = queue.pop(0)
	 # add its children if they exist
      if child["left_child"]:
        queue.append(child["left_child"])
      if child["right_child"]:
        queue.append(child["right_child"])
    # count the level
    result += 1
  return result

two_level_tree = {
"data": 6, 
"left_child":
  {"data": 2}
}

four_level_tree = {
"data": 54,
"right_child":
  {"data": 93,
   "left_child":
     {"data": 63,
      "left_child":
        {"data": 59}
      }
   }
}


depth(two_level_tree)
# 2
depth(four_level_tree)
# 4
```
This algorithm will visit each node in the tree once, which makes it a linear runtime, `O(N)`, where `N` is the number of nodes in the tree.