Monday, July 16, 2012
Recursive programming in Stata
* This is one of the basic programming techniques in most programming languages but as far as I can tell it is largely absent from end user Stata programming.
* Imagine some routine which is recursively identical.
* For instance, imagine you would like to calculate a factorial.
* Such as !10 = 10 * 9 * 8 * 7 * 6 *5 * ... 2 * 1
* Interesting Stata (outside of Mata) does not have a basic factorial command but rather only a log factorial
* Easy enough to invert:
di exp(lnfactorial(10))
* Now, let's see if we can't write our own command to calculate a factorial.
cap program drop myfact
program define myfact, rclass
* Let's display some feedback to help the user see what is going on
if "`2'" == "noisy" di "Evaluate `1' - Input `1'"
* If the number to be evaluated is greater than 1 then this program will call itself.
if `1' > 1 {
* myfact calling myfact at a value 1 less than the input value
myfact `=`1'-1' `2'
* After the called myfact command it returns a scalar local called 'current_sum'
* This sum we multiply by the current `1' being evaluated
local current_sum = `1'*r(current_sum)
}
* This is in a sense the starting point of the recursive operation.
* This is only because computers are required 'in general' to evaluate computational problems.
else local current_sum = 1
* Display some more output
if "`2'" == "noisy" di "Evaluate `1' - Output `current_sum'"
* This returns to the top most operation the current sum of the recursive operation.
return scalar current_sum = `current_sum'
end
myfact 10 noisy
return list
* If we want our program to run without feedback
myfact 10
return list
* Of course this is far from the easiest way to program our own factorial calculator.
* For instance:
cap program drop myfact2
program define myfact2, rclass
local current_sum = 1
forv i = 1(1)`1' {
local current_sum=`current_sum'*`i'
}
return scalar current_sum = `current_sum'
end
myfact2 10
return list
* The point is to demonstrate the problem solving technique known as recursive programming.
* There are numerous other applications for this technique.
* Search and sorting algorithms frequently feature recursive algorithms.
* In economics I have used recursive algorithm to solve market equilibrium problems.
* That is when the decision of one actor depends on the choices of other actors simultaneously.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment