mercredi 23 janvier 2019

How does method call work as a condition ? For recursive backtracking in Java

My question is about how exactly do method call work as a condition of an if/else statement ?

I understand recursion is a method that calls itself by changing the value of its arguments, a solution is tried and if it is the right one the recursion is stopped.

Such simple recursion make sense to me:

/* Given a string, compute recursively (no loops) a new string where all the 
 * lowercase 'x' chars have been changed to 'y' chars.
 */
public String changeXY(String str) {
    if(str.length() == 0)
        return str;

    if(str.charAt(0) == 'x')
        return 'y' + changeXY(str.substring(1));

    return str.charAt(0) + changeXY(str.substring(1));
}

But when a method call is put as a condition of an if statement I don't understand how it works ? What is being checked ? How is it decided if the method call is true and can then return true to stop the recursion ? How are possibilities 'saved' to then backtrack if it is not the right one ? How does the base case work by returning a compare ?

/* Given an array of ints, is it possible to choose a group of some of the 
 * ints, such that the group sums to the given target? This is a classic 
 * backtracking recursion problem. Rather than looking at the whole array, 
 * our convention is to consider the part of the array starting at index 
 * start and continuing to the end of the array. The caller can specify the 
 * whole array simply by passing start as 0. No loops are needed -- the 
 * recursive calls progress down the array.
 */
public boolean groupSum(int start, int[] nums, int target) {
    if(start >= nums.length)
        return target == 0;

    if(groupSum(start+1, nums, target - nums[start]))
        return true;

    if(groupSum(start+1, nums, target))
        return true;

    return false;
}

Both codes were taken from this github.

Thanks!

Aucun commentaire:

Enregistrer un commentaire