Recursion in Python

                   Recursion is a method where solution to a problem depends on solutions to the

smaller instances of the same problem.One of the most magical thing that a program can do

is to define a function that can call itself. Here is an example:

def countdown(n):

if n==0: return 0

else: return countdown(n-1)+ n

print countdown(3)

When we execute this program ,the output obtained will be 3.

We use a stack diagram to represent the state of a program during function call.Every time

a function gets called , a  new function frame containing local variables and parameters

are created by the Python.The following is the stack diagram for countdown() with n=3.

For a recursive function ,there might be more than one frame on the stack at the same time.

The top of the stack is the frame for __main__.The four countdown frames have different

values for the parameter n.The bottom of the stack ,where n=0,is called the base case.

When the base case is reached ,no more recursive calls are made,hence no more frames

are created.

If a recursion never reaches a base case, it goes on making recursive calls forever, and

the program never terminates.This is known as infinite recursion. Here is an example of

a minimal program with infinite recursion:

 

def recurse():

recurse()

One of the dangers of the code that calls itself is that,it will get into an endless loop and

so there will be a limit to the number of levels deep we can go.In Python that defaults to 1000.

But we can increase the limit of depth using the setrecursionlimit method of the sys class.

The following is an example code that uses the setrecursionlimit method to change the

depth level of the recursion:

import sys

sys.setrecursionlimit(1500)

def countdown(n):

if n==0: return 0

else: return countdown(n-1)+n

print countdown(1200)

When we run the code without that extra line,”RuntimeError: maximum recursion depth

exceeded” we will get the ouput 720600.

Advertisements

About ramyabkrishna

I am Ramya B Krishna doing MCA at GEC Thrissur. I am now in the process of taking a Leap into the world of Linux and hoping to do a few projects as well.

Posted on July 15, 2011, in Uncategorized. Bookmark the permalink. Leave a comment.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: