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)

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

## Post a Comment