On 11/18/2011 08:16 AM, 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! :-)
Well, it doesn't count the number of occurrences correctly if the list
is empty. It should get zero, and it gets -1. But for any non-empty
list, nothing ever looks at the -1 value, so it doesn't matter what you
put there. This example diverges from traditional recursion in many
ways, but the chief reason it's not traditional recursion is that it
never uses the return value. within the function.
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 ?
Nowhere. You don't use it, so it gets discarded. if you were going to
use it, your internal calls to the method would look something like:
b = self.slais(lst[1:], x)
and then you'd do something with b.
Further, why do not I get a *TypeError* when I use a simple *return*
statement in the *if* clause?
You would if you actually used the value for arithmetic. But the return
itself would be perfectly legal. it's just a shortcut for 'return None'
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.
Using a class is fine. But you're abusing it. What happens if you try
to sum a second list? (Hint, it gives you a higher number)
Thanks...
If you really want to recursively count, you need a structure which uses
no objects of global lifetime. The intermediate values should be stored
in local variables to that method.
def counter(mylist, val):
if len(mylist == 0):
return 0
prev = counter(mylist[1:], val) #this is actually using the
recursive return value
if mylist[0] == val:
return prev + 1
else:
return prev
Totally untested. And there are certainly many other variants
possible. But the key is you have to do something with the value
returned to you by the lower level function.
--
DaveA
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
