Skip to main content

Recursion in Python

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

It is legal for one function to call another, and you have seen several examples of that. It is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

For example, look at the following function:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)

A call to this function countdown(5) will print
5
4
3
2
1
Blastoff!

Advantages of recursion
Recursive functions make the code look clean and elegant.
A complex task can be broken down into simpler sub-problems using recursion.
Sequence generation is easier with recursion than using some nested iteration.

Disadvantages of recursion
Sometimes the logic behind recursion is hard to follow through.
Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
Recursive functions are hard to debug.

Infinite recursion
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, and it is generally not considered a good idea. Here is a minimal program with an infinite recursion:
def recurse():
recurse()
In most programming environments, a program with infinite recursion does not really run forever. Python reports an error message when the maximum recursion depth is reached:

sample programs using recursion
Print the factorial of a number using recursion( university question)
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)

n=input('Enter n')
x=fact(n)
print "factorial of ..",n ," ..is.. ",x
Program to print n’th Fibonacci number ( university question)
def fib(n):
   if n <= 1:
         return n
   else:
         return fib(n-1) + fib(n-2)
       
n=input('Enter n…')
x=fib(n)
print n,"th Fibonacci number…",x

Program to find sum of the digits of a number(university question)
def sumd(n):
     if n == 0:
        return 0
     else:        
        return n%10 + sumd(n/10) 
n=input('Enter n')
s=sumd(n)
print "sumof the digits of  ..",n ," ..is.. ",s
Program to find decimal to binary using recursion
def decb(n):
    if n==0:
        return 0
    else:
        return n%2 + 10* decb(n/2)
n=input('Enter n')
b=decb(n)
print "The binary equivalent of  ..",n ," ..is.. ",b

Program to find sum of n natural numbers using recursion
def sum(n):
     if n ==0:
       return 0
     else:
       return n + sum(n-1)

n=input('Enter n')
s=sum(n)
print "The sum of natural numbers up to ...",n ," ..is.. ",s
Program to find nPr using a recursive factorial function ( university question)
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)
n=input('Enter n')
r=input('Enter r')
print "nPr=", fact(n)/fact(n-r)

Do the following programs in the lab
1.Print the factorial of a number.(university question)
2.Find nCr using a recursive factorial function.(university question)
3.Find the sum of the digits of a number.( university question)
4.Generate n’th Fibonacci number. ( university question)
5.Generate the Fibonacci series.
6.Convert a decimal number into octal using recursion.
7.Convert the decimal number into binary using recursion.
8.Sum of n natural numbers using recursion.(university question)
9.Write a program to compute nPr.Use a recursive function fact() to find the factorial.(University Question)

Comments

Popular posts from this blog

Strings in Python

Strings are compound data type made of sequence of characters. Hence from the string, the individual charters can also be directly accessed. Strings are created by using single quotes or double quotes or triple quotes.
Example: >>>s1="Python Programming" >>>s2='Python Programs' >>>s3="""Python is a powerful Programming language"""
This will create a string object s1, s2 and s3 using different forms.
Individual characters can be accessed using different subscripts( +ve or –ve) with the string object.
Example >>>s="Python" >>>s[0] ‘P’ >>>s[2] ‘t’ >>>s[5] ‘n’ >>>s[-1] ‘n’ >>>s[-3] ‘h’ >>>s[-6] ‘P’
We can also slice a string. Segment of a string is called a slice.
>>>s[1:3] ‘yt’
If the first index is not mentioned, the slicing will start from 0. >>>s[:3] ‘Pyt’
>>>s[2:6] ‘thon’
If the last index is not mentioned, the slicing will go till the end o…

Files in Python , Exception handling

While a program is running, its data is in main memory. When the program ends, or the computer shuts down, data in memory disappears. To store data permanently, you have to put it in a file. Files are usually stored on a secondary storage device(hard disk, pen drive, DVD,CD etc). When there are a large number of files, they are often organized into directories (also called “folders”). Each file is identified by a unique name, or a combination of a file name and a directory name. By reading and writing files, programs can exchange information with each other and generate printable formats like PDF. Working with files is a lot like working with books. To use a book, you have to open it. When you’re done, you have to close it. While the book is open, you can either write in it or read from it. In either case, you know where you are in the book. Most of the time, you read the whole book in its natural order, but you can also skip around. All of this applies to files as well. To open a fil…

Classes and Objects in Python

Python is an object-oriented programming language, which means that it provides features that support object-oriented programming. The basic components of object oriented programming are classes and objects. A Class is a blue print to create an object. It provides the definition of basic attributes and functions of objects. Object is a running instance of the class having the identity(name), properties( values) and behaviors(functions). The Object oriented program thus consist of object definitions (classes) and most of the computations and functions are mentioned as operations on the object. Each object definition corresponds to some object or concept in the real world, and the functions that operate on these object correspond to the ways real-world objects interact. We have learned objects of string, list, tuple etc…and used the properties and functionalities of these objects which are built into the Python. Now we are going to create our own(user defined) objects. The class provides basic…