# 6.00.1x Week 3

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:
$a \times b = a \mbox{; if } b = 1$ (Base case)
$a \times b = a + a \times (b - 1) \mbox{; otherwise}$ (Recursive case)

The implementation of the code is as follows:

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:

1. If n = 0, then LHS is 0 and RHS is (0(0+1)) / 2 = 0, so true. (Base case)
2. 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)
3. 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:

1. Base case: Mul (a, b) = a is true for b = 1. Mul(3, 1) = 3, so it’s true.
2. 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.
3. By induction the equation is true for all values.

## Examples of functions that can be called recursively

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

## Difference between loop and recursion

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

## Recursion example for multiplication and exponentiation($a^{b}$)

base case: b = 1
recursive step: a + a * (b-1)

base case: exp = 0
recursive step: base * base ^ (exp – 1)

## Compound data types

Compound data types are combination of simpler data types.

1. 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’)
2. 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’]
3. 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’}