Proofs, Recursion and Analysis of AlgorithmsRecursive SequencesRecursive functionRecursively defined operationsRecursively defined algorithmsRecursive algorithm for selection sortSelection Sort ExampleRecursive algorithm for binary searchBinary Search ExampleClass exerciseProofs, Recursion and Analysis of AlgorithmsMathematical Structures for Computer ScienceChapter 2Copyright © 2006 W.H. Freeman & Co. MSCS Slides Proofs, Recursion and Analysis of AlgorithmsSection 2.4 Recursive Definitions 2Recursive SequencesDefinition: A sequence is defined recursively by explicitly naming the first value (or the first few values) in the sequence and then defining later values in the sequence in terms of earlier values.Examples: S(1) = 2S(n) = 2S(n-1) for n 2•Sequence S 2, 4, 8, 16, 32,….T(1) = 1T(n) = T(n-1) + 3 for n 2•Sequence T 1, 4, 7, 10, 13,….Fibonaci SequenceF(1) = 1F(2) = 1 F(n) = F(n-1) + F(n-2) for n > 2•Sequence F 1, 1, 2, 3, 5, 8, 13,….Section 2.4 Recursive Definitions 3Recursive functionAckermann functionn+1 m = 0A(m,n) = A(m-1, 1) for m > 0 and n = 0A(m-1, A(m,n-1)) for m > 0 and n > 0Find the terms A(1,1), A(2,1), A(1,2)A(1,1) = A(0, A(1,0)) = A(0, A(0,1)) = A(0,2) = 3A(1,2) = A(0, A(1,1)) = A(0, 3) = 4A(2,1) = A(1, A(2,0)) = A(1, A(1,1)) = A(1, 3) = A(0, A(1,2)) = A(0, 4) = 5Using induction it can be shown that A(1,n) = n + 2 for n = 0,1,2…A(2,n) = 2n + 3 for n = 0,1,2…Section 2.4 Recursive Definitions 4Recursively defined operationsExponential operationa0 = 1an = aan-1 for n 1Multiplication operationm(1) = m m(n) = m(n-1) + m for n 2Factorial OperationF(0) = 1F(n) = nF(n-1) for n 1Section 2.4 Recursive Definitions 5Recursively defined algorithmsIf a recurrence relation exists for an operation, the algorithm for such a relation can be written either iteratively or recursivelyExample: Factorial, multiplication etc.S(1) = 1S(n) = 2S(n-1) for n 2S(integer n) //function that iteratively computes the value S(n)Local variables: integer i ;//loop index CurrentValue ;if n =1 thenoutput 2j = 2CurrentValue = 2while j n CurrentValue = CurrentValue *2j = j+1end whilereturn CurrentValueend ifend function SS(integer n) //recursively calculates S(n) if n =1 then //base caseoutput 2 elsereturn (2*S(n-1)) end ifend function SSection 2.4 Recursive Definitions 6Recursive algorithm for selection sort Algorithm to sort recursively a sequence of numbers in increasing or decreasing orderFunction sort(List s,Integer n) //This function sorts in increasing order if n =1 thenoutput “sequence is sorted” //base case end if max_index = 1 //assume s1 is the largest for j = 2 to n doif s[j] > s[max_index] thenmax_index = j //found larger, so updateend if end for exchange/swap s[n] and s[max_index] //move largest to the end return(sort(s,n-1)) end function sortSection 2.4 Recursive Definitions 7Selection Sort ExampleSequence S to be sorted:S: 23 12 9 –3 89 54After 1st recursive call, the sequence is: Swap -3 and 23 S: -3 12 9 23 89 54After 2nd recursive call, the sequence is:Swap 12 and 9S: -3 9 12 23 89 54After 3rd and 4th recursive call, the sequence is:Nothing is swapped for the next two recursive calls as elements happen to be in increasing order.S: -3 9 12 23 89 54After 5th recursive call, the sequence is:S: -3 9 12 23 54 89Final sorted array S: -3 9 12 23 54 89Section 2.4 Recursive Definitions 8Recursive algorithm for binary searchLooks for a value in an increasing sequence and returns the index of the value if it is found or 0 otherwise.Function binary_search(s, j, k, key)if j > k then //not foundreturn 0 end if m = (j+k)/2 if key = sk then // base case return (m) end if if key < sk then k = m-1 else j = m+1 end if return(binary_search(s,j,k,key)) end binary_searchSection 2.4 Recursive Definitions 9Binary Search ExampleSearch for 81 in the sequence 3 6 18 37 76 81 92Sequence has 7 elements.Calculate middle point: (1 + 7)/2 = 4.Compares 81 to 37 (4th sequence element): no match.Search in the lower half since 81 > 37New sequence for search: 76 81 92Calculate midpoint: (5 + 7)/2 = 66th Element: 81 Compares 81 to 81: perfect match Element 81 found as the 6th element of the sequenceSection 2.4 Recursive Definitions 10Class exerciseWhat does the following function calculate?Function mystery(integer n) if n = 1 thenreturn 1 elsereturn (mystery(n-1)+1) end if end function mysteryWrite the algorithm for the recursive definition of the following sequencea, b, a+b, a+2b, 2a+3b,
View Full Document