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.

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

x

First we define the base case, so that

The recursive case is:

Start testing a recursive function with the simplest examples:

1

1

1

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

exponentiation[1,-1]

Trace shows the exponentiation hitting the base case and stopping.

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

To compute 2

{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}

1024

1267650600228229401496703205376

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

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

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

3011

{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.

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!

Out[593]= 2

Now we may safely compute the factorial of larger numbers:

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

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

*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:

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

x

^{n }= 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

^{2}, the function calls itself to computer 2^{2-1}i.e. 2^{1}, which in turn calls itself to compute 2^{0}, 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.

## No comments:

## Post a Comment