help with java hash map

Question

can some one please explain what is happening in the code below and how it ends up with 36?

thanks

edit by Amir Rachum

public class HashMap2009 {
    public static void main (String[] args) {
        Map<String, Integer> myMap2009 = 
            new HashMap<String, Integer>();
        myMap2009.put("one", new Integer(1));
        myMap2009.put("three", new Integer(3));
        myMap2009.put("five", new Integer(5));
        myMap2009.put("seven", new Integer(7));
        myMap2009.put("nine", new Integer(9));
        System.out.println(oddOne(myMap2009));
    }
    private static int oddOne(Map<String, Integer> myMap2009) {
        if (myMap2009.isEmpty())
            return 11;
        else {
            Set<String> st = myMap2009.keySet();
            String key = st.iterator().next();
            int num = myMap2009.get(key);
            myMap2009.remove(key);
            return num + oddOne(myMap2009);
        }
    }
}

Answer 1

This is a simple example of recursion, which results in adding up all the keys in the map one by one and when the map is empty, it adds another 11. This sums up to 36.

Answer 2

That's a recursive function, that each time it is called, add the value of the first element in the map and then remove it.

If the map is empty it return 11

So: 9+7+5+3+1+11 = 36 ( 9,7,5,3,1 for each value in the map and 11 for when it is empty )

BTW, this looks to me as a terrible way to teach recursion ( because the map creates too much noise )

A simpler ( and I think more effective ) way would've been:

import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
public class ArrayList2009 {
    public static void main( String [] args ) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(3);
        list.add(5);
        list.add(7);
        list.add(9);
        System.out.println( addOne( list ) );                        
    }
    private static int addOne( List<Integer> list ){
        if ( list.isEmpty() ) {
            return 11;
        } else {
            Iterator<Integer> i = list.iterator();
            int num = i.next();
            i.remove();
            return num + addOne( list );
        }
    }
}

Which does exactly the same, but introduce less noise because the List interface easier to understand.

Answer 3

When calling oddOne it will get

• the first number
• remove the number
• add it to the result of oddOne (with the number removed)

this repeats till empty whne oddOne return 11

so we end up with

1 + (3 + (5 + (7 + (9 + 11)))) = 36

actually the order will e all jumbled up as it is a hashmap but this has no influence on adding numbers

Answer 4

You're making recursive calls, removing one element from the map per call.

You could start out with num == 1 (a map is unordered) and you remove this from your map. Then you do the recursive call, which gives you num == 3. This continues until your map is empty, which results in 1 + 3 + 5 + 7 + 9, and an additional 11 for your empty map.

Take a look at recursion: http://en.wikipedia.org/wiki/Recursion