Recursive Programming: The General Principle

Recursion, where a function calls itself, is a fundamental programming method. Recursion is a different way of iterating over a List than using a loop. Recurse is from the Latin recurrere, to run back (I picture a dog retrieving a stick over and over).

There are two principles of writing a recursive function, which is piecewise:

1. Recursive case: Define a function f(n+1) recursively in terms of f(n), or equivalently, f(n) in terms of f(n-1)
2. Base case: Define one or more base cases, which are stopping points for the recursion, so that it doesn't become infinite. 

An elementary example is exponentiation defined this way:

xⁿ = x•x^(n-1)

First we define the base case, so that Mathematica will match it to prevent an infinite recursive loop. Let's just consider positive integers and zero. The base case is any integer raised to the 0^th power equals 1.

exponentiation[x_,0]:=1;

The recursive case is:

exponentiation[x_,n_Integer/;x>0]:=x exponentiation[x,n-1]

Start testing a recursive function with the simplest examples:

exponentiation[0,0]
1

exponentiation[1,0]
1

exponentiation[1,1]
1

Let's make sure the Condition requiring x > 0 works; it does.

exponentiation[1,-1]
exponentiation[1,-1]

Trace shows the exponentiation hitting the base case and stopping.

exponentiation[1,1]//Trace
{exponentiation[1,1],1 exponentiation[1,1-1],{{1-1,0},exponentiation[1,0],1},1 1,1}

To compute 2², the function calls itself to computer 2^2-1 i.e. 2¹, which in turn calls itself to compute 2⁰, which is the base case, 1. Once it has recursed down to the base case, it has a value to substitute in the preceding computations and the recursion 'unwinds.' All recursive functions work this way.

exponentiation[2,2]//Trace
{exponentiation[2,2],2 exponentiation[2,2-1],{{2-1,1},exponentiation[2,1],2 exponentiation[2,1-1],{{1-1,0},exponentiation[2,0],1},2 1,2},2 2,4}

exponentiation[2,10]
1024

exponentiation[2,100]
1267650600228229401496703205376

exponentiation[2,1000]
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Use Block for Large Recursions and Debugging

You may run into the built-in default recursion limit, $RecursionLimit, of 1024 when performing a large recursion.

In[584]:= exponentiation[2,10000]
During evaluation of In[584]:= $RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>
Out[584]= Hold[exponentiation[2,8978-1]]

The safe way to exceed the limit is using Block. Block temporarily changes the value of a Global or System variable. I've suppressed the output here since it is 3,011 digits long, but you can try this safely at home without "//IntegerDigits//Length".

Block[{$RecursionLimit=10050},exponentiation[2,10000]]//IntegerDigits//Length
3011

Mathematica will warn you and stops an infinite recursion with a default recursion limit specified by $RecursionLimit ($IterationLimit is used similarly to stop infinite loops).

{$RecursionLimit,$IterationLimit}
{1024,4096}

Just as you can use Block to temporarily exceed $RecursionLimit, you can use Block to temporarily 'tighten up' $RecursionLimit while writing a recursive function.

In[592]:= Block[{$RecursionLimit=20},factorial@x_:=x*factorial[x-1];factorial@2]
During evaluation of In[592]:= $RecursionLimit::reclim: Recursion depth of 20 exceeded. >>
Out[592]= Hold[factorial[-14-1]]

Always remember to write the base case rule!

In[593]:= Block[{$RecursionLimit=20},factorial@x_:=x*factorial[x-1];factorial@0=1;factorial@2]
Out[593]= 2

Now we may safely compute the factorial of larger numbers:

factorial@200

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

Note all the zeroes at the end. They must be from each time a multiple of 10 is incorporated into the factorial.

Use Packages to Extend Mathematica with Your Own Functions

The framework for extending Mathematica with user-created programs, like library functions in many programming languages, is provided by Packages. 

Generally use Needs to load Packages, not Get. Needs checks to see if a Package is already loaded. But use Get when developing a Package since in that case you want to overwrite the old Package.

Here are the essentials of what you need to know to create Packages of your own. This table steps through an example of a Package. See the line-by-line comments below the table for an explanation of what’s going on in each step.

Line/Comment #	Command	$Context	$ContextPath
1	Times[4, Pi, Power[2, 2]]	Global`	{Global`, System`}
2	area@radius_:= 4*Pi*r^2	Global`	{Global`, System`}
3	BeginPackage@“MyFunctions`”]	MyFunctions`	{MyFunctions` , System`}
4	sphereArea::usage=” sphereArea @radius calculates the area of a sphere of radius r.”	MyFunctions`	{MyFunctions `, System`}
5	Begin@” MyFunctions `Private`”	MyFunctions `Private`	{MyFunctions `, System`}
6	sphereArea@radius_:= 4*Pi*r^2	MyFunctions `Private`	{MyFunctions `, System`}
7	circumference@radius_:= 2*Pi*r	MyFunctions `Private`	{MyFunctions `, System`}
8	End[]	MyFunctions`	{MyFunctions `, System`}
9	EndPackage[]	Global`	{MyFunctions `, Global`,System`}

Comment by Line Number

1. A Mathematica session begins in the Global` Context. All built-in commands reside in the System` Context, which is always on the Context search path stored in $ContextPath) so they can be found no matter what Context you are in. This is the FullForm of a calculation for the surface area of a sphere with radius = 2 using built-in commands Times, Power, and constant Pi.
2. All user-defined symbols, including function names and definitions, reside in the Global` Context and are globally visible, along with built-in commands in the System` Context, unless the user changes the Context. This function is a one-off for calculating the surface area of a sphere.
3. BeginPackage changes the current Context to that of the Package it names, removes all Contexts except System (so built-in commands are accessible) from $ContextPath, and adds the Package name to $ContextPath. BeginPackage removes all Contexts, especially the Global` Context, from $ContextPath so that no globally-visible, previously-defined symbols can foul you up while you develop your Package. Thus you can use the same names while fooling around in Global` that you may end up using in the Package.
4. Usage messages not only return their content when queried with Information@symbol (“?symbol”) but expose the function name for use outside the Package.
5. Symbols in a Private` Context are not visible on the Context search path. But since a usage message declared sphereArea in the public Package Context, it will be found when used in any Context. I suspect while we always see short ‘nicknames’ for symbols, which are the last Context path element, Mathematica always sees the full Context path names, thus is omniscient and ambiguity between identical names is resolved.
6. A function for calculating the surface area of a sphere, like the one-off one in Global`, is more formally defined for repeated use in the future, corresponding to the usage message placed in the public area of the Package (see #4). This definition, in the Private area of the Package, is invisible while any definition in the usage message is visible (e.g. using “?sphereArea”).
7. A private function calculating the circumference of a circle is defined for use within the Package by other functions but not for public export. It cannot be seen outside the Package (unless its full Context path is entered).
8. End[] ) - no argument is used - is the command used to exit a Context, in this case, “MyFunctions`Private`”, which removes the most recent Context entered in $ContextPath and returns us to the previous Context, “MyFunctions`”.
9. EndPackage[]- no argument is used - exits the Package and adds any other Contexts, in this case Global`, to the Context search path. 

Further guidance:

For consistency, make the name of a Package file the same as Context it uses (e.g. here, "MyFunctions.m"). Put the Package file in a directory in $Path (the directory List searched by Mathematica), such as that specified by $UserBaseDirectory, which is the location Mathematica provides for user Packages, or add your Package file’s directory to $Path with PrependTo.

Test your Package with typical parameter values for which it was designed, but also incorrect datatypes and values outside the range for which it was designed,

You can Protect a symbol from alteration by a user with SetAttributes[aSymbol, Protected].

You can Protect a symbol’s definition from being read by a user with SetAttributes[aSymbol, ReadProtected]

Whether in a Notebook or Package (.m) file, cells that you want to be automatically evaluated must be Initialization cells (Cell => Cell Properties => Initialization Cell).

Sources
Programming in Mathematica Course by Roman Maeder, Wolfram Research, Inc.
David Wagner, Power Programming with Mathematica: The Kernel  (New York: McGraw-Hill, 1996. out of print).
StackExchange discussion here.

Memory Management Tools

While Mathematica is designed to manage memory for you, under certain circumstances it can get bogged down, mainly because it keeps a record of all your inputs and outputs with In and Out. So if you're using functions that output a lot of computation, or working with large files, you may notice Mathematica slowing down.

There are a number of ways that you can manage memory in Mathematica. Here is a summary (see also How to Find Memory Used in Computations).

Command	Effect
?Global`*	Shows all Symbols in a non-accessible table
Names@”Global`*”	Returns a List of all Symbols that you can access
Clear@symbol	Clears the value of symbol but leaves its name in memory
Clear@”Global`*”	Clears the values of all Symbols but leaves their names in memory
Remove@symbol	Removes the name symbol and its value from memory
Remove@”Global`*”	Removes all Symbols and their values from memory

If you're going to go as far as removing all Global Symbols, consider starting a new session by entering Quit[] in your Notebook or Quit Kernel → Local under the Evaluation menu.

Beginners hesitate to Quit the kernel, but there's little downside. Even if you haven't saved your Notebooks, the kernel is a separate entity and you can save them.

To automate resuming after quitting the kernel or in general, use Initialization Cells. You can set Initialization in the menu under Cell → Cell Properties or by right-clicking on the cell and selecting Initialization Cell. A little downward tick mark appears in the upper right corner of the cell.

Then when you re-start the kernel by selecting any cell, selecting Evaluation → Evaluate Initialization Cells, or re-open the Notebook, all the Initialization cells are automatically re-Evaluated. In this way you lose very little time by quitting the kernel and re-starting.

Memory-Management Commands to Use Occasionally

Memory currently used by the kernel:

In[157]:= MemoryInUse[]

Out[157]= 135450976

Memory currently used by the front end (all of your open Notebooks):

In[158]:= MemoryInUse@$FrontEnd

Out[158]= 543264768

The maximum memory used by the kernel during your current Mathematica session:

In[159]:= MaxMemoryUsed[]

Out[159]= 137155304

Clear a cell that consumed lots of memory in your session:

Unprotect[Out]; Out[537] =.;
Protect@Out;