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:
if n==0: return 0
else: return countdown(n-1)+ n
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
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:
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:
if n==0: return 0
else: return countdown(n-1)+n
When we run the code without that extra line,”RuntimeError: maximum recursion depth
exceeded” we will get the ouput 720600.