[Blindmath] Bases, exponents, and recursion

[Mike Jolls]

Another use for recursion in computer science is searching a binary tree where each node in the tree can point to a left and right sub-node (children).   You use a recursive method to traverse the tree and search for whatever value you want to find.  It's a very fast search and the # of entreis you have to search to get a match (or determine not found) is Log base 2 of N (N=# items in your tree).

 

> From: pmw at mega-data.com
> To: blindmath at nfbnet.org
> Date: Wed, 11 Sep 2013 10:11:29 -0400
> Subject: Re: [Blindmath] Bases, exponents, and recursion
> 
> 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 
> 
> 
> 
> 
> 
> _______________________________________________
> 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/mrspock56%40hotmail.com