Consider the following pseudo code for a procedure search (L,a) inwhich the list
ID: 3610938 • Letter: C
Question
Consider the following pseudo code for a procedure search (L,a) inwhich the list L is selected to see if contains the entry a. Notethat L[1] is the first entry of L.procedure search(L,a)
if (L is empty) then return false;
if(L[1] is equal to a) then returntrue;
M=list obtained be removing L[1] formL;
return search(M,a)
endProcedure
a) Which feature or property of the above pseudo code forsearch(L.a) ensures that search(L,a) is recursive?
b) Which features or properties of the above pseudo code ensurethat the calls to search stop after a certain point?
c) The procedure search(L,a) is called with L={1,2,3} and a=2.Describe the sequence of statements carried out by thecomputer.
please give an explanation as well,
lifesaver points
Explanation / Answer
a) Which feature or property of the above pseudo code forsearch(L.a) ensures that search(L,a) is recursive? The search is recursive since the procedure Search(L,a) callsSearch(M, a) unless L is empty where M is L without L[1]. So teh procedure Search is being called recursively till the listbecomes empty. Therefore Search(L, a) is recursive b) Which features or properties of the above pseudo code ensurethat the calls to search stop after a certain point? The Search procedure terminates if L[1] is equal to aor every time the Search is being called with the first elementremoved. As the list L has finite size n, after n+1 calls the listsize will be zero i.e empty and the procedure Search stops. Therefore this pseudo code will run n+1 times if the element is notthere in the list or it runs for less than or equal to ntimes if the element a is in the list L As the number of calls are limited, the Search procedureterminates c) The procedure search(L,a) is called with L={1,2,3} and a=2.Describe the sequence of statements carried out by thecomputer. search( {1,2,3}, 2) 1) compares whether L is empty [as L is not empty..it goes tonext statement] 2) compares L[1] with a [As L[1] =1 is not equal to 2..it goes tonext statement] 3) obtains M = {2, 3} 4) calls Search({2,3} , 2) and waits for the value to bereturned 4.1) compares whether {2, 3} is empty [as{2, 3} is not empty it goes to next statement} 4.2) compares M[1] with 2 and returns true [it terminates the search as M[1] is 2 which is equal to 2] 5) now Search({1,2,3}, 2) returns true