[Tutor] A recursion question

[Kĩnũthia Mũchane]

On 11/18/2011 06:04 PM, Dave Angel wrote:
> On 11/18/2011 08:16 AM, Kĩnũthia Mũchane wrote:
>> <snip>
>>
> 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)
That is very true, I tried it with a second list and the value was higher.
>> 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
I was trying to come up with something like this but I was totally 
stumped. Now I understand, perfectly.
My heartfelt thanks to you, Dave, and Christian ! ;-)
>
> 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.
>
>
>
>
>


-- 
Kĩnũthia

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