Jundallah3 Jundallah3 - 29 days ago 16
C Question

Number of steps to transform X to Y. (Integers)

So I am confused on how this recursive function works. I don't understand how this actually produces the answer. The question states:

Write a recursive function that returns the minimum number of steps
necessary to transform X to Y. If X > Y, return 1000000000, to indicate that no solution exists.(For example, if X = 13 and Y = 28, the correct response would be 2 - first you would add 1 to13 to obtain 14, then multiply 14 by 2 to obtain 28.) Feel free to call the provided function

This is the solution:

int min(int x, int y) {
if (x < y) return x;
return y;
}

// Returns the minimum number of steps to transform x into y, or
// 100000000 to indicate no solution.
int minSteps(int x, int y) {
if (x > y) return NO_SOLUTION;
if (x == y) return 0;
int mult = 1 + minSteps(2*x, y);
int add = 1 + minSteps(x+1, y);
return min(add, mult);
}


If someone can please explain the solution that will be great. Thanks!

Answer

In the core of many problems that can be solved with recursion lies the principle of reduction of the original problem to a smaller one and continuing the process until it diminishes to a known one.

This problem perfectly suits for such approach. Your answer is a series of arithmetic operations that convert x to y. I.e., something like this:

x ? a ? b ? c ? ... ? y

Where ? denotes either multiplication by 2 or addition of 1; and a,b,c... represent the intermediate results after applying the operation on a previous result. For example, transformation of 5 to 22 can be described this way:

5 (*2) 10 (+1) 11 (*2) 22

Now let's get back to the reduction principle. Starting with a given x, we need to choose the first step. It can be either *2 OR[1] +1, we don't know it yet, so we need to check them both. In the case of *2, the x transforms to 2x and in the case of +1, the x transforms to x+1. And voila, we progressed one step and reduced the problem! Now we have 2 smaller problems to solve - one for 2x and one for x+1, and find the minimum between the results. Since we're counting the steps, we create 2 distinct counters (one for each type of operation taken) and add 1 to each one of them (since we performed one step already). To complete the calculation of the actual value of each counter we need to solve the two smaller problems - and to solve them we call the function recursively with the new input (twice, once per input). The algorithm continues this way, reducing the problem each time until getting to a stop condition, which can be either x == y (it's a valid transformation) or x > y (invalid transformation). In case of x == y there are exactly 0 steps required and the execution stops, causing the call stack to fall back, populating the actual value of the counter that originated the recursion branch. In case of x > y the result is 1000000000 (which is assumed to be too large to be an actual result and thus the sum will be dropped as larger than the sum from the second branch). This process is usually better understood by visualizing with recursion tree (see @DavidBowling answer, for example. Err, deleted for some reason...).

[1] Although in this problem it's very clear, but sometimes the distinction between the operations can be vague. It's very important to dissect the problem into a number of smaller ones, without any overlap between them.