Recursion in Python

0 like 0 dislike
583 views

edited
1. What is recursion?
• Its definition
• examples
• Characterisitics
1. Factorial of a number.
2. Fibonacci Sequence .

0 like 0 dislike
by (562 points)
edited

Recursion in Python

• Is one of the most powerful tools in a programming language.
• It is defined as defining anything in turns of itself.
• It is used to solved problems involving iteration(multiple education), in reverse order. Iteration loop statements, helps a programmer to carry out certain task a known times or as long as the desired condition is true.
• If a function refers itself, i. e. call itself, it is said to be a recursive function.
• A function contain either a call statement to itself or a call statement to a second function, which again call back, the original function.
• The first type is known as direct recursion and second type is known as indirect recursion.

For a function to be recursive, it must have the following two properties:

• There must be a base criteria for with the function does not call itself.
• Each time a function calls itself, must be closer to the base criteria.
• The function with this two properties is set to be a well define function.
• When a function calls itself recursively, it is known as recursion.

Types of recursion:

• Recursion are  of  four  types.
• Direct Recursion
• Indirect Recursion
• Tail Recursion
• Non-Tail Recursion

Direct Recursion:

• The recursion in which the function calls itself is called direct recursion. In this type, only one function is involved.

Indirect Recursion:

• The recursion in which two function calls each other is known as indirect recursion.

Tail Recursion:

• A Recursive function is called tail recursive if recursive is the last thing done by function,there is no need  to keep record of previous state.

Non-Tail Recursion:

• A recursive function is called non-tail recursive if recursive is not the last thing done by function ,there is no need to keep record of previous state.

• Recursion provides logical simplicity to an iterative statement .
• It also provide self documentation of recursive programme.
• It made the code look more simpler and effective.
• Complex function can be further split into various smaller sub-problems .

Drawback’s of Recursion

• A recursive solution to a problem is more expensive than a non-recursive solution.
• Recursive solution takes more time and also occupies greater memory space.
• More space is reallocated.
• Debugging is very difficult.

Implementation of recursion

In general, there are two approaches to writing repetitive algorithms. One is with use of iteration. The other uses recursion.

Recursion:

Suppose P is a procedure containing either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure P. Then, P is called recursive procedure. So, program will not continue to run indefinitely, a recursive procedure must have following two properties:

• There must be certain criteria, called base criteria for which procedure does not call itself.
• Each time the procedure does call itself, it must be closer to base criteria.
• A function is said to be recursively defined if function definition refers to itself. It must have following two properties:
• There must be certain arguments , called base values, for which function does not refer to itself.
• Each time function does refer to itself, the argument of function must be closer to base value.

1. Factorial Function:

Product of positive integers from 1 to n, inclusive is called “ n factorial” and is denoted by n! .

n! =1.2.3… .. .. (n-1) (n-1) n

0! =1, 1! =1, 2! =1.2=2, 3! =1.2.3=6, 4! =1.2.3.4=24

n! =n.(n-1)!

Program

#recursive function

def factorial(k):

if( k==1):

return 1

else:

return k*factorial(k-1)

#user input

num=4

if num<0:

print("enter positive number")

elif num==0:

print("factoial of 0 is 1")

else:

print("factorial of ",num," ",end=" ")

print(factorial(num))

Output:

Factorial of 4 =24

1. Fibonacci sequence

The celebrated Fibonacci sequence is 0,1,1,2,3,5,8,13,24,34,55…….

That is f0=0 and f1=1 and each succeding term is sum of two preceding terms, the next two terms of sequence are:

34+55=89 and 55+89=144

Program

#recursive function

def fib(n):

if (n<=1):

return n

else:

return(fib(n-1)+fib(n-2))

n_terms=9

if n_terms <=0:

print("enter positive value")

else:

print("fib sequence:")

for i in range(n_terms):

print fib(i)

Output:

fib sequence:

0

1

1

2

3

5

8

13

21

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.