admin
Admin
Admin
| Beiträge: 81 |  |
|
Rekursive Programmierung LotusScript - 22/07/2009 22:10
http://www.dominopower.com/issues/issue200003/recursion001.html
Using recursion in LotusScript
By Greg White
LotusScript is a powerful programming language that gives developers the ability to utilize advanced programming techniques. One of these techniques is recursion. Many developers hesitate to use recursion, preferring to use techniques with which they're already familiar. But using recursive functions can greatly simplify your code, if you implement them correctly.
What is recursion?
Simply defined, a recursive function is one that calls itself. While that definition may be simple, writing a recursive function for the first time can be difficult because it requires a different method of thinking.
Most functions are coded in a fairly straightforward fashion -- you progress from point A, to point B, and end at point C. You may have loops and If Then statements, but you can easily visualize the function in a linear fashion. Recursive functions, however, take an inside-out approach to arriving at an answer. Consider the recursive function below, which calculates the factorial of a number. The factorial of a number is arrived at by multiplying it by all smaller integers. So, the factorial of 3 (denoted as 3!) is equal to 3 * 2 * 1, or 6.
Function factorial (i as integer) as long
If i = 1 then
Factorial = 1
Else
Factorial = i * Factorial(i -1)
End If
End Function
Stepping through a recursive function
Let's step through this function to see how recursion works. We'll assume that you've called the factorial function with a value of 3 as the integer parameter.
You can easily see that since 3 is not equal to 1, the line of code you're concerned with here is:
Factorial = i * Factorial(i - 1)
In English, this line would roughly translate into "The factorial of 3 is equal to 3 times the factorial of 2." So, in other words, the factorial of 3 is equal to 3 times some as of yet unknown value.
Let's figure out that unknown value. If you were to call the factorial function with a value of 2 (which is exactly what this function is doing), you'd see that the factorial of 2 is equal to 2 times the factorial of 1.
You're almost there! Call the factorial function with a value of 1, and the answer is simple: The factorial of 1 is 1. Now what?
Let's take a look at the results we've come up with so far:
3! = 3 * 2!
2! = 2 * 1!
1! = 1
Working from the bottom up, you can easily see that the factorial of 3, or 3!, is equal to 6.
Using recursion in LotusScript (continued)
The elements of a recursive function
You can see how recursive functions differ from ordinary functions. A recursive function simply breaks down a larger problem into smaller problems until you arrive at a simple answer. Once that simple answer has been attained, the recursive function works its way backward to figure out the ultimate answer.
Let's look at one of those lines of code again:
Factorial = 1
This is what I call the end case (sometimes referred to as the base case). The end case is the end of the line for a recursive function. The problem is now so simple that it can be directly solved. All recursive functions have an end case.
Let's look at the other relevant line of code:
Factorial = i * Factorial(i - 1)
This is what's known as the recursive case. If the problem's too difficult to solve, we break it down into a simpler problem by making a recursive call. All recursive functions have a recursive case.
Now that we know the elements of a recursive function, let's put it all together. A recursive function asks a simple question -- can the problem at hand be solved directly? If so, we apply the end case. If not, we need to break the problem down further, so we apply the recursive case.
While writing a recursive function, I often have to remind myself of the simplicity of the concept. It can be easy to get so bogged down in the details that you find yourself reverting back to writing code in a non-recursive manner. In this case, calculating factorials is fairly easy. Almost all recursive functions are more difficult. Next, we'll look at an example that's slightly more difficult, but much more useful.
Duplicating @ReplaceSubstring in LotusScript
While knowing how to calculate a factorial may help you on Jeopardy!, it doesn't come in handy too often when designing applications. Let's try writing something we can use.
Like many Domino developers, I often rewrite formula language functions in LotusScript, both for ease of use and to tweak the functionality to my liking. The @ReplaceSubstring function is a perfect candidate for translation into recursive LotusScript because we can easily think of it in a recursive manner.
Let's say you want to replace all of the back slashes in a string with forward slashes (something that happens quite often when dealing with URLs). If you were to do this manually, you'd probably use a simple method: search for a back slash, and if you found one, you'd replace it with a forward slash and continue your search (the recursive case). If there were no more back slashes, you'd know the string was fine the way it stood (the end case).
Let's dive right in to some code:
Function ReplaceSubstring(fullstring As String, replace As String, replacewith As String) As String
Dim lefttext As String
Dim righttext As String
Dim fulltext As String
If Not Instr(fullstring, replace) = 0 Then
lefttext = Left(fullstring, Instr(fullstring, replace)-1)
righttext = Right(fullstring, Len(fullstring) - (Instr(fullstring, replace) - 1 +_
Len(replace)))
fulltext = lefttext + replacewith + righttext
ReplaceSubstring = ReplaceSubstring(fulltext, replace, replacewith)
Else
ReplaceSubstring = fullstring
End If
End Function
Using recursion in LotusScript (continued)
It's a little more complicated than our factorial example, but there are only six lines of code that require any real thought. Let's look at that If statement:
If Not Instr(currstring, replace) = 0 Then
The If statement is where we determine whether or not we've arrived at the end case. Are there any more back slashes present? If so, we launch into the recursive case:
lefttext = Left(currstring, Instr(currstring, replace)-1)
righttext = Right(currstring, Len(currstring) - (Instr(currstring, replace) - 1 + Len(replace)))
fulltext = lefttext + replacewith + righttext
replacesubstring = replacesubstring(fulltext, replace, replacewith)
The first three lines merely reassemble the string. Everything to the left of the text we want to replace is added to the text we want to replace it with. This string is then added to everything to the right. (If we were trying to replace back slashes with forward slashes in "DemoTestDB.nsf", we'd add "Demo" to "/" and then add that to "TestDB.nsf".)
The fourth line in the recursive case is what truly makes this function recursive. We take the string we've just reassembled and check for more backslashes by recursively calling the ReplaceSubstring function.
The remainder of the important code consists entirely of:
replacesubstring = currstring
This is our end case, where we've finally reduced the problem to a point where it can be easily solved.
Drawbacks to using recursion
While recursion can be a powerful tool, that power does come with drawbacks. The first drawback is that it takes some practice before you can start slamming out recursive code. If you're in a hurry to meet a deadline, you'll almost certainly use the Evaluate statement in LotusScript before you'd attempt to rewrite @ReplaceSubstring as a recursive function.
Another drawback is that recursive code may confuse those who aren't already familiar with recursion. Most Domino developers can muddle through someone else's LotusScript without too many problems (especially if it's well commented!). But looking at someone else's recursive code for the first time can be quite a trial.
Perhaps the biggest drawback to using recursion is the limit that Lotus Notes imposes on recursive functions. If your elegantly written recursive function needs to call itself too many times, you'll receive an "Out of Stack Space" error. This is because Lotus Notes has a 32K limit on the amount of information it stores in the stack for recursive functions. In other words, Lotus Notes won't be able to keep track of all of the temporary variables your function is using!
The first two drawbacks can be easily overcome, but that 32K-stack limit can be a real problem. Luckily, you can usually give yourself a little more stack space to play with by making fewer recursive calls. For instance, if we were to check for two back slash characters each time through our ReplaceSubstring function, we'd cut the number of recursive calls in half.
Using recursion in LotusScript (continued)
By lowering the number of recursive calls your function has to make, you can usually ensure that your function will work in the vast majority of cases. And, of course, you should test your function thoroughly to determine exactly what the limits are.
Summary
A working knowledge of recursion can be extremely useful when you run across a situation that calls for it. By thinking it through and implementing recursion intelligently, you can add real power to your applications.
Bulk reprints
Bulk reprints of this article (in quantities of 100 or more) are available for a fee from Reprint Services, a ZATZ business partner. Contact them at reprints@zatz.com or by calling 1-800-217-7874.
Greg White has been developing in Lotus Notes and Domino for five years. He can be reached via e-mail at GregSWhite@yahoo.com.
|
Forum 
LotusScript Poster Part 1 (535)