Recursive Definitions and Structural Induction CS APMA 202 Rosen section 3 4 Aaron Bloomfield 1 Recursion Recursion means defining something such as a function in terms of itself For example let f x x We can define f x as f x x f x 1 2 Recursion example Rosen section 3 4 question 1 a Find f 1 f 2 f 3 and f 4 where f 0 1 Let f n 1 f n 2 f 1 f 0 2 1 2 3 f 2 f 1 2 3 2 5 f 3 f 2 2 5 2 7 f 4 f 3 2 7 2 9 b Let f n 1 3f n f 1 3 f 0 3 1 3 f 2 3 f 1 3 3 9 f 3 3 f 2 3 9 27 f 4 3 f 3 3 27 81 3 Recursion example Rosen section 3 4 question 1 c Find f 1 f 2 f 3 and f 4 where f 0 1 Let f n 1 2f n f 1 2f 0 21 2 f 2 2f 1 22 4 f 3 2f 2 24 16 f 4 2f 3 216 65536 d Let f n 1 f n 2 f n 1 f 1 f 0 2 f 0 1 12 1 1 3 f 2 f 1 2 f 0 1 32 3 1 13 f 3 f 2 2 f 0 1 132 13 1 183 f 4 f 3 2 f 0 1 1832 183 1 33673 4 Fractals A fractal is a pattern that uses recursion The pattern itself repeats indefinitely 5 Fractals 6 Fibonacci sequence Definition of the Fibonacci sequence Non recursive 1 5 1 5 F n Recursive or F n F n 1 F n 2 F n 1 F n F n 1 n n 5 2 n Must always specify base case s F 1 1 F 2 1 Note that some will use F 0 1 F 1 1 7 Fibonacci sequence in Java long Fibonacci int n if n 1 n 2 return 1 else return Fibonacci n 1 Fibonacci n 2 long Fibonacci2 int n return long Math pow 1 0 Math sqrt 5 0 n Math pow 1 0 Math sqrt 5 0 n Math sqrt 5 Math pow 2 n 8 Recursion definition From The Hacker s Dictionary recursion n See recursion tail recursion See also 9 Bad recursive definitions Consider f 0 1 f n 1 f n 2 What is f 1 Consider f 0 1 f n 1 f n What is f 1 10 Defining sets via recursion Same two parts Base case or basis step Recursive step Example the set of positive integers Basis step 1 S Recursive step if x S then x 1 S 11 Defining sets via recursion Rosen section 3 4 question 24 give recursive definitions for a The set of odd positive integers b The set of positive integer powers of 3 c 1 S If x S then x 2 S 3 S If x S then 3 x S The set of polynomials with integer coefficients 0 S If p x S then p x cxn S c Z n Z and n 0 12 Defining strings via recursion Terminology is the empty string is the set of all letters a b c z The set of letters can change depending on the problem We can define a set of strings as follows Base step If w and x then wx Thus s the set of all the possible strings that can be generated with the alphabet Is this countably infinite or uncountably infinite 13 Defining strings via recursion Let 0 1 Thus is the set of all binary numbers Or all binary strings Or all possible computer files 14 String length via recursion How to define string length recursively Basis step l 0 Recursive step l wx l w 1 if w and x Example l aaa l aaa l aa 1 l aa l a 1 l a l 1 l 0 Result 3 15 Today s demotivators 16 Strings via recursion example Rosen section 3 4 question 38 Give a recursive definition for the set of string that are palindromes We will define set P which is the set of all palindromes Basis step P Second basis step x P when x Recursive step xpx P if x and p P 17 Strings and induction example This requires structural induction which will be covered later in this slide set 18 Recursion pros Easy to program Easy to understand 19 Recursion cons Consider the recursive Fibonacci generator How many recursive calls does it make F 1 1 F 2 1 F 3 3 F 4 5 F 5 9 F 10 109 F 20 13 529 F 30 1 664 079 F 40 204 668 309 F 50 25 172 538 049 F 100 708 449 696 358 523 830 149 7 1020 At 1 billion recursive calls per second generous this would take over 22 000 years But that would also take well over 1012 Gb of memory 20 Trees Rooted trees A graph containing nodes and edges Cannot contain a cycle Cycle not allowed in a tree 21 Rooted trees Recursive definition Basis step A single vertex r is a rooted tree Recursive step Let T1 T2 Tn be rooted trees Form a new tree with a new root r that contains an edge to the root of each of the trees T1 T2 Tn 22 Extended Binary trees Recursive definition Basis step The empty set is an extended binary tree Recursive step Let T1 and T2 be extended binary trees Form a new tree with a new root r Form a new tree such that T1 is the left subtree and T2 is the right subtree 23 Full binary trees Recursive definition Basis step A full binary tree consisting only of the vertex r Recursive step Let T1 and T2 be extended binary trees Form a new tree with a new root r Form a new tree T such that T1 is the left subtree and T2 is the right subtree This is denoted by T T T 1 2 Note the only difference between a regular binary tree and a full one is the basis step 24 Binary tree height h T denotes the height of tree T Recursive definition Basis step The height of a tree with only one node r is 0 Recursive step Let T1 and T2 be binary trees The binary tree T T1 T2 has height h T 1 max h T1 h T2 This definition can be generalized to non binary trees 25 Binary tree size n T denotes the number of vertices in tree T Recursive definition Basis step The number of vertices of an empty tree is 0 Basis step The number of vertices of a tree with only one node r is 1 Recursive step Let T1 and T2 be binary trees The number of vertices in binary tree T T1 T2 is n T 1 n T1 …