From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Mar 31 20:21:01 2008 Date: Mon, 31 Mar 2008 20:20:46 -0400 From: "William J. Rapaport" Subject: 191: Another Recursive Algorithm To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: Another Recursive Algorithm ------------------------------------------------------------------------ Here's another example of a recursive algorithm. This one is for computing a^n (i.e., "a" raised to the nth power). First, here's a recursive definition of it: base case: a^0 =def 1 recursive case: a^(n+1) =def a * a^n (Recall that we have already recursively defined * in terms of +, and + in terms of the successor function. So, with this definition, we see that addition (and therefore its inverse, substraction), multiplication (and therefore its inverse, division), and now exponentiation can all be defined based only on Peano's axioms, together with recursion.) Here's the recursive algorithm: (Recall that "\in" is my typed substitute for the set-membership symbol, "R" represents the set of real numbers, and "N" represents the set of natural numbers.) ------------------------------------------------------------------------ procedure power (a \in R, n \in N): begin if n = 0 then power(a,n) := 1 // base case (table look-up) else power(a,n) := a * power(a,n-1) // recursive case end ------------------------------------------------------------------------ Let's trace this to see how it would compute 4^3 (which we know = 64): I'll use "|" (a down arrow) to mean something like "is computed by". V power(4,3): | V a n power(a,n) - - ------------ 4 3 4*power(4,2) | V a n power(a,n) - - ------------ 4 2 4*power(4,1) | V a n power(a,n) - - ------------ 4 1 4*power(4,0) | V a n power(a,n) - - ---------- 4 0 1 (by the table-look-up base case) So, "unwinding", we now know that power(4,0) = 1, so power(4,1) = 4* power(4,0) = 4*1 = 4, so power(4,2) = 4* power(4,1) = 4*(4*power(4,0)) = 4*(4*1) = 16, so power(4,3) = 4* power(4,2) = 4*(4*(4*power(4,0))) = 4*(4*(4*1)) = 64 From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Mar 31 20:22:53 2008 Date: Mon, 31 Mar 2008 20:22:41 -0400 From: "William J. Rapaport" Subject: 191: Still more recursive algorithms To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: Still more recursive algorithms ------------------------------------------------------------------------ For some more recursive algorithms, take a look at: http://www.cse.buffalo.edu/~shapiro/Courses/CSE116/notes5.html