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.

Diagram of function calls of multiplication through recursion by Ling Gen Sheng Shaun
Diagram of function calls of multiplication through recursion by Ling Gen Sheng Shaun

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.

Loop example for multiplication and exponentiation(a^{b})

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’}

Leave a Reply