[Tutor] recursive function example

[ugajin at talktalk.net]

-----Original Message-----
From: Alan Gauld <alan.gauld at btinternet.com>
To: tutor at python.org
Sent: Wed, 11 Dec 2013 0:29
Subject: Re: [Tutor] recursive function example


On 10/12/13 14:48, ugajin at talktalk.net wrote: 
 
>> Here is original code: 
>> def mult(a, b): 
>>      if b == 0: 
>>          return 0 
>>      rest = mult(a, b - 1) 
>>      value = a + rest 
>>      return value 
>> print "3 * 2 = ", mult(3, 2) 
>> 
>> I see how python outputs the string "mult(3,2)" before running the 
>> function, 
 
>No it doesn't. 
>It outputs the string "3 * 2 - " before running the function! 
 
Yes, my mistake.

>> and then adds the return value to the output, 
 
>Again no. It adds the first parameter to the return value of the recursive call to mult() 
 

I meant that the printed output is in two parts; the string and the return value. 
The function call is made part way through outputting/executing the print command.


>> and I see how the 'if' condition is met, 
 
>> but I do not see how the variable 'rest' is assigned a value, and a 
>> single value at that. 
 
>Because it calls mult with a new set of arguments (a, b-1) instead of the original (a,b). Each call to mult calls mult with a new (a, b-1) until eventually b is equal to >zero and the if test returns zero. 

Again, I am not making myself clear.


>> 'rest' must have a value of 3 (for this example) for the function to 
>> return the correct value, and 'rest' must be assigned the value 
>> of '3' but when, prior, to b == 0? 
 
>No after b=0. the first return from mult is the b-0 case of zero. 
>the next return value will be a + 0 = 3 and the final return value 
>is 3 + 3 which is 6, the correct result. 

Lost me here!, "The first return after b=0 is b-0"?
"a + 0 = 3", yes
I don't see where the second 3 comes from.
 
>> When 'b' == 0 (zero) the 'if' condition is escaped. 
 
>By escaped you mean the functions returns zero. 

Yes.
 
>> In the first iteration, 'rest' is shown with the value '0' (zero), 
>> and in the second it is '3'. 
 
>That's correct, zero + a where a=3. So value = 3 
 
>> 1st, run rest = mult(3, 1) 
>> 2nd. run rest = mult(3, 0) and the 'if' condition is met 
>> Is there some inherent multiplication e.g. 3*1 = 3 and 3*0 = 0, 
 
>There is no multiplication at all. The function works on the basis that multiplication is equivalent to repeated addition. 
>So 3 * 2 = 0+2+2+2 or 0+3+3 

I would have thought so, too. Where is the 0 (zero) in yours from? There is no 0 (zero) in 3 * 2
 
>Try reversing the arguments to see the first case at work... 
 
>> and even if so, it seems backwards? 
 
>It is backwards in so far as the recursion has to drill down 
>to the zero case then unwind back up to the initial case. 
>That's often the case with recursion. 
 
>It often helps to do it on paper rather than using the computer. 
>Try drawing a table like 
 
>a	b	b==0   b-1	return 
>--------------------------------------- 
>3	2	False	1 
>3	1	False	0 
>3	0	True	-1	  0 # I get it this far, but then ask where does -1 and second 0 (zero) come from?
                            Why does the function not stop here? 
                            b is never equal to -1, if b == 0 then b -1 would be equal to -1, but 
                            when b == 0, the if condition is met and return is 0
>3	1			3+0=3    # I don't get this, where does the second 3 and the 0 come from?
>3	2			3+3=6   # or this, it looks like the function has added a + a, but I do not see how, or when it is told to do this.
 
>Work your way through it line by line. 


I do not understand how a function that begins with two parameters can end with one unless an operation is performed on the two parameters to combine them. 
I do not see an instruction in the function mult(a, b) that says to do this
As you say 3 * 2 has to be 3+3 or 2+2+2
Where a = 3 and b = 2 (initial), b = 1 (1st run) and b = 0 (2nd run)
One might add a + b (initial) + b (1st run) + b (2nd run) to return 6, but
there is a slight of hand at work here or something. Where is 'b' stored and where is the instruction to add together these values, if indeed this is what is done?
Thanks, for trying to explain. Perhaps you will try again?

HTH 
-- Alan G 
Author of the Learn to Program web site 
http://www.alan-g.me.uk/ 
http://www.flickr.com/photos/alangauldphotos 
 
_______________________________________________ 
Tutor maillist  -  Tutor at python.org 
To unsubscribe or change subscription options: 
https://mail.python.org/mailman/listinfo/tutor 

 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20131210/9b1051c6/attachment-0001.html>