On 2011/11/18 03:16 PM, Kĩnũthia Mũchane wrote:
Hi,
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
else:
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.
Thanks...
If you pop in some print statements you can see what's happening a bit
easier. You are creating a stack of functions which each return their
values but in a LIFO fashion (Last In, First Out) so you can see the
first return is -1 as you expected to happen when the list is exhausted,
and then each subsequent return is the count which is why you get the
correct return value in the end. Also, why do you think you should get
a TypeError when you `return -1` ?
class Find_Ex():
count = 0
def slais(self, lst, x):
print lst
if len(lst) == 0: #if list is empty just give a -1
print 'Returning -1'
return -1
elif lst[0] == x:
print 'Incrementing Count'
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
else:
print 'Nothing Found'
Find_Ex.slais(self,lst[1:], x)#'x' not found so we move to
the next element
print 'Returning the count'
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)
[4, 4, 4, 5, 6, 7, 4, 7, 7, 4]
Incrementing Count
[4, 4, 5, 6, 7, 4, 7, 7, 4]
Incrementing Count
[4, 5, 6, 7, 4, 7, 7, 4]
Incrementing Count
[5, 6, 7, 4, 7, 7, 4]
Nothing Found
[6, 7, 4, 7, 7, 4]
Nothing Found
[7, 4, 7, 7, 4]
Nothing Found
[4, 7, 7, 4]
Incrementing Count
[7, 7, 4]
Nothing Found
[7, 4]
Nothing Found
[4]
Incrementing Count
[]
Returning -1
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
Returning the count
There are 5 occurrences of 4
--
Christian Witts
Python Developer
//
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
