[Tutor] A recursion question

[Christian Witts]

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
//
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20111118/24894036/attachment.html>