[Tutor] -Recursive Functions (fwd)

[Danny Yoo]

> def stringToNum(aString):
>    (i have to put a condition over here .)
>
>       if myString[n-1].isdigit():
>          sum=sum+int(myString[n-1])
>         n=n+1
>    print sum


Has your instructor given examples of doing recursion across string
sequences yet?  When we do recursion across a sequence, we often take care
of two particular situations:

    1.  How do we deal with the "empty" or null sequence?
    2.  How do we deal with the nonempty sequence?

For example, say that we're trying to write a function that can figure out
how long a string is.  (Pretend that we don't have the len() function
handy for the purposes of this exercise).  How can we approach a problem
like this?


One thing to see is that the length of the empty string is zero, so we can
code for this:

###
def length(s):
    "Returns the length of sequence s."
    if s == "": return 0
###


That was easy.  And this handles empty strings perfectly well.

###
>>> length("")
0
###


The problem, of course, is that it can't handle much else.

###
>>> length("hello")
>>>
###


So how to we handle strings that aren't empty?  Well, we can lop off the
first character of any string by doing a slice:

###
>>> msg = "Hello"
>>> msg[1:]
'ello'
###

How does this string chopping help, though?  It helps because the length
of the word "Hello" is just one more than the length of the word "ello".
More formally:

   length("hello")  equals  1 + length("ello")

Does this get us anywhere?  Yes, because we can apply the chopping
technique again: the length of "ello" is just 1 + the length of "llo".
And the length of "llo" is just 1 + the length of "lo"...

So if our length() function can handle strings of length 0, and if we can
teach it how to handle nonempty strings, then it should be able to handle
all strings.  The part that's "recursive" about the length function is
that we can write it in terms of a small version of the problem:

    length("some string") = 1 + length("ome string")

    "big problem" can be reduced to trivial solution,
                            combined with solution to slightly easier
                            problem.

Does this make sense so far?  Try writing the length() function and see if
it works for you; you'll be better equipped to handle your original
problem once you can do length().


Good luck to you.