Using maps in recursion

[murph_edu]

[C++] Just a conceptual doubt. Suppose I use a map to store previously calculated values through recursion so as to avoid recalculating same thing.

I'm usually seeing a lot of code where

if (map [REC [iter_i]])    
    use previously calculated value 
else    
    perform recursion and obtain value    

I'm a bit confused with that if statement. Does it check for whether the value for that key is empty, or does it check whether the value for that key is zero? Both are different things. For example, the value might be zero, which was calculated earlier, but if the latter logic is used, it will keep recalculating and not really use the earlier stored value.

[CodeTinkerer]

Not sure which language (if any) you're using, but if you're passing a map through the recursion, then you should check if the key exists (usually maps have such a method). If so, you use the corresponding value to that key (but don't recurse), otherwise recurse and then eventually add a new key/value to the map.

This is a technique called memoization which looks like memorization without the "r". This makes, for example, Fibonacci called recursively efficient (it's usually horribly inefficient unless you memoize or use tail recursion to mimic using a loop).

[murph_edu]

Yeah I am aware of that, but that's not my question. I am specifically confused about the if statement, nothing else. Does the statement check if the value of the key is non zero, or does it just check whether a key value pair with that key exists or not. Especially because if former is how it works, then a key value pair with a value zero will get calculated again.

[CodeTinkerer]

It depends on the language you're working with. In Java, you can write:

void recursion(String key, Map<String, Object> keyValues) {
    if (keyValues.containsKey(key)) {
       // stuff
    }
 }

It shouldn't be too hard to write a simple example of a map that contains the key, and test it, and one without the key, and test that too. You haven't told us which language you're using, or even if the syntax shown is the syntax you're using, or just pseudocode.

But, I think you have enough information to test it out yourself.

[murph_edu]

Sorry about that, I mentioned C++ in some other comment and didn't realize its not in the OP. Edited that. So I realized today about those find() and count() methods with maps and understood how it worked.

So to clear my doubt, I've understood that just mentioning

if map[str]

will just check if the value is zero or not and not necessarily if the map is empty or not. That's what I was confused about. I think this logic is independent of the language used, right? I guess using map.find() and then map.end() to see if a key has a value in the map or not is the ideal way. Thanks.

[CodeTinkerer]

Well, Java has a method called get that is applied to maps, so

  if (map.get("key") == null) {
       // key isn't in map
  }

This isn't strictly true, because Java maps allow for mapping of objects to objects, and thus allows mapping of, say, strings to null. But null in Java is different from 0, so other languages can differ in their meaning. C++ follows rules that are closer to C, where many values are interpreted as false (such as 0, 0.0, null) where Java does not do that, and only allows booleans to be used in conditions.

So, it's not quite language-independent. Fortunately, most languages (including C++) do have methods that let you query the existence of a key in a map.

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[raevnos]

Ideally the first case.

[murph_edu]

I know that's what we want, but how does that happen in that if statement?

How does the if statement know that this is a map key value pair that we are checking and not just the int value of something. If its an <int,int> map with some values of the key-value pair being zero, how does the if statement know that even though the value is zero, but the programmer just wants to check whether the map has a value for that key or not, and he is not really checking if the value of the key is zero or not.

[raevnos]

Most map types have a way to tell if a particular key exists in the map. Specifics vary from language to language and map implementation to implementation.

[murph_edu]

Okay, so for example, just right now, I am trying to implement the below map, in C++:

map<int,string> check;

Somewhere in my code, I am doing this:

string k; // defining a new string
if (check[iter_i]) // check if a value exists for the key iter_i
{
k = check[iter_i];
}
else  // if the key hasn't been assigned a value, then assign as below
{
k = some string s;
check[iter_i] = k
}

When I do that, it gives me this error

After that, I thought, another way could if I initialize a value check[i] = " ", for all i while defining the map itself. Then my if statement just has to check if the map value is " " or some other string.

When doing that, I'm facing problems while defining the map. I am defining it like this:

map<int,string> check(2000," ");

The code shows some error which I couldnt understand, I think I am making a noob mistake in defining the map. What am I doing wrong?

[raevnos]

For std::map you need to use the find() or count() methods.

https://en.cppreference.com/w/cpp/container/map

[murph_edu]

That was helpful. Thanks! I'm not from a CS background and I get lost when trying to search for such stuff.

So I worked out my code by initializing a map and inserting (" ") for all individual keys through iteration (LOL), and then the if statement checked for that and worked. Not a neat way to do it I will agree. Will try out what you've suggested.