Recursion for finding the smallest path of numbers in an array

Question

i have the array [0,1,3,4,1]. With this array I need to write a recursive function that either:

Goes to the next element, or
Skips the next element and goes to the one after it (can only skip a max of 1 element)

the condition being that it needs to be the smallest number possible. The solution to this problem is as follows:

start at 0
skip 1 and go to 3
skip 4 and go to 1
add the unskipped elements and return it

I have started the function with its base case:

private int play(int[] a, int first, int last) {
    int result = 0;

    // base case
    if (first == last){
        return a[first];
    }
    else{
        //result = play(a,first+1,last);
        //System.out.println(result);
    }
    return result;

}

with first = 0 and last = array_length -1. Note, the array can have any number of elements, so say if I had the array [0 4 23 566 34 45 555 11 34 35 45 65 55 98 344] the lowest total would be 591.

Please bear with me, I am new to this recursion thing. Thanks in advance

So its suppose to return the numbers that you don't skip over all added up? — 3kings
– 3kings, Commented Oct 21, 2015 at 20:06
So you are allowed to skip numbers, but never skip more than one number in a row? — tobias_k
– tobias_k, Commented Oct 21, 2015 at 20:12
@tobias_k yes, the function cannot skip more than one element — user3170251
– user3170251, Commented Oct 21, 2015 at 20:14
You are on the right track, you just need to determine if the recursive call uses first+1 or first+2 (using the condition you mentioned). Hint: beware case where first+2 would be beyond last. — secolive
– secolive, Commented Oct 21, 2015 at 20:15

gonzo · Accepted Answer · 2015-10-21 21:18:18Z

2

I would do something like this where you keep track of what current index you are currently on and the sum so far up to the point of that index following the path (so the sum would exclude the numbers we skipped).

public static int play(int[] a, int index, int sum){
    if (index>=a.length) return Integer.MAX_VALUE;  //Path went over last index. Invalid Path. 
    sum += a[index];  //Add on to the sum of the index you are currently on
    if (index == a.length-1){
        return sum;  //If we are at last element, return sum of the path traveled
    }else{
        return Math.min(play(a, index+1, sum), play(a, index+2, sum)); //Continue onto path checking both options
    }
}

Test Code:

public static void main(String args[]) {
    int[] a = new int[]{0, 4, 23, 566, 34, 45, 555, 11, 34, 35, 45, 65, 55, 98, 344};
    System.out.println(play(a, 0, 0));
}

Output: 591

Hope this helps.

Edit: Okay, removing all the code and just thinking about this logically. The way I like to think of recursion (especially with paths) is that I am sending out individual little men and after each recursion I am going to duplicate those little men to take different paths. Lets use the smaller array, [0,1,3,4,1], for this example.

We start off with one little man. He starts off at 0. He has 2 options. First option is to go to 1 and second option is to go to 3. We need to go down both of these paths since we are unsure what lies ahead. The little man duplicates himself sending one person to 1 and another to 3.

Now the little man that went to path 1 has 2 more options laying ahead. He can either go to 3 or 4. The little man that went to path 3 also has 2 more options. He can go to 4 or 1. So they duplicate themselves and send the little men through all the options. I'm hoping this all makes sense at this point. The code that handles the duplication of the little man to different paths is: play(a, index+1, sum), play(a, index+2, sum))

What does a little man do once it reaches the end of the path? He has to tell the original little man how far the path is. The code for this is: if (index == a.length-1){return sum;}

The original little man, though, doesn't care about that one path. He needs to compare it to the counterpart that went the other path to see which one is shorter. That is controlled by the Math.Min. Which just returns the shorter distance of the 2 little men. So the little man that has the shorter of the distances kills his clone (:p) since we do not like that path. Eventually all of the little men will kill each other leaving only one little man standing which is the shortest distance. :)

edited Oct 21, 2015 at 21:18

answered Oct 21, 2015 at 20:32

gonzo

2,1312 gold badges18 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

user3170251 Over a year ago

this function does indeed work, but I have a midterm to attend to. Could you explain the function step by step? I would really like to understand how recursion works.

gonzo Over a year ago

@user3170251 yup for sure. I'll add some more text. Let me know if there is a specific section you are not understanding.

gonzo Over a year ago

@user3170251 let me know if that at all makes sense. It is a little hard to teach this over text. :p

user3170251 Over a year ago

this example is brilliant. I'm definitely saving this explanation for possible future projects.

user3170251 Over a year ago

quick question code-wise, why is Integer.MAX_VALUE used

|

Collectives™ on Stack Overflow

Recursion for finding the smallest path of numbers in an array

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related