[Tutor] recursive function example

[Alan Gauld]

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!

> 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()

> 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.

> '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.

> When 'b' == 0 (zero) the 'if' condition is escaped.

By escaped you mean the functions returns zero.

> 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

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
3	1			3+0=3
3	2			3+3=6

Work your way through it line by line.

HTH
-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.flickr.com/photos/alangauldphotos