1 of 90

���Python Programming

UNIT – IV

Functions

2 of 90

� Functions

  • A function is a block of organized and reusable program code that performs a single, specific, and well-defined task.

  • Every function encapsulates a set of operations and when called it returns the information to the calling program

*

3 of 90

� Need for Functions

  • Dividing the program into separate well defined functions facilitates
    • Each function can be written and tested separately
    • Simplifies the program development process
    • Understanding, coding, testing multiple separate functions are far easier than doing for one huge function
  • Libraries in Python contains pre-defined and pre-tested functions, programmers can directly use them in their program without worrying about the code details
  • Programmers can make their own functions used in the main program or any other program that requires its functionalities
  • Code reuse is the prominent reason to use functions

*

4 of 90

*

5 of 90

� Function Definition

  • Inputs to the function are called arguments/parameters
  • Calling function may or may not pass parameters to the called function
  • Called function return the result through the return statement
  • Function declaration – declaration statement, identifies the function with the function name, list of arguments it accepts, and the type of data it returns
  • Function definition- consists of function header that identifies the function, followed by the body of the function that contains the executable code for that function

  • Two basic types of functions
    • Built-in functions – comes as a part of python language eg., len(), abs()
    • User defined functions- created by users using def keyword

*

6 of 90

Points to define a function

Function Definition

  • Every Function should start with def keyword

  • Every function should have name(not equal to any keyword)

  • Parameters/Arguments are placed within the parentheses, and are optional

  • Every function name with/without arguments should end with (:)

  • return -> empty/value

  • Multi-value return can be done(tuples)

*

7 of 90

Function Call:

  • Function name , Arguments/parameters – equal to the function definition

*

8 of 90

*

Function to add two numbers

def add( a,b): # function definition

sum= a+b

return sum

a=int(input("enter a number"))

b=int(input("enter a number"))

Result =add(a,b) #function name assigned to a variable

print(“Result is =", Result)

O/P:

enter a number 3

enter a number 4

Result is 7

9 of 90

*

#Example for a function with no argument

def fun():

for i in range(4):

print("welcome")

fun() #function call

O/P:

welcome

welcome

welcome

welcome

10 of 90

*

#mismatch between function parameters

def fun(i,j):

print(i,j)

fun(6) #function call

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 3, in <module>

f(6) #function call

TypeError: f() missing 1 required positional argument: 'j'

11 of 90

*

#mismatch between function parameters

def fun(i):

print(i)

fun(6,5) #function call

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 3, in <module>

fun(6,5) #function call

TypeError: fun() takes 1 positional argument but 2 were given

12 of 90

*

Sample Program

def fun(i):

print(i)

k=10

fun(k) #function call

O/P:

10

13 of 90

*

#arguments may be passed in the form of expression

def fun(i):

print(i)

fun(5*3+7) #function call

O/P:

22

14 of 90

Variable scope and lifetime

  • Scope of the variable

part of the program in which a variable is accessible is called

its scope

  • Lifetime of the variable

duration for which the variable exists is called its lifetime

*

15 of 90

Global and Local Variables

  • Local – within the function where variable have been declared

  • Global – Entire program.
  • GLOBAL VARIABLE : A variable declared outside of the function or in global scope is known as global variable. This means, global variable can be accessed inside or outside of the function.

*

16 of 90

Sample Program

a=20 # Global variable

def display(): # user defined function

print(“Inside user-defined function:”,a)

display() # actual program

print(“Outside user-defined function:”,a)

Output:

Inside user-defined function: 20

Outside user-defined function: 20

*

17 of 90

Sample Program

a=20 # Global variable

def display():

b=30 # user defined function

print(“Inside user-defined function:”,a)

print(“Local variable”,b)

display() # actual program

print(“Outside user-defined function:”,a)

*

18 of 90

Sample Program

a=10 # Global variable

def display():

b=20

print(“Global=”,a)

print(“local=”,b)

display()

c=40 # Local variable

print(“local”,c)

print(“Global”,a)

*

19 of 90

Sample Program

a=10 # Global variable # If local and global variable having same name, First preference to local variables.

c=20

def display():

a=20

print(a)

display()

a=40 # Local variable

print(a)

d=a+c

print(d)

*

20 of 90

*

21 of 90

*

# Difference between local and global variables

num1=10 #global variable

print("global variable num1=", num1)

def fun(num2): #num2 is function parameter

print("inside function-local variable num2=",num2)

num3=30 #num3 is a local variable

print("inside function-local variable num3=",num3)

fun(20) #20 is passed as an argument to function

print("global variable num1=", num1)

print("local variable - outside function num3=", num3)

O/P:

global variable num1= 10

inside function-local variable num2= 20

inside function-local variable num3= 30

global variable num1= 10

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 10, in <module>

print("local variable - outside function num3=", num3)

NameError: name 'num3' is not defined

22 of 90

*

# use of global statement

num1=10 #global variable

print("global variable num1=", num1)

def fun(num2): #num2 is function parameter

print("inside function-local variable num2=",num2)

global num3 #num3 is a global variable

num3=30

print("inside function-global variable num3=",num3)

fun(20) #20 is passed as an argument to function

print("global variable num1=", num1)

print("global variable declared inside function - outside function num3=", num3)

O/P:

global variable num1= 10

inside function-local variable num2= 20

inside function-global variable num3= 30

global variable num1= 10

global variable declared inside function - outside function num3= 30

23 of 90

*

#name clash of local and global variable

num=10 #global variable

print("global variable num=", num)

def fun():

num=30

print("inside function-local variable num=",num)

fun()

print("outside function-global variable num=", num)

O/P:

global variable num= 10

inside function-local variable num= 30

outside function-global variable num= 10

24 of 90

*

#modifying a global variable

var="Good" #global variable

print("global variable var=", var)

def fun():

global var

var="Morning"

print("inside function-global variable var=",var)

fun()

print("outside function-global variable var=", var)

var="Evening"

print("outside function-global variable var=", var)

O/P:

global variable var= Good

inside function-global variable var= Morning

outside function-global variable var= Morning

outside function-global variable var= Evening

25 of 90

*

#access of variables in inner and outer functions

def ofun():

o_var=10

def ifun():

i_var=20

print("outer variable inside inner function o_var=",o_var)

print("inner variable inside inner function i_var=",i_var)

ifun()

print("outer variable outside inner function o_var=",o_var)

print("inner variable outside inner function i_var=",i_var)

ofun()

O/P outer variable inside inner function o_var= 10

inner variable inside inner function i_var= 20

outer variable outside inner function o_var= 10

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 10, in <module>

ofun()

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 9, in ofun

print("inner variable outside inner function i_var=",i_var)

NameError: name 'i_var' is not defined :

26 of 90

*

#name clash variables in case of nested functions

def ofun():

var=10

def ifun():

var=20

print("inside inner function var=",var)

ifun()

print("outside inner function var=",var)

ofun()

O/P:

inside inner function var= 20

outside inner function var= 10

27 of 90

*

#name clash variables in case of nested functions-Global statement also doesn't change

def ofun():

var=10

def ifun():

global var

var=20

print("inside inner function var=",var)

ifun()

print("outside inner function var=",var)

ofun()

O/P:

inside inner function var= 20

outside inner function var= 10

28 of 90

*

#Variable defined in global namespace

def fun():

print(str)

str="welcome to functions in Python"

fun()

O/P:

welcome to functions in Python

29 of 90

*

#local variable with same name as that of global variable

def fun():

print(str) #refers global string str

str="inside function"

print(str) #refers local string str

str="welcome to functions in Python"

fun()

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 6, in <module>

fun()

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 2, in fun

print(str) #refers global string str

UnboundLocalError: local variable 'str' referenced before assignment

30 of 90

*

#use of global statement is required in name clash

def fun():

global str

print(str) #refers global string str

str="inside function"

print(str) #refers local string str

str="welcome to functions in Python"

fun()

O/P:

welcome to functions in Python

inside function

31 of 90

*

#function without a return statement, prints the value None

def fun(str):

print(str)

x=fun("Welcome")

print(x)

print(fun("Hello Hai"))

O/P:

Welcome

None

Hello Hai

None

32 of 90

*

#To find cube of a number

def cube(x):

return(x**3)

k=int(input("enter a number"))

x=cube(k)

print("cube of a number",k, "is", x)

O/P:

enter a number3

cube of a number 3 is 27

33 of 90

*

#statement after return statement will not be executed

def cube(x):

return(x**3)

print("value of x is",x)

k=int(input("enter a number"))

x=cube(k)

print("cube of a number",k, "is", x)

O/P:

enter a number3

cube of a number 3 is 27

34 of 90

# Python program to find the largest number among the three

numbers

   def maximum(a, b, c):

       if (a >= b) and (a >= c):

         largest = a

      elif (b >= a) and (b >= c):

          largest = b

     else:

         largest = c

    return largest

  # Driven code 

a = 10

b = 14

c = 12

print(maximum(a, b, c))

*

35 of 90

More on Defining Functions

  • Required arguments- Required arguments are the arguments passed to a function in correct positional order. Here, the number of arguments in the function call should match exactly with the function definition.
  • Keyword arguments -
  • Default arguments
  • Variable-length arguments

*

36 of 90

������� Required arguments

  • Number and type of arguments should match

def fun():

print("Hello")

fun("Hi")

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 3, in <module>

fun("Hi")

TypeError: fun() takes 0 positional arguments but 1 was given

*

37 of 90

������� � Required arguments

  • Number and type of arguments should match

def fun(str):

print(str)

fun()

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 3, in <module>

fun()

TypeError: fun() missing 1 required positional argument: 'str'

*

38 of 90

������� Required arguments

  • Number and type of arguments should match

def fun(str):

print(str)

fun("Hello")

(or)

def fun(str):

print(str)

str="Hello"

fun(str)

O/P:

Hello

*

39 of 90

������� Keyword arguments

  • Keyword arguments are related to the function calls. When you use keyword arguments in a function call, the caller identifies the arguments by the parameter name.
  • This allows you to skip arguments or place them out of order because the Python interpreter is able to use the keywords provided to match the values with parameters.
  • Values are assigned to the arguments based on their name (keyword)

def fun(str, x):

print("string is",str)

print("x is",x)

fun(x=15,str="Hello")

O/P:

string is Hello

x is 15

*

40 of 90

������� Keyword arguments

  • Values are assigned to the arguments based on their name (keyword)

def fun(str, x):

print("string is",str)

print("x is",x)

fun(x=15,s1="Hello")

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 5, in <module>

fun(x=1.5,s1="Hello")

TypeError: fun() got an unexpected keyword argument 's1'

*

41 of 90

������� Keyword arguments

  • Even the value is assigned, output is not as expected

def fun(str, x, y):

print("string is",str)

print("x is",x)

print("y is",y)

x=10

y=[10,"aaa",12.3]

str="Welcome"

fun(x,y,str)

O/P:

string is 10

x is [10, 'aaa', 12.3]

y is Welcome

*

42 of 90

������� Keyword arguments

  • Even the value is assigned, variable name have to be assigned during function call

def fun(str, x, y):

print("string is",str)

print("x is",x)

print("y is",y)

x=10

y=[10,"aaa",12.3]

str="Welcome"

fun(x=x,y=y,str=str)

O/P:

string is Welcome

x is 10

y is [10, 'aaa', 12.3]

*

43 of 90

������� Keyword arguments

  • Different variable name used for getting input, variable name have to be assigned during function call

def fun(str, x, y):

print("string is",str)

print("x is",x)

print("y is",y)

a=10

b=[10,"aaa",12.3]

c="Welcome"

fun(x=b,y=a,str=c)

O/P:

string is Welcome

x is [10, 'aaa', 12.3]

y is 10

*

44 of 90

������� Default arguments

  • A default argument is an argument that assumes a default value if a value is not provided in the function call for that argument.

def fun(name="aaa", course="BTech"):

print("name is",name)

print("course is",course)

fun(name="xxx",course="BE") #Keyword arguments

fun(name="rrr") #default arguments for course

fun() #default arguments for name and course

O/P:

name is xxx

course is BE

name is rrr

course is BTech

name is aaa

course is BTech

*

45 of 90

������� Default arguments

  • Default arguments must be written after the non-default arguments

def fun(name="aaa", course):

print("name is",name)

print("course is",course)

fun(name="xxx",course="BE") #Keyword arguments

fun(course="BE") #default arguments for name

O/P:

File "<ipython-input-13-c9a72b30d90a>", line 2 def fun(name="aaa", course): ^ SyntaxError: non-default argument follows default argument

*

46 of 90

������� variable-length arguments

  • You may need to process a function for more arguments than you specified while defining the function. These arguments are called variable-length arguments and are not named in the function definition, unlike required and default arguments.
  • An asterisk (*) is placed before the variable name that holds the values of all nonkeyword variable arguments.

  • Make function call with arbitrary or any number of arguments
  • Arbitrary arguments form a tuple before being passed into the function
  • Variable-length arguments should be present in the last in the list of formal parameters
  • Any formal parameters written after the variable-length arguments must be keyword-only arguments

  • Syntax

def functionname([arg1,arg2,….] *var_args_tuple):

function statements

return(expression)

*

47 of 90

variable-length arguments

  • You may need to process a function for more arguments than you specified while defining the function. These arguments are called variable-length arguments and are not named in the function definition, unlike required and default arguments.
  • An asterisk (*) is placed before the variable name that holds the values of all nonkeyword variable arguments.

  • Make function call with arbitrary or any number of arguments
  • Arbitrary arguments form a tuple before being passed into the function
  • Variable-length arguments should be present in the last in the list of formal parameters
  • Any formal parameters written after the variable-length arguments must be keyword-only arguments

  • Syntax

def functionname([arg1,arg2,….] *var_args_tuple):

function statements

return(expression)

*

48 of 90

� �������������Create function with variable length arguments�

def func(*args):

#

# body of the function

#

*

49 of 90

Passing multiple arguments�

def sum(*args):

print(type(args))

print(args)

sum(10, 20)

sum(10, 20, 30)

sum(10, 20, 30, 40)

Output: <class 'tuple'>

(10, 20)

<class 'tuple'>

(10, 20, 30)

<class 'tuple'>

(10, 20, 30, 40)

*

50 of 90

Multiple arguments sum function�

# func

def sum(*args):

result = 0

for arg in args:

result = result + arg

return result

print(sum(10, 20)) # 30

print(sum(10, 20, 30)) # 60

print(sum(10, 20, 30, 40)) # 100

*

51 of 90

variable-length arguments

#program to demonstrate *args in python  

def my_func(*argp):  

    for i in argp:  

#printing each element from the list  

        print(i)  

#passing the parameters in function  

my_func("Let","us","study","Data Science","and","Blockchain")  

  • Output:

Let

us

study

Data Science

and

Blockchain

*

52 of 90

#program to demonstrate *args in python  

def my_func(par1,par2,*argp):  

#displaying the first parameter      

    print("The first parameter is: ",par1)  

#displaying the second parameter  

    print("The second parameter is: ",par2)  

    for i in argp:  

#printing each element from the list  

        print(i)  

#passing the parameters in function  

my_func("Let","us","study","Data Science","and","Blockchain")

Output:  

The first parameter is: Let

The second parameter is: us

study Data Science and Blockchain

*

53 of 90

������� variable-length arguments

def fun(*subj):

    print("\n", "likes to read")

    for i in subj:

        print(i)

    

fun("xxx","C", "JAVA","PYTHON") 

fun("aaa", "C++","PYTHON")             

fun("zzz","PYTHON")

fun("ttt")

O/P

likes to read

xxx

C

JAVA

PYTHON

likes to read

aaa

C++

PYTHON

likes to read

zzz

PYTHON

likes to read

ttt

*

54 of 90

������� variable-length arguments

def fun(name, *subj):

print("\n",name, "likes to read")

for i in subj:

print(i)

fun("xxx","C", "JAVA","PYTHON")

fun("aaa", "C++","PYTHON")

fun("zzz","PYTHON")

fun("ttt")

O/P:

xxx likes to read

C

JAVA

PYTHON

aaa likes to read

C++

PYTHON

zzz

likes to read

PYTHON

ttt likes to read

*

55 of 90

������� variable-length arguments

def fun(name, *subj):

print("\n",name, "likes to read")

for i in subj:

print(i)

name1="xxx"

name2="aaa"

name3="yyy"

name4="www"

s1="C"

s2="JAVA"

s3="PYTHON"

fun(name1,s1,s2,s3)

fun(name2,s2,s1)

fun(name3,s2)

fun(name4)

*

56 of 90

������� variable-length arguments

def fun(name, *subj,str, x):

print("\n",name, "likes to read")

for i in subj:

print(i)

print("in semester",str,"in",x,"days")

name1="xxx"

name2="aaa"

name3="yyy"

name4="www"

s1="C"

s2="JAVA"

s3="PYTHON"

fun(name1,s1,s2,s3,str="VI",x=30)

fun(name2,s2,s1,str="VI",x=30)

fun(name3,s2,str="VI",x=30)

fun(name4,str="VI",x=30)

*

57 of 90

������� variable-length arguments

def fun(name, *subj,str, x):

print("\n",name, "likes to read")

for i in subj:

print(i)

print("in semester",str,"in",x,"days")

name1="xxx"

s1="C"

s2="JAVA"

s3="PYTHON"

str="VI"

x=30

fun(name1,s1,s2,s3,str,x)

O/P:

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun1.py", line 13, in <module>

fun(name1,s1,s2,s3,str,x)

TypeError: fun() missing 2 required keyword-only arguments: 'str' and 'x'

*

58 of 90

������� variable-length arguments

def fun(name, *subj,str, x):

print("\n",name, "likes to read")

for i in subj:

print(i)

print("in semester",str,"in",x,"days")

name1="xxx"

s1="C"

s2="JAVA"

s3="PYTHON"

str="VI"

x=30

fun(name1,s1,s2,s3,str=str,x=x)

O/P:

xxx likes to read

C

JAVA

PYTHON

in semester VI in 30 days

*

59 of 90

Lambda functions or Anonymous Functions

  • In Python, an anonymous function is a function that is defined without a name. While normal functions are defined using the def keyword in Python, anonymous functions are defined using the lambda keyword. Hence, anonymous functions are also called lambda functions.

Syntax of Lambda Function in python

lambda arguments: expression

Lambda functions can have any number of arguments but only one expression. The expression is evaluated and returned. Lambda functions can be used wherever function objects are required.

*

60 of 90

# Program to show the use of lambda functions

double = lambda x: x * 2

print(double(5))

Output:

10

  • In the above program, lambda x: x * 2 is the lambda function. Here x is the argument and x * 2 is the expression that gets evaluated and returned.
  • This function has no name. It returns a function object which is assigned to the identifier double. We can now call it as a normal function. The statement

def double(x):

return x * 2

*

61 of 90

������� Lambda functions or Anonymous Functions

Lambda functions contain only a single line.

sum=lambda x, y : x + y

print(“sum=“,sum(3,5))

lambda x, y : x + y

is same as,

def sum(x,y):

return x+y

*

62 of 90

������� Lambda functions or Anonymous Functions

*

63 of 90

lambda function can access global variable�

c1=100

def sum2(n1,n2):

  global c1

  c1=300

�sum2(34,45)

sum1=lambda a,b:a+b*c1

print(sum1(5,8))

Output:

2405

*

64 of 90

����# lambda function can be passed as �arguments�

sq=lambda a:a*a

cu=lambda b:b*b*b 

def sum1(s1,s2):

  return s1+s2

ans=sum1(sq(5),cu(5))

�print(ans)

  • Output:
  • 150

*

65 of 90

# using lambda functions inside a function�

def test1(a):

   return (lambda a:a*a)(a)

print(test1(10))

Output: 100

(lambda a,b:a+b)(3,4)

print((lambda a,b:a+b)(3,4))

*

66 of 90

# sum of first 10 natural numbers using lambda funcitons with out arguments�

x=lambda:sum(range(1,11))

print(x())

output:

55

# sum of first 10 natural numbers using lambda funcitons 

  • x=lambda n:sum(range(1,n))
  • print(x(11))

*

67 of 90

������� Lambda functions or Anonymous Functions

def small(a,b):

if a < b:

return a

else:

return b

sum=lambda x, y : x+y

diff=lambda x, y : x-y

print("smaller of two operations is",small(sum(-3,-2),diff(-1,2)))

O/P:

smaller of two operations is -5

*

68 of 90

������� Lambda functions or Anonymous Functions

def inc(a):

return (lambda i :i+1)(a)

n=int(input("enter a number"))

print("value of n is",n)

b=inc(n)

print("value of b is",b)

O/P:

enter a number6

value of n is 6

value of b is 7

*

69 of 90

������� Lambda functions or Anonymous Functions

print((lambda i :i*2)(7))

O/P:

14

#passes lambda function as argument to a function

def fun(f,n):

print(f(n))

twice=lambda x:x*2

thrice=lambda x:x*3

fun(twice,4)

fun(thrice,6)

O/P:

8

18

*

70 of 90

������� Lambda functions or Anonymous Functions

# sum of first 10 natural numbers

x=lambda:sum(range(1,11))

print(x())

O/P:

55

#lambda function that calls another lambda function

add=lambda x,y:x+y

mul_and_add=lambda x,y,z:x*add(y,z)

print(mul_and_add(3,4,5))

O/P:

27

*

71 of 90

������� Documentation Strings

  • serve the same purpose as comments
  • designed to explain the function
  • Helps the tools to automatically generate online or printed documentation

  • Syntax

def functionname(parameters);

“function_docstring”

function statements

return[expression]

*

72 of 90

# documentation strings�

def sum1(a,b):

  " sum of two numbers“ #documentation string

  print(sum1.__doc__)

  return (a+b)

sum1(5,8)

*

73 of 90

������� Documentation Strings

def fun():

""“The program just prints the message.

It will display hello world!!! """

print("hello world")

print(fun.__doc__)

fun()

O/P:

the program just prints the message.

it will display hello world!!!

hello world

*

74 of 90

def sum1(a,b):

  ' sum of two numbers‘ #documentation

  print(sum1.__doc__)

 

  return (a+b)

sum1(5,8)

Output:

sum of two numbers

13

*

75 of 90

*

76 of 90

������� Recursive Functions

  • A function that calls itself to solve a smaller version of its task until a final call is made which does not require a call to itself
  • It has two major cases
    • base case –program is simple enough to be solved directly without making any further calls to the same function
    • recursive case-
        • first the problem is divided into simpler sub-parts
        • second the function calls itself with the sub-parts
        • third the result is obtained by combining the solutions of simpler sub-parts

*

77 of 90

������� Factorial of a given number

n! = n * (n-1)!

For example, to find 5!

5 * 4!

4 * 3!

3 * 2!

2 * 1!

Base case

if n=1, result is 1, because 1!=1

Recursive case

fact(n)=n * fact(n-1)

*

78 of 90

������� Factorial of a given number

def fact(n):

if(n==1 or n==0):

return 1

else:

return n*fact(n-1)

n=int(input("enter a number"))

print("The factorial of", n,"is",fact(n))

O/P:

enter a number 5

The factorial of 5 is 120

*

79 of 90

# 1+2+3..�

# sum(5)=5+sum(4)

#sum(4)=4+sum(3)

�def sum(n):

  if(n==0):

    return 0;

  else:

    ans=n+sum(n-1)

    return ans

n=int(input("enter a number"))

sum(n)

*

80 of 90

������� Greatest Common Divisor

Euclid’s algorithm is based on applying repeatedly the equality

gcd(m, n) = gcd(n, m mod n),

For example, gcd(60, 24) can be computed as follows:

gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

Euclid’s algorithm for computing gcd(m, n)

Step 1 If n = 0, return the value of m as the answer and stop; otherwise,

proceed to Step 2.

Step 2 Divide m by n and assign the value of the remainder to r.

Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.

Base case

if m%n == 0, return n

Recursive case

gcd(m, n) = gcd(n, m mod n)

*

81 of 90

������� Greatest Common Divisor

def gcd(a,b):

if(a%b==0):

return b

else:

return gcd(b,a%b)

a=int(input("enter a number:"))

b=int(input("enter a number:"))

print("GCD of", a, b,"is",gcd(a,b))

O/P:

enter a number:62

enter a number:8

GCD of 62 8 is 2

*

82 of 90

������� Finding Exponent

To find xy

For example, 23 can be computed as follows:

23 = 2 * 22

= 2 * 2 * 21

= 2 * 2 * 2 * 20

= 2 * 2* 2*1

= 8

Base case

if y==0, return 1

Recursive case

exp(x,y)= x* exp(xy-1)

*

83 of 90

������� Finding Exponent

def exp(x,y):

if(y==0):

return 1

else:

return x*exp(x,y-1)

x=int(input("enter a number"))

y=int(input("enter a number"))

print(x,"power", y,"is",exp(x,y))

O/P:

enter a number2

enter a number3

2 power 3 is 8

*

84 of 90

������� Fibonacci series

0 1 1 2 3 5 8 13 21 …….

Base case

if n==1, return 0

if n==2, return 1

Recursive case

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

*

85 of 90

������� Fibonacci series

def fib(n):

if(n==1):

return 0

elif(n==2):

return 1

else:

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

n=int(input("enter the number of terms"))

for i in range(1,n+1):

print("Fibonacci(",i,")=",fib(i))

O/P:

enter the number of terms 5

Fibonacci( 1 )= 0

Fibonacci( 2 )= 1

Fibonacci( 3 )= 1

Fibonacci( 4 )= 2

Fibonacci( 5 )= 3

86 of 90

������� Recursion vs Iteration

Recursion

Follows top-down approach to solve a problem

Original problem is divided into smaller sub-problems

Iteration

Follows bottom-up approach to solve a problem

Begins the solution with what is known and then constructs the solution step-by-step

*

87 of 90

������� Pros and Cons

*

88 of 90

������� program to count number of times a recursive function is called

def fun(n, count=1):

if(n==1):

return count

else:

return fun(n-1, count+1)

n=int(input("enter a number"))

print("number of times recursive function was invoked",fun(n))

O/P:

enter a number100

number of times recursive function was invoked 100

89 of 90

������� Infinite Recursion

def fun(n, count=1):

if(n==1):

return count

else:

return fun(n, count+1)

n=int(input("enter a number"))

print("number of times recursive function was invoked",fun(n))

O/P:

enter a number2

Traceback (most recent call last):

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun2.py", line 7, in <module>

print("number of times recursive function was invoked",fun(n))

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun2.py", line 5, in fun

return fun(n, count+1)

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun2.py", line 5, in fun

return fun(n, count+1)

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun2.py", line 5, in fun

return fun(n, count+1)

[Previous line repeated 990 more times]

File "C:/Users/user/AppData/Local/Programs/Python/Python37-32/fun2.py", line 2, in fun

if(n==1):

RecursionError: maximum recursion depth exceeded in comparison

90 of 90

Thank you