[Tutor] Re: recursion question

[Matt Richardson]

On Tue, 2003-12-02 at 16:50, Lee Harr wrote:
> > > >>>def mult(m, n):
> > >         if n == 0:
> > >                 return 0
> > >         if n == 1:
> > >                 return m
> > >         return m + mult(m, n-1)
> > >
> > > >>>mult(5, 5)
> > > 25
> > >
> > > >So I guess what I'm asking is, does the
> > > >function call within the definition of the function spawn another
> > > >instance of the function?  And then if necessary, that second function
> > > >spawn another?
> > > >
> > >
> > >
> > > You got it.
> > >
> > > Just unroll your sample call:
> > >
> > > mult(5, 5)
> > > 5 + mult(5, 4)
> > > 5 + 5 + mult(5, 3)
> > > 5 + 5 + 5 + mult(5, 2)
> > > 5 + 5 + 5 + 5 + mult(5, 1)
> > > 5 + 5 + 5 + 5 + 5
> > >
> > >
> > > (Now, you tell me why mult(5, -2) does not work right  :o)
> > >
> >Thanks, Lee, I think the unrolling you did is making it easier for me to
> >grok this.  Ok, so to answer your question, it sets up the call as
> >
> >mult(5, -2)
> >
> >so when the function hits the final return statement it looks like
> >
> >return 5 + mult(5, -2-1)
> >
> >which sets up a bad loop.  If I'm wrong, correct me before I do any more
> >damage!
> >
> 
> mult(5, -2)
> 5 + mult(5, -3)
> 5 + 5 + mult(5, -4)
> 5 + 5 + 5 + mult(5, -5)
> 5 + 5 + 5 + 5 + mult(5, -6)
> 5 + 5 + 5 + 5 + 5 + mult(5, -7)
> etc, etc, etc.
> 
> Now for extra credit:  Make a mult that can work with negative numbers....
> 
>>> def mult(m, n):
	if n == 0:
		return 0
	if n == 1:
		return m
	if n < 0:
		p = abs(n)
		result = -1 * (m + mult(m, p-1))
		return result
	return m + mult(m, n-1)

>>> mult(5, 2)
10
>>> mult(5, -2)
-10

Probably not the prettiest, but I'm supposed to be working :)

Matt

-- 
Matt Richardson
Instructional Support Technician
Department of Art
California State University San Bernardino
marichar at csusb.edu
(909)880-7727