SUNY Geneseo Department of Mathematics

Introduction to Recursion

Tuesday, September 22

Math 303
Fall 2015
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc
- Colloquium
  - “Suspect Something Fishy? How Statistics Can Help Detect It, Quickly!”
  - Dr. Aleksey Polunchenko, SUNY Binghamton
  - Wednesday, Sept. 23, 2:45
  - Newton 204
  - Extra credit for short write-ups, like last colloquium
Questions?
Recursion
- Video lecture
  - Recursion = function or definition that calls or refers to itself
  - Comparison to iteration
```
factorial( n )                        factorial( n )
    if n = 0                              f = 1
        return 1                          for i = 1 to n
    else                                      f = f * i
        return n * factorial(n-1)         return f
```
- Examples
  - Fast multiplication algorithm
    - For x a non-negative integer…
      - xy = 0 if x = 0
      - xy = (x/2) (2y) if x > 0 is even
      - xy = (x-1)y + y if x > 0 is odd
    - Pseudocode
```
times( x, y )    // x is a natural number
    if x = 0
        // base case
        return 0
    else if x > 0 and even
        // recursive case 1
        return times( x/2, 2*y )
    else         // x > 0 and odd
        // recursive case 2
        return times( x-1, y ) + y
```
    - Matlab code and runs
```
function product = times( x, y )
if x == 0
    product = 0;
elseif mod(x,2) == 0
    product = times( x/2, 2*y);
else
    product = times( x-1, y ) + y;
end
end
>> times( 3, 4 )
ans =
    12
>> times( 0, 4 )
ans =
     0
>> times( 16, 3 )
ans =
    48
```
    - Correctness proof
      - Induction on x
      - Base case: x = 0, “if x = 0 return 0”
      - Induction hypothesis:
        times( x, y ) = xy for all 0 ≤ x < k (strong induction)
      - Induction step:
        Show times( k, y ) = ky, k > 0
        Case 1: k even
        times( k, y ) = times( k/2, 2y )
        = (k/2) (2y) (induction hyp)
        = ky (algebra)
        Case 2: k odd
        times( k, y ) = times( k-1, y ) + y
        = (k-1)y + y
        = ky
  - Peano arithmetic
    - Definition of “natural number”
      - 0 is a natural number
      - “s(x)” is a natural number if x is
    - Recursively convert from decimal form to Peano form
    - Pseudocode
```
toPeano( n )    // returns string
    if n = 0
        return “0”
    else
        return concatenate( “s(”, toPeano(n-1), “)” )
```
    - Matlab code and runs
```
function p = toPeano( n )
if n == 0
    p = '0';
else
    p = [ 's(' toPeano(n-1) ')' ];
end
end
>> toPeano( 11 )
ans =
s(s(s(s(s(s(s(s(s(s(s(0)))))))))))
>> toPeano( 0 )
ans =
0
```
    - Correctness
      - Base case: n = 0, “if n = 0 return ‘0’” matches Peano’s definition
      - Induction hypothesis: for all 0 ≤ x < k toPeano(x) returns Peano form of x (i.e., “s(s(s(...s(0)...))” )
      - Induction step: toPeano( k ) concatenates “s(” to “s(s(....s(0)...))” with “)” afterward
- Problem set
  - Handout
Next
- More recursion examples

Next Lecture