[Tutor] A recursion question

[Dave Angel]

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