Into the depths – infinite recursion

Most languages don’t place any restrictions on how many recursive calls are used, i.e. the depth of recursion. The exception to the rule is Python whose recursion limit is 1000, but it can be changed – needless to say that if you are using recursion, Python is not the best language anyways. In many respects the only thing limiting the use of recursion in languages such as C are limits placed on the system, e.g. the constraints of stack space.

Of course when designing a recursive algorithm, it is a good idea for the recursive function to contain some piece of code that does not depend on recursion, allowing the function to terminate at some point. For example, the following Pascal function contains a line of code that includes no recursive call (on the 3rd line of code). To compute 2.0^4 means calling the function as pow(2.0,4), which makes the following sequence of recursive calls: pow(2.0,3), pow(2.0,2), pow(2.0,1), and pow(2.0,0). The last call terminates at line 3 in the function.

function pow(x:real; n:integer): real;
begin
   if n=0 then pow:=1.0
   else if n>0 then pow:=x*pow(x,n-1)
   else pow:=1/pow(x,-n)
end;

If recursive function has no such terminating clause it is possible that it will go on forever (or at least until resources run out and it crashes). Such a function exhibits what is known as infinite recursion. If the terminating clause of the function pow() were omitted, then the function would become infinitely recursive.

function pow(x:real; n:integer): real;
begin
   if n>0 then pow:=x*pow(x,n-1)
   else pow:=1/pow(x,-n)
end;

Calculating pow(2.0,4), would result in the code eventually crashing. Once the value of n reaches 0, it will continue to invoke the else clause infinitum.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.