[Tutor] A recursion question

[Dave Angel]

On 11/19/2011 01:36 AM, Kĩnũthia Mũchane wrote:
> On 11/19/2011 06:03 AM, Asokan Pichai wrote:
>> Another way to do that is to avoid any intermediate variables altogether
>> That may be easier to understand YMMV
>>
>> def counter(mylist, val):
>>      if len(mylist == 0):
>>             return 0
>>      if mylist[0] == val:
>>            return  1 + counter(mylist[1:], val)
>>      else:
>>            return counter(mylist[1:])
> The intermediate variable explanation by Dave actually clinched it for 
> me. Actually, the one I wrote is suspiciously similar to yours ;-). 
> Anyway, thanks Asokan!

FWIW, Asokan's code looks exactly right to me. But I figured the version 
I supplied would make it clearer to you what was happening.

The key to thinking recursively is to figure out exactly what the 
function as a whole does, then figure out how to use exactly such a 
function that  solves a somewhat smaller problem, to solve the whole 
thing.  Since the function as a whole takes in a list, and returns a 
count, that's the way to use the "smaller problem" function.  Both 
Asokan's answer and mine do that.  But his "local variable" is implied 
in the expressions, where I made it explicit so you could see what was 
happening.

If you're familiar with the mathematical proof by induction, this is 
very analogous.

-- 

DaveA