[Blindmath] Bases, exponents, and recursion
P. McDermott-Wells
pmw at mega-data.com
Wed Sep 11 14:11:29 UTC 2013
Thanks! I am a university instructor (math, CS and IT courses) so this is a
topic that I have to explain on a regular basis.
-----Original Message-----
From: I. C. Bray [mailto:i.c.bray at win.net]
Sent: Tuesday, September 10, 2013 12:01 PM
To: Blind Math list for those interested in mathematics
Subject: Re: [Blindmath] Bases, exponents, and recursion
Impressive!
I have never heard recursion, and power example discussed so concisely!
Well Done!
Ian
----- Original Message -----
From: "P. McDermott-Wells" <pmw at mega-data.com>
To: "'Blind Math list for those interested in mathematics'"
<blindmath at nfbnet.org>
Sent: Tuesday, September 10, 2013 11:39 AM
Subject: Re: [Blindmath] Bases, exponents, and recursion
: 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
:
:
:
:
: _______________________________________________
: 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/i.c.bray%40win.net
More information about the BlindMath
mailing list