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

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)

Popular posts from this blog

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…

User Defined Functions in Python

So far we have only seen the functions which come with Python either in some file (module) or in interpreter itself (built in), but it is also possible for programmer to write their own function(s) and are called User Defined Functions. These functions can then be combined to form a module which can then be used in other programs by importing them.
In the context of programming, a function is a named sequence of statements that performs a desired operation. This operation is specified in a function definition.
To define a function keyword def is used. After the keyword comes an identifier i.e.name of the function, followed by parenthesized list of parameters and the colon which ends up the line. Next follows the block of statement(s) that are the part of function. A block is one or more lines of code, grouped together so that they are treated as one big sequence of statements while executing. In Python, statements in a block are written with indentation. Usually, a block begins when a li…

Dictionary In Python

Dictionaries are similar to other compound types except that they can use any immutable type as an index. We can refer to a dictionary as a mapping between a set of indices (which are called keys) and a set of values. Each key maps a value. The association of a key and a value is called a key-value pair. A dictionary is an extremely useful data storage construct for storing and retrieving all key value pairs, where each element is accessed (or indexed) by a unique key. However, dictionary keys are not in sequences.
            Dictionaries are mutable.             Dictionaries are unordered. Items in dictionaries are accessed via keys and not via their position. A dictionary is an associative array (also known as hashes). Any key of the dictionary is associated (or mapped) to a value. The values of a dictionary can be any Python data type. So dictionaries are unordered key-value-pairs.  Dictionaries don't support the sequence operation of the sequence data types like strings, tuples and…