Recursive Algorithm and Induction 1. Give a recursive algorithm that takes as in
ID: 3880817 • Letter: R
Question
Recursive Algorithm and Induction
1. Give a recursive algorithm that takes as input two non-negative integers x and y and
returns their sum, x + y. The only arithmetic operation your algorithm can perform is
incrementing an integer value, e.g. x++, and decrementing an integer value, e.g. x.
2. Use induction to prove that your algorithm always returns a correct answer.
3. State a correct claim about the number of increment and decrement operations your
algorithm makes to compute x + y and use induction to prove that your claim is correct.
Explanation / Answer
1. I am writing a simple algorithm irrespective of any language.//it slightly matches with C/C++
Calculate_sum(x,y) //Calculate_sum is the name of function which takes x,y as arguments.
{
if(x==0)//termination condition. If x becomes 0, it returns y
return y;
x--;//decreasing x
y++;//increasing y(y will be the answer)
return Calculate_sum(x,y)//recursive call
}
2.Prove that my algorithm is correct by induction.
Calculate_sum(0,y) =y
Assume that Calculate_sum(x,y) gives correct answer. i.e Calculate_sum(x,y) = x+y ......(1)
Now, Calculate_sum(x+1,y) should also be true.
Acc. to algorithm
Calulate_sum(x+1,y) = calculate_sum(x,y+1) (Since x is decreased by one and y is increased by one)
= x+(y+1) (Acc. to eqn (1))
= (x+1) +y
Therefore Calulate_sum(x+1,y) is correct if Calulate_sum(x,y) is correct.
Hence our algorithm is correct by induction.
3. In our algorithm,
No. of increment operations = x
No. of decrement operations = x
Total = 2x
No. of increment operations in Calculate_sum(0,y) = 0(As function returns y directly without any operation)
Let assume no. of increment operations in Calculate_sum(x,y) = x.
Now no. of increment operations in Calculate_sum(x+1,y) = 1 + no. of increment operations in Calculate_sum(x,y+1)
= 1 + x
Therefore , no. of increment operations in Calculate_sum(x+1,y) is also correct whenever Calculate_sum(x,y)
is correct.
Hence no. of increment operations in Calculate_sum(x,y) =x. (Proved by induction)
Similarly no. of decrement operations in Calculate_sum(x,y) =x. (can be proved in similar way as above).
Total = 2x.
Please upvote. Thank you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.