Using Recursion 2010 Goodrich Tamassia Using Recursion 1 The Recursion Pattern Recursion when a method calls itself Classic example the factorial function n 1 2 3 n 1 n Recursive definition 1 if n 0 f n else n f n 1 As a C method recursive factorial function recursiveFactorial n if n 0 return 1 basis case else return n recursiveFactorial n 1 recursive case 2010 Goodrich Tamassia Using Recursion 2 Linear Recursion Test for base cases Begin by testing for a set of base cases there should be at least one Every possible chain of recursive calls must eventually reach a base case and the handling of each base case should not use recursion Recur once Perform a single recursive call This step may have a test that decides which of several possible recursive calls to make but it should ultimately make just one of these calls Define each possible recursive call so that it makes progress towards a base case 2010 Goodrich Tamassia Using Recursion 3 Example of Linear Recursion Algorithm LinearSum A n Input A integer array A and an integer n 1 such that A has at least n elements Output The sum of the first n integers in A if n 1 then return A 0 else return LinearSum A n 1 A n 1 2010 Goodrich Tamassia Example recursion trace call return 15 A 4 15 5 20 LinearSum A 5 Using Recursion call return 13 A 3 13 2 15 LinearSum A 4 call return 7 A 2 7 6 13 LinearSum A 3 call return 4 A 1 4 3 7 LinearSum A 2 call return A 0 4 LinearSum A 1 4 Reversing an Array Algorithm ReverseArray A i j Input An array A and nonnegative integer indices i and j Output The reversal of the elements in A starting at index i and ending at j if i j then Swap A i and A j ReverseArray A i 1 j 1 return 2010 Goodrich Tamassia Using Recursion 5 Defining Arguments for Recursion In creating recursive methods it is important to define the methods in ways that facilitate recursion This sometimes requires we define additional paramaters that are passed to the method For example we defined the array reversal method as ReverseArray A i j not ReverseArray A 2010 Goodrich Tamassia Using Recursion 6 Computing Powers The power function p x n xn can be defined recursively 1 if n 0 p x n x p x n 1 else This leads to an power function that runs in O n time for we make n recursive calls We can do better than this however 2010 Goodrich Tamassia Using Recursion 7 Recursive Squaring We can derive a more efficient linearly recursive algorithm by using repeated squaring 1 if x 0 p x n x p x n 1 2 2 2 p x n 2 if x 0 is odd if x 0 is even For example 24 25 26 27 2 4 2 2 24 2 2 22 2 42 16 21 4 2 2 2 24 2 2 2 22 2 2 42 32 2 6 2 2 26 2 2 23 2 82 64 21 6 2 2 2 26 2 2 2 23 2 2 82 128 2010 Goodrich Tamassia Using Recursion 8 Recursive Squaring Method Algorithm Power x n Input A number x and integer n 0 Output The value xn if n 0 then return 1 if n is odd then y Power x n 1 2 return x y y else y Power x n 2 return y y 2010 Goodrich Tamassia Using Recursion 9 Analysis Algorithm Power x n Input A number x and integer n 0 Output The value xn if n 0 then return 1 if n is odd then y Power x n 1 2 return x y y else y Power x n 2 return y y 2010 Goodrich Tamassia Using Recursion Each time we make a recursive call we halve the value of n hence we make log n recursive calls That is this method runs in O log n time It is important that we use a variable twice here rather than calling the method twice 10 Tail Recursion Tail recursion occurs when a linearly recursive method makes its recursive call as its last step The array reversal method is an example Such methods can be easily converted to nonrecursive methods which saves on some resources Example Algorithm IterativeReverseArray A i j Input An array A and nonnegative integer indices i and j Output The reversal of the elements in A starting at index i and ending at j while i j do Swap A i and A j i i 1 j j 1 return 2010 Goodrich Tamassia Using Recursion 11 Another Binary Recusive Method Problem add all the numbers in an integer array A Algorithm BinarySum A i n Input An array A and integers i and n Output The sum of the n integers in A starting at index i if n 1 then return A i return BinarySum A i n 2 BinarySum A i n 2 n 2 Example trace 0 8 0 4 4 4 0 2 0 1 2 2 1 1 2010 Goodrich Tamassia 2 1 4 2 3 1 4 1 Using Recursion 6 2 5 1 6 1 7 1 12 Computing Fibonacci Numbers Fibonacci numbers are defined recursively F0 0 F1 1 Fi Fi 1 Fi 2 for i 1 Recursive algorithm first attempt Algorithm BinaryFib k Input Nonnegative integer k Output The kth Fibonacci number Fk if K 0 then return 0 if k 1 then return 1 else return BinaryFib k 1 BinaryFib k 2 2010 Goodrich Tamassia Using Recursion 13 Analysis Let nk be the number of recursive calls by BinaryFib k n0 1 n1 1 n2 n1 n0 1 1 1 1 3 n3 n2 n1 1 3 1 1 5 n4 n3 n2 1 5 3 1 9 n5 n4 n3 1 9 5 1 15 n6 n5 n4 1 15 9 1 25 n7 n6 n5 1 25 15 1 41 n8 n7 n6 1 41 25 1 67 Note that nk at least doubles every other time That is nk 2k 2 It is exponential 2010 Goodrich Tamassia Using Recursion 14 Analysis T N T N 1 T N 2 1 T N 2 T N 3 1 T N 3 T N 4 1 1 T N 2 T N 3 T N 3 T N 4 3 If we repeat the recurrence we re going to get 8 T s on level 3 Then 16 32 and so on So we get 2 k T s at level k To get down T N 1 to the base case T 2 we ll need to go to level k N 2 We ll have 2 N 2 T s there so T N O 2 N 2010 Goodrich Tamassia Using Recursion 15 GCD Function definition gcd x y x gcd y reminder x y if y 0 if y 0 function gcd is input integer …