[Tutor] Re:-Recursive Functions
Evripides Loizides
loizie@hotmail.com
Sun Jun 1 20:15:03 2003
<html><div style='background-color:'><DIV>
<P># we have the word house we can find the last character like taht:<BR>word = "house"<BR>length = len(word)<BR>lastLetter = word[length - 1]<BR>print lastLetter</P>
<P><BR>>>> e</P>
<P># we have the word "house" we can print all the letters:<BR></P>
<P>word = "house"<BR>index = 0<BR>while index < len(word):<BR> letter = word[index]<BR> print letter,<BR> index = index +1</P>
<P><BR>>>>> h o u s e<BR></P>
<P>i got taht right too but using while loop if u ask me to do it again using recursive function i will not be able.<BR></P></DIV>
<DIV></DIV>>From: Danny Yoo <DYOO@HKN.EECS.BERKELEY.EDU>
<DIV></DIV>>To: Tutor <TUTOR@PYTHON.ORG>
<DIV></DIV>>CC: loizie@hotmail.com
<DIV></DIV>>Subject: Re: [Tutor] -Recursive Functions (fwd)
<DIV></DIV>>Date: Sun, 1 Jun 2003 16:17:36 -0700 (PDT)
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>> > def stringToNum(aString):
<DIV></DIV>> > (i have to put a condition over here .)
<DIV></DIV>> >
<DIV></DIV>> > if myString[n-1].isdigit():
<DIV></DIV>> > sum=sum+int(myString[n-1])
<DIV></DIV>> > n=n+1
<DIV></DIV>> > print sum
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>Has your instructor given examples of doing recursion across string
<DIV></DIV>>sequences yet? When we do recursion across a sequence, we often take care
<DIV></DIV>>of two particular situations:
<DIV></DIV>>
<DIV></DIV>> 1. How do we deal with the "empty" or null sequence?
<DIV></DIV>> 2. How do we deal with the nonempty sequence?
<DIV></DIV>>
<DIV></DIV>>For example, say that we're trying to write a function that can figure out
<DIV></DIV>>how long a string is. (Pretend that we don't have the len() function
<DIV></DIV>>handy for the purposes of this exercise). How can we approach a problem
<DIV></DIV>>like this?
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>One thing to see is that the length of the empty string is zero, so we can
<DIV></DIV>>code for this:
<DIV></DIV>>
<DIV></DIV>>###
<DIV></DIV>>def length(s):
<DIV></DIV>> "Returns the length of sequence s."
<DIV></DIV>> if s == "": return 0
<DIV></DIV>>###
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>That was easy. And this handles empty strings perfectly well.
<DIV></DIV>>
<DIV></DIV>>###
<DIV></DIV>> >>> length("")
<DIV></DIV>>0
<DIV></DIV>>###
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>The problem, of course, is that it can't handle much else.
<DIV></DIV>>
<DIV></DIV>>###
<DIV></DIV>> >>> length("hello")
<DIV></DIV>> >>>
<DIV></DIV>>###
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>So how to we handle strings that aren't empty? Well, we can lop off the
<DIV></DIV>>first character of any string by doing a slice:
<DIV></DIV>>
<DIV></DIV>>###
<DIV></DIV>> >>> msg = "Hello"
<DIV></DIV>> >>> msg[1:]
<DIV></DIV>>'ello'
<DIV></DIV>>###
<DIV></DIV>>
<DIV></DIV>>How does this string chopping help, though? It helps because the length
<DIV></DIV>>of the word "Hello" is just one more than the length of the word "ello".
<DIV></DIV>>More formally:
<DIV></DIV>>
<DIV></DIV>> length("hello") equals 1 + length("ello")
<DIV></DIV>>
<DIV></DIV>>Does this get us anywhere? Yes, because we can apply the chopping
<DIV></DIV>>technique again: the length of "ello" is just 1 + the length of "llo".
<DIV></DIV>>And the length of "llo" is just 1 + the length of "lo"...
<DIV></DIV>>
<DIV></DIV>>So if our length() function can handle strings of length 0, and if we can
<DIV></DIV>>teach it how to handle nonempty strings, then it should be able to handle
<DIV></DIV>>all strings. The part that's "recursive" about the length function is
<DIV></DIV>>that we can write it in terms of a small version of the problem:
<DIV></DIV>>
<DIV></DIV>> length("some string") = 1 + length("ome string")
<DIV></DIV>>
<DIV></DIV>> "big problem" can be reduced to trivial solution,
<DIV></DIV>> combined with solution to slightly easier
<DIV></DIV>> problem.
<DIV></DIV>>
<DIV></DIV>>Does this make sense so far? Try writing the length() function and see if
<DIV></DIV>>it works for you; you'll be better equipped to handle your original
<DIV></DIV>>problem once you can do length().
<DIV></DIV>>
<DIV></DIV>>
<DIV></DIV>>Good luck to you.
<DIV></DIV>>
<DIV></DIV></div><br clear=all><hr>MSN 8 helps <a href="http://g.msn.com/8HMOENUS/2752??PS=">ELIMINATE E-MAIL VIRUSES.</a> Get 2 months FREE*.</html>