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 "sum of 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)