Question

I know how induction works but I can't quite figure out how to use it to show the following code works (see picture) Any help well appreciated!
https://s.yimg.com/hd/answers/i/c8602f05ab344ac4a156792852afd52a_A.png?a=answers&mr=0&x=1454886113&s=00fce6326842a0d02d9dda40378af4e5

Answer 1

That's some pretty cool recursive code, continually cutting the string in half and putting the second half before the first half.

Not sure what you're looking for, but it can properly reverse an inputted string.

Answer 2

@woodrow73 Yeah exactly it reverses an inputted string, but I'm supposed to prove it by somehow using the induction methode and I'm not sure how I can do that

Answer 3

you can start with saying, for any string of N length, you know it works for sure. Then say, we want to prove for n+1. Then, when you pass in N+1 as the string, what happens? You can have 2 cases. If N+1 is even and if N+1 is odd.

Answer 4

Odd: (0-N/2), with n/2 evaluated to the lower integer. for instance if N+1 is 11, then N/2 will evaluate to 5. Because you know string of N length already works, and since that also has N/2 = 5, mystery(a) will evaluate correctly.

Answer 5

and you can make similar arguments for the other one and finish the proof. OR!! there's a much simpler way to do it.

Answer 6

you could simply use strong induction, because we know it works for all strings of length n , and when it is n+1, on the first recursive call, mystery(n/2, n+1) will be returned. And by the induction hypothesis we know this call work. Thus, when the function returns, it will have effectively returned the palindrome of the string.

Answer 7

@Curry hmmm okay yeah I see where you are going. Thx a lot for you help! :)