Recursive Definitions and Structural InductionRecursionRecursion exampleSlide 4FractalsSlide 6Fibonacci sequenceFibonacci sequence in JavaRecursion definitionBad recursive definitionsDefining sets via recursionSlide 12Defining strings via recursionSlide 14String length via recursionStrings via recursion exampleRecursion prosRecursion consTreesRooted trees(Extended) Binary treesFull binary treesBinary tree heightBinary tree sizeRecursion vs. inductionSlide 27Slide 28What did we just do?Structural inductionTree structural induction exampleSlide 32String structural induction exampleSlide 34Induction methods comparedInduction types comparedVia weak mathematical inductionVia strong mathematical inductionVia structural inductionAnother way via structural inductionBut wait!Recursive definition examplesMore more examplesMore more more examplesMore^4 examplesMore^5 examplesMore^6 examplesMore^7 examples1Recursive Definitions and Structural InductionCS 202Epp section ???Aaron Bloomfield2Recursion•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)3Recursion example–Find f(1), f(2), f(3), and f(4), where f(0) = 1a) 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 = 9b) 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 = 814Recursion example–Find f(1), f(2), f(3), and f(4), where f(0) = 1c) 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 = 65536d) 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 = 336735Fractals•A fractal is a pattern that uses recursion–The pattern itself repeats indefinitely6Fractals7Fibonacci sequence•Definition of the Fibonacci sequence–Non-recursive:–Recursive: F(n) = F(n-1) + F(n-2)or: F(n+1) = F(n) + F(n-1)•Must always specify base case(s)!–F(1) = 1, F(2) = 1–Note that some will use F(0) = 1, F(1) = 1   nnnnF255151)(8Fibonacci sequence in Javalong 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)));}9Recursion definition•From “The Hacker’s Dictionary”:•recursion n. See recursion. See also tail recursion.10Bad 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)?11Defining 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  S12Defining sets via recursion•Give recursive definitions for:a) The set of odd positive integers1  SIf x  S, then x+2  Sb) The set of positive integer powers of 33  SIf x  S, then 3*x  Sc) The set of polynomials with integer coefficients0  SIf p(x)  S, then p(x) + cxn  S–c  Z, n  Z and n ≥ 013Defining 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?14Defining strings via recursion•Let  = { 0, 1 }•Thus, * is the set of all binary numbers–Or all binary strings–Or all possible computer files15String 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: 316Strings via recursion example•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  P17Recursion pros•Easy to program•Easy to understand18Recursion 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!19Trees•Rooted trees:–A graph containing nodes and edges•Cannot contain a cycle!Cycle not allowed in a tree20Rooted 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, …, Tn21(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 subtree22Full 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 (denoted by T = T1∙T2)•Note the only difference between a regular binary tree and a full one is the basis step23Binary 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 heighth(T) = 1 + max ( h(T1), h(T2) )•This definition can be generalized to non-binary trees24Binary