This week, we learnt about recursion and different compound data types.

**Recursion**

Recursion means repeating similar version of something. In programming, a recursion function is a function that calls a smaller version of itself. It is useful for problems that can be represented as smaller version of themselves. The concept of recursion can be condensed into these statements

– Reduce a problem to a simpler version of the problem, plus some simple computations (recursive step)

– Keep reducing until a simple case is reached that can be solved directly (base case)

For example, if we want to multiply a number a by b recursively, we can make a recursive function, the pseudocode is as follows:

(Base case)

(Recursive case)

The implementation of the code is as follows:

1 2 3 4 5 |
def mul(a, b): if b == 1: return a else: return a + mul(a, b - 1) |

For example, we want to find the multiplication of 7 and 5, call the function mul(7, 5). Since b is not equals to 1, we go to the recursive step, the recursive step says that the mul(7, 5) will return 7 + mul(7, 4), but what is mul(7, 4)? We have to find it by calling another version of the same function, mul(7, 4), which in turns equals to 7 + mul(7, 3). Do this until you need to find mul(7, 1), in which case b is equals to 1, then return 7.

**Inductive reasoning**

How do we ensure that our recursion will work? There are three steps to follow.

- if b > 1, it will make a recursive call b-1
- b will keep decreasing with each recursion, until it becomes less than 1
- put a stop at recursion when b = 1

**Mathematical induction**

We can also use mathematical induction to prove if a recursion will work. For example, let’s prove the mul(a, b) recursion function.

Traditional way: mul(a, b) = a * a * a * … * a for b times

Recursive way: mul(a, b) = a + a * mul(a, b -1 )

Can we prove that the second statement is true for any value? First, we need to know how to prove using mathematical induction.

To prove a statement indexed on inters is true for all values of n:

1. Prove it is true when n is smallest value (e.g. n = 0 or n = 1)

2. Assuming function n is true, then prove that if it is true for an arbitrary value, one can show that it must be true for n + 1

Example:

Use mathematical induction to prove 0 + 1 + 2 + 3 + … + n = (n(n+1)) / 2

Proof:

- If n = 0, then LHS is 0 and RHS is (0(0+1)) / 2 = 0, so true. (Base case)
- Assuming equation is true for a value k, in recursive step we need to prove k + 1 is true in order to prove that is inductively correct

so we need to prove 0 + 1 + 2 + 3 + … + k + (k + 1) = ((k+1)(k+1+1)) / 2 is true.

so, LHS = (k(k+1)) / 2 + (k+1) = RHS. k + 1 is true. (Recursive step) - By induction, the equation is true for all values.

Example:

Back to our mul function, how do we relate mathematical induction to recursion code:

Base case: base case of Mul must be true

Recursive case: assume Mul is correct for all values, choose an arbitray value, b, then if b+1 is true, induction states it must be correct.

Proof:

- Base case: Mul (a, b) = a is true for b = 1. Mul(3, 1) = 3, so it’s true.
- Recursive step: Asumming Mul(a, b) works for all value b, then prove that it is true for an arbitray value, one can show that it must be true for b + 1. Mul(a, b + 1) by inspection turns out true, so the recursive step is true.
- By induction the equation is true for all values.

**Examples of functions that can be called recursively**

- Factorial: https://courses.edx.org/c4x/MITx/6.00.1-x/asset/lectureCode_Lec5-fact.py
- Tower of hanoi
- Fibonacci
- Palindrome:

**Difference between loop and recursion**

Loop does not call a smaller version of itself. Recursion calls a smaller version of itself.

**Loop example for multiplication and exponentiation()**

1 2 3 4 5 6 7 8 |
def iterMul(a, b): """ """ summation = 1 while b > 0: summation *= a b -= 1 return summation |

1 2 3 4 5 6 7 8 9 10 11 12 |
def iterPower(base, exp): """ base: float or int exp: int exp >= 0 Return the answer of base raised to exp. """ summation = 1 while exp > 0: summation *= base exp -= 1 return summation |

**Recursion example for multiplication and exponentiation()**

1 2 3 4 5 |
def recurMul(a, b): if b == 1: return a else: return a + recurMul(a, b-1) |

base case: b = 1

recursive step: a + a * (b-1)

1 2 3 4 5 6 7 8 9 10 11 |
def recurPower(base, exp): """ base: float or int exp: int exp >= 0 Return the answer of base raised to exp. """ if exp == 0: return 1 else: return base * recurPower(base, exp - 1) |

base case: exp = 0

recursive step: base * base ^ (exp – 1)

**Compound data types**

Compound data types are combination of simpler data types.

- Tuples
- Ordered sequence of elements, elements can be char, int, string, tuples (tuple can contain tuples), etc.
- Open and close parentheses with elements separated by commas.
- Warning: if initializing only one element in tuple (singleton), must put comma, e.g. X = (‘test’, ), an element (string) in a tuple, so as not to confuse with x = (‘test’), which is a string.
**Immutable.**- E.g.
**X = (1, ‘a’, ‘b’, (‘hi’, 2, 93), ‘house’)**

- Lists
- Similar to tuple, ordered sequence of elements. E.g.
- Open and close square brackets with elements separated by commas.
- Initializing singleton don’t have to put comma behind.
- Important:
**lists are mutable**(can change the elements inside it). Tuple, str, int are immutable. - Aliasing, two variable point to same list, may get bug. E.g. X = [‘1’, ‘2’, ‘3’], Y = X, changing X will change the value of Y.
- E.g.
**X = [1, ‘a’, ‘b’, [‘Tree’, 2, 93], ‘Car’]**

- Dictionaries
- Unlike tuples and lists, where their indeces starts from 0 to n – 1, indices (key) of dictionary can be values of any immutable type.
**Collection of <key, value> pair.**- Since the indices can be any values, dictionaries elements are unordered.
- E.g.
**monthNumbers = {‘Jan’:1, ‘Feb’:2, ‘Mar’:3, 1:’Jan’, 2:’Feb’, 3:’Mar’}**