[Tutor] Understanding error in recursive function

[Martin A. Brown]

Greetings Tom,

>As a test I am trying to write a function that returns the sum of 
>values 

Given the code you pasted, I think you mean 'count' of values, 
right?  I'll assume that below, because it is a tricky thing to sum 
some strings.

>attached to one key in a dictionary. I am wondering why the 
>code that I wrote is returning:


>"maximum recursion depth exceeded "
>Here is the code:

Recursion is a great tool, and quite powerful.  (Though you may not 
need it for this problem.)

>animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}
>
>x = animals['a']
>
>def howMany(aDict):
>      count = 0
>      for value in howMany(aDict):
>           count += 1
>      return count
>
>howMany(x)

>Just wondering why I would be getting that error.

I will show you how I would change the howMany function so that it 
prints (to STDERR) its argument(s).  This is always a useful 
diagnostic or debugging feature.  Even after many years, I still 
grab frequently for printing variable contents or logging them.

N.B.  I'm going to assume you are using Python3.

  import sys
  def howMany(aDict):
        print('%r' % (aDict,), file=sys.stderr)
        count = 0
        for value in howMany(aDict):
             count += 1
        return count

This will print out a whole bunch of ['aardvark'], once each time 
the howMany function is called.  Now, Im going to separate my reply 
into one part about recursion and another part about what I think 
you are trying to do. First, it looks like you want to see how many 
animals have names which start with a specific letter.

You start by creating a dictionary that uses an initial letter as 
the key and a list to hold the names of the animals.  Your function 
could probably be as simple as:

  def howMany(aList):
        return len(aList)

Note that the object passed into the howMany function is not a dict, 
so I changed the variable name to aList.  Since I know that you are 
trying to learn recursion, then, we could try to use a recursion 
solution to your question, rather than use len(aList).  It is 
important to recognize that the next step is not efficient use of 
CPU nor memory, but it should help you play with recursion.

So, now, I'll mention a thing or two about recursion and then I'll 
return to your problem about counting the number of animals in each 
list, where there's a dictionary key for the initial letter of the 
name we give to each type of animal.

One of the most important parts of recursion is defining the 
termination condition for the recursion.  When does the recursion 
stop?  When did we reach the end of the list?

One other important piece of successful recursion is to make sure 
when you are about to call the function again, that you have changed 
something about the variable you are giving to the function.  Your 
problem, in essence is that you were calling the function like this:

  def func(x):
      func(x)

There is no difference between what the function accepts and what 
the function calls.  This, essentially is an infinite loop.  And, 
Python dutifully runs this until it runs out of stack space.  In 
Python this sort of error is called an Exception, and it looks like 
this:

  RuntimeError: maximum recursion depth exceeded

If you look back at your code, you'll also see that Python never 
gets to the line where you set count += 1.

So, to review, here's what a recursive function would need to do in 
order to count the items of the list:

  * have a beginning count of 0
  * return the count as soon as it receives an empty list
  * strip off one item of the list
    AND
  * add one to the count, for each time it calls itself

Here is an inefficient function that demonstrates these principles 
of recursion:

  def howMany(l, count=0):
      if not l:  # -- termination condition, empty list!
          return count
      return howMany(l[1:], count+1)

The problems with this list include that it will fail if the lists 
are long. For example, I was able to determine that on my box, I can 
only handle 988 calls to the same function before triggering the 
maxmimum recursion depth exceeded error.

Given that your question was recursion, I chose to focus on that, 
but I would recommend using the simplest tool for the job, and in 
this case that would be the builtin function called 'len'.

But, this is a great place to ask the question you asked.

Best of luck and I hope you are enjoying Python,

-Martin

-- 
Martin A. Brown
http://linux-ip.net/