[Tutor] A recursion question

Kĩnũthia Mũchane kinuthia.muchane at gmail.com
Fri Nov 18 14:16:47 CET 2011


I am trying to do something which is really stupid :-)
I would like to count the number of occurrences of a certain character 
in a list.
This is more of an exercise in recursion rather than the underlying problem.
I could have used a *for* loop or simply the list *count* method.
Here is the code:

class Find_Ex():

     count = 0
     def slais(self, lst, x):
         if len(lst) == 0: #if list is empty just give a -1
             return -1
         elif lst[0] == x:
             Find_Ex.count += 1 # we have found 'x', increment class 
attribute 'count' by 1
             Find_Ex.slais(self,lst[1:], x)# slice the list and go to 
the next element
             Find_Ex.slais(self,lst[1:], x)#'x' not found so we move to 
the next element
         return Find_Ex.count

s = Find_Ex()
lst = [4,4,4,5,6,7,4,7,7,4]
x = 4
print "There are %d occurrences of %d"%(s.slais(lst, x),x)

It works as advertised but I am convincing myself that it should not! :-)

If the list is empty, which is the base case, s.slais([], 4) returns -1. 
Now using some bush logic, in a non-empty list, in order for the 
recursion to terminate it has to 'hit' the base case and return -1. 
Where does this -1 go ? Further, why do not I get a *TypeError*  when I 
use a simple *return* statement in the *if* clause?

The reason I am asking  that is that I think(wrongly, of course :-)) it 
should be part of the answer and therefore I should be getting an answer 
that is off by one or a *TypeError*!!

And by the way, the reason I used a *class* was that I could not get a 
suitable place in the program to initialise my *count* variable otherwise.



S 1º 8' 24”
E 36º 57' 36”

More information about the Tutor mailing list