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.