4 replies to this topic

[juanvillegas]

Hi all! This is my first publication here, nice to meet you all. I'm preparing a spoken test for a teaching assistance position. They need me to solve some exercise and explain it correctly to other students. The excercise is quite easy:

"Design and write a recursive function to find wether a given number p is or not prefix of another number n. Both are natural numbers."

I have wrote the following:

isPrefix(n,p)

if n equals p

then true

else if digits in n < digits in p

then false

else

isPrefix(n/10,p);

and something similar with only one base case

if (n==0)

then false;

else

then n==p AND isPrefix(n/10,p);

Is there anything better you can think of? Something more elegant,more intuitive, etc? Which of both would you suggest? The first is more efficient, but the second is more elegant i guess.

Cheers to all!

[LuthfiHakim]

Hi Juan,

I prefer the second approach. I disagree with you, I think it's more efficient than the first one. But I believe you better change the last AND operator into OR, else it will never enter IsPrefix function (if the compiler supports lazy boolean calculation).

[juanvillegas]

Yes, it's definitively OR. Thanks!
However, regarding efficiency, i consider the first as more efficient than the second because an extra comparison statement is lighter than a recursive call.
Anyway, i'll take the second one i guess.

[Momerath]

Your method fails when p is zero. I'd use

Boolean IsPrefix(n, p) {

    if p > n return false

    else return p == n || IsPrefix(n/10, p)

}

It's more efficient as it stops checking once it is impossible for p to be a prefix of n, rather than reducing n down to zero. Of course this only works for positive numbers, but you did restrict it to them :)

[LuthfiHakim]

^ Good call. But I think the original will not fail in returning correct result, although it will enter pointless iteration in some condition :)

@Juan: taking current hardware into consideration, perhaps the difference of efficiencies between both can be neglected. As for the reason why I chose the second approach was because you check for exit condition immediately upon entering the recursive routine. Therefore less possibility to enter endless loop.