[Blindmath] Bases, exponents, and recursion

Tue Sep 10 15:39:23 UTC 2013

Think of recursion as similar to the Russian nesting dolls (they are
actually shell-like dolls with empty centers and open by pulling apart the
top half from the bottom half). You open up the big doll, and inside is a
slightly smaller doll.  You open that second doll, and a slightly smaller
one is inside the second one.  You keep repeating the process until you get
to the tiniest doll. Sometimes there are up to 10 dolls nested this way!

Raising a number to a power can also be done as repeatedly multiplying the
number by itself.  But you can also break it out as was noted in an earlier
message.

2^5 = 2*(2^4)  
Then we replace 2^4 and the original problem becomes this:
2^5 = 2*(2*(2^3))
Then we replace 2^3 and the original problem becomes this:
2^5 = 2*(2*(2*(2^2)))
Then we replace 2^2 and the original problem becomes this:
2^5 = 2*(2*(2*(2*(2^1))))
Then we replace 2^1 with 2, and the original problem becomes this:
2^5 = 2*(2*(2*(2*(2))))

Do you see the nesting that is happening?  We are doing the same process
each time, but simplifying the problem each time by reducing the exponent.

In recursion, your goal is to repeatedly simplify the problem.  And each
time you simplify it, you call the recursion procedure again.  
Example:  2^5 is equivalent to 2*2^4.  And 2^4 is equivalent to 2^3.  And so
on until you get to the last and simplest level, which is 2^1 power. Notice
that what changes each time is the power (exponent) value.  So the
exponent's value will have to be the parameter that is passed to the
recursive procedure.

So here is where the nesting comes in.  You would first call your recursive
procedure (which I will name recur) with the number to be raised to a power
(I will call it num which has a value of 2 in my example) and with original
exponent value(I will call it exp, which has a value of 5 in my example).
Inside the procedure, you will simplify the problem as noted above.  Since
2^5  is equivalent to 2 * 2^4, I will use recursion to calculate the new,
smaller problem of 2^4 by calling recur again, this time passing the same
value of num but a reduced value for exp (in this case, we will reduce it by
1).  So it would look like this:
   Return result = num * recur(num, exp-1)

When that line is executed, the recur procedure is called again, this time
with the values of 2 and 4.  As that runs, it will call recur again, with
the values of 2 and 3. And so on, until you get to 1 and are done.  

Remember from algebra that an expression must be fully evaluated.  The call
to recur in the statement Result = num * recur(num, exp-1) must be evaluated
before we get a value for result. But when we call it with 2 and 4, it calls
itself again.  So none of the calls can get a final result calculated until
we stop this process somewhere.

Recursive procedures must always have a stopping point.  The stopping point
will be the simplest case - when there is no need to go any further.  In
this case, once the exponent value becomes 1, there is no need to call the
recursive procedure again (because 2^0 is always 1 and will not change the
outcome).  So the first thing you must do in a recursive procedure is
determine the stopping point, and make sure that the procedure exits when
the stopping point is met.

In this example, when exp is one, we want to quit.  Since 2^1 = 2, when
recur is called with 2 and 1, we need to return the value of 2, but also
force it to stop. So in this case, we would not call recur again:
	If exp = 1, return num
That would return the value of num (2 in this example) back to the previous
call of recur (which was trying to calculate 2^2 as 2*2^1.  So that now
becomes 2^2 and the statement has been fully evaluated and it can now return
its result to the previous call.  So when we get the result for exp=1 (the
stopping point), we return the smallest doll back to the next larger doll
(the previous call of recur in which this call was nested).  And so on up
the chain.  Ultimately what we have done is this nesting

2^5 = 2*(2*(2*(2*(2))))

Do you see the nesting that is happening?  We are doing the same process
each time, but simplifying the problem each time. 

It is helpful to actually write the code for a recursion such as this and
single step through it to watch how the values change on each nested call.

Recursion can be tough to get your mind to wrap around, but it is one of
those classic CS patterns that you need to know and that you will use. So
don't get frustrated, because it takes some time to master it. Remember this
saying:  To fully understand recursion, you must first understand recursion!

Hope this helps!

On Sep 9, 2013, at 3:25 AM, "Andy B." <sonfire11 at gmail.com> wrote:

> Not sure if I am missing something or not. I sent something to the 
> professor about the assignment.... He is going to have to help me figure
it out.
> 
> 
> -----Original Message-----
> From: Blindmath [mailto:blindmath-bounces at nfbnet.org] On Behalf Of 
> David Tseng
> Sent: Sunday, September 8, 2013 10:40 PM
> To: Blind Math list for those interested in mathematics
> Subject: Re: [Blindmath] Bases, exponents, and recursion
> 
> Andy,
> 
> Are you sure you're not missing a caret (or super script) somewhere?
> 
> A base super exponent (or base^exponent) would make more sense.
> 
> So, the recurrence you're looking for is:
> base^exponent = base * base^(exponent - 1).
> 
> In the context of a computer science course (most likely discrete 
> mathematics), this is meant to get you thinking about the power 
> procedure as a recursive problem.
> 
> HTH,
> David
> 
> 
> On Sun, Sep 8, 2013 at 2:47 PM, Bente Casilenc <bente at casilenc.com> wrote:
> 
>> Andy
>> 
>> After looking at your example I will modify my previous statement. It 
>> looks to me like they want your power function to return the 
>> exponential problem as a multiplication problem. In essence you are 
>> returning a problem that shows the base multiplied by itself so 
>> working off your example you would see power (3,2) and your function 
>> would return 3*3 because 3 to the second power is a shortcut for
> representing 3 times 3 .  Hope this helps.
>> 
>> Bente
>> bente at casilenc.com
>> 
>> Sent from my iPhone
>> 
>> On Sep 8, 2013, at 5:01 PM, "Andy B." <sonfire11 at gmail.com> wrote:
>> 
>>> I have what most likely is a simple problem. However, it is quite 
>>> complicated to figure out. I have the following problem I have to solve:
>>> 
>>> 
>>> 
>>> Create a function called power that takes a base and exponent as the 
>>> arguments, then returns a base exponent. For example, power(2,5)=
>> 2*2*2*2*2.
>>> In the recursion step, use the relationship:
>>> 
>>> Base exponent=base*base exponent-1
>>> 
>>> 
>>> 
>>> I am totally confused. What exactly is a base exponent?
>>> 
>>> 
>>> 
>>> 
>>> 
>>> The sample that I have used 6! As an example, but it doesn't seem to 
>>> help when trying to figure out the power of a number through 
>>> recursion. I
>> assume
>>> the example wants something like this:
>>> 
>>> 
>>> 
>>> Power(2,5)=
>>> 
>>> 
>>> 
>>> Recursion steps:
>>> 
>>> Exponent = result
>>> 
>>> 1=2
>>> 
>>> 2=4
>>> 
>>> 3=8
>>> 
>>> 4=16
>>> 
>>> 5=32
>>> 
>>> 
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Blindmath mailing list
>>> Blindmath at nfbnet.org
>>> http://nfbnet.org/mailman/listinfo/blindmath_nfbnet.org
>>> To unsubscribe, change your list options or get your account info 
>>> for
>> Blindmath:
>> http://nfbnet.org/mailman/options/blindmath_nfbnet.org/bente%40casile
>> n
>> c.com
>> 
>> _______________________________________________
>> Blindmath mailing list
>> Blindmath at nfbnet.org
>> http://nfbnet.org/mailman/listinfo/blindmath_nfbnet.org
>> To unsubscribe, change your list options or get your account info for
>> Blindmath:
>> 
>> http://nfbnet.org/mailman/options/blindmath_nfbnet.org/davidct1209%40
>> g
>> mail.com
> _______________________________________________
> Blindmath mailing list
> Blindmath at nfbnet.org
> http://nfbnet.org/mailman/listinfo/blindmath_nfbnet.org
> To unsubscribe, change your list options or get your account info for
> Blindmath:
> http://nfbnet.org/mailman/options/blindmath_nfbnet.org/sonfire11%40gma
> il.com
> 
> 
> _______________________________________________
> Blindmath mailing list
> Blindmath at nfbnet.org
> http://nfbnet.org/mailman/listinfo/blindmath_nfbnet.org
> To unsubscribe, change your list options or get your account info for
Blindmath:
> http://nfbnet.org/mailman/options/blindmath_nfbnet.org/sabra1023%40gma
> il.com