Recursion and Induction: Lexical Issues;Recursive ProgrammingGreg PlaxtonTheory in Programming Practice, Spring 2005Department of Computer ScienceUniversity of Texas at AustinLexical Issues• Program layout• Function parameters and binding• The where clause• Pattern matchingTheory in Programming Practice, Plaxton, Spring 2005Program Layout• Unlike many programming languages, white space is significant inHaskell• Line indentation is used to delineate the scope of definitions– A definition with initial indentation k is implicitly ended before thefirst subsequent line with indentation at most k• For example, the following three lines represent a single definitionchCase c -- change case| upper c = uplow c| otherwise = lowup cTheory in Programming Practice, Plaxton, Spring 2005Program Layout: Example• The following (unorthodox) indentation leads to the same definition forthe chCase functionchCase c -- change case| upper c = uplow c| otherwise =lowup c• The following indentation leads to an error, since the last line is notconsidered part of the definition of chCasechCase c -- change case| upper c = uplow c| otherwise =lowup cTheory in Programming Practice, Plaxton, Spring 2005Function Parameters and Binding• Consider the following expression, where f is a function of one argumentf 1+1• In normal mathematics, this will be an invalid expression, and if forced,you will interpret it as f(1+1)• In Haskell, this is a valid expression and it stands for (f 1)+1Theory in Programming Practice, Plaxton, Spring 2005Function Parameters and Binding• To apply a function to a sequence of arguments, simply write thefunction name followed by its arguments; no parentheses are neededunless the arguments are themselves expressions• Some examples involving a function g of two arguments– The expression g x y z stands for (g x y) z– If you write g f x y, it will be interpreted as (g f x) y, so, if youhave in mind the expression g(f(x),y), write it as g (f x) y– You can’t write g(f(x),y), because (f(x),y) will be interpretedas a pair, which is a single itemTheory in Programming Practice, Plaxton, Spring 2005Function Parameters and Binding• Note that unary minus often requires parentheses• For example, the following expression results in an errorinc -2• It is interpreted as (inc -) 2, which yields a type errorTheory in Programming Practice, Plaxton, Spring 2005The where Clause• The following function has three arguments, x, y and z, and itdetermines if x2+ y2= z2pythagoras x y z = (x*x) + (y*y) == (z*z)• The definition would be simpler to read in the following formpythagoras x y z = sqx + sqy == sqzwheresqx = x*xsqy = y*ysqz = z*zTheory in Programming Practice, Plaxton, Spring 2005The where Clause• The following alternative also workspythagoras x y z = sq x + sq y == sq zwheresq p = p*pTheory in Programming Practice, Plaxton, Spring 2005Pattern Matching• Previously we defined function imply as followsimply p q = not p || q• We can instead use pattern matching to define it asimply False q = Trueimply True q = qTheory in Programming Practice, Plaxton, Spring 2005Pattern Matching• We can also define the function imply as followsimply False False = Trueimply False True = Trueimply True False = Falseimply True True = True• Pattern matching can also involve certain sufficiently simple arithmeticexpressionssuc 0 = 1suc (n+1) = (suc n)+1Theory in Programming Practice, Plaxton, Spring 2005Pattern Matching• Unfortunately, a definition such as the following is not permitted sincemultiplication is not allowed with the patterncount 2*t = count tcount 2*t + 1 = (count t) + 1Theory in Programming Practice, Plaxton, Spring 2005Recursive Programming• Computing powers of 2• Counting the 1s in a binary expansion• Multiplication via addition• Fibonacci numbers• Greatest common divisorTheory in Programming Practice, Plaxton, Spring 2005Computing Powers of 2• Here is the definition of a recursive function that computes nonnegativeinteger powers of twopower2 0 = 1power2 (n+1) = 2 * (power2 n)• What is the running time of power2?Theory in Programming Practice, Plaxton, Spring 2005Counting the 1s in a Binary Expansion• Here is the definition of a recursive function that computes the numberof 1’s in the binary representation of its argument, where we assumethat the argument is a natural numbercount 0 = 0count n| even n = count (n ‘div‘ 2)| odd n = count (n ‘div‘ 2) + 1Theory in Programming Practice, Plaxton, Spring 2005Multiplication via Addition• Here is a simple recursive algorithm for performing multiplication viaadditionmlt x 0 = 0mlt x (y+1) = (mlt x y) + x• For what integer arguments does the above approach work?• What is the running time of mlt?Theory in Programming Practice, Plaxton, Spring 2005Multiplication via Addition: A Faster Approach• Consider the more general problem of computing x*y + z over threegiven arguments x, y, and z• The recursive function quickMlt, defined below, performs this taskusing only additionquickMlt x 0 z = zquickMlt x y z| even y = quickMlt (2 * x ) (y ‘div‘ 2) z| odd y = quickMlt (2 * x ) (y ‘div‘ 2) (x + z)• For what integer arguments does the above approach work?• What is the running time of quickMlt?Theory in Programming Practice, Plaxton, Spring 2005Fibonacci Numbers• Here is a recursive algorithm for computing the Fibonacci numbersfib 0 = 0fib 1 = 1fib (n + 2) = (fib n) + (fib (n+1))• What is the running time of fib?• We will see a faster algorithm in a later lectureTheory in Programming Practice, Plaxton, Spring 2005Greatest Common Divisor• The greatest common divisor (gcd) of two positive integers is thelargest positive integer that divides them both• Here is a recursive function corresponding to (the simple version of)Euclid’s gcd algorithmgcd m n| m == n = m| m > n = gcd (m - n) n| n > m = gcd m (n - m)Theory in Programming Practice, Plaxton, Spring 2005Greatest Common Divisor: Efficient Version• Here is a more efficient version of Euclid’s gcd algorithmegcd m n| m == 0 = n| n == 0 = m| m == n = m| m > n = egcd (m ‘rem‘ n) n| n > m = egcd m (n ‘rem‘ m)• The running time of this algorithm is bounded by the number of bitsin the input– An exponential improvement over the simple version in terms ofworst-case running timeTheory in Programming Practice, Plaxton, Spring 2005Greatest Common Divisor: Binary Version• Here is a an efficient “binary version” of