Given the following recursive search function, prove by induction that it correc

Question

Given the following recursive search function, prove by induction that it correctly returns 1 if the value val is in the array v and 0 otherwise. (Hint: try working out all the possibilities for arrays of size = 1 to get a sense of how your proof should proceed.)

int search(v[]: integer array, size: integer, val: integer)

if (size == 0) return 0;

else

if (v[size-1] == val) return 1;

else return search(v, size-1, val);

You will need to provide at least these details in a complete proof:

Basis: The case where size = 0

Inductive Hypothesis: Assume...

Inductive Step:

Explanation / Answer

int search(v[]: integer array, size: integer, val: integer)

if (size == 0) return 0;

else

if (v[size-1] == val) return 1;

else return search(v, size-1, val);

to v

What is happening in this program is that every time the function is called, the values are being checked at the last index ie, size-1.

So for every call, the last element of the array is being checked if it equals to val. If yes return 1 else call the function again by decreasing its size by 1.

Now in the second time, since we decrease the size by 1, the comparison is between the second last array element and the value val. If its a match return 1 else return 0.

Continue this until you reach the first element of the array.

Basis: The case where size = 0

Inductive Hypothesis: Assume the array is empty

Inductive Step:Hence no result since the array is empty...return 0

Basis: The case where size!=0

Inductive Hypothesis: Assume the array is not empty

Inductive Step:search(v, size-1, val), if true return 1

                     else call search(v, size-1, val);//note here the actual size is 1 less than that in previous step

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.