Recursion
As per CBSE curriculum
Class 12
Chapter- 06
By-
Neha Tyagi
PGT (CS)
KV 5 Jaipur(II Shift)
Jaipur Region
Neha Tyagi, KV 5 Jaipur II Shift
Recursion - Introduction
“Recursion refers to a programming technique in
which a function calls itself either directly or
indirectly.”
• You must have noticed that in many programs
a function call other function like as-
This is function calling in a
common function.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• If a function calls itself to complete its working,
this is recursion.
Here, A () is calling itself hence it
is recursion.
Here, Sum () is calling itself
hence it is recursion.
Here, Fact () is calling
itself.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• Recursion can be of two types.
– Direct recursion
Here, A () is calling itself hence it
is recursion.
– Indirect recursion
Here A () function is calling B()
and B () function is calling A().
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• Recursion is a technique by which we can
solve big computational problems and this
repeated calling, decreases the complexity of
that problem.
• A recursive procedure has two parts-
1. One or more base case
2. A recursive step
• A recursive code should be able to understand
where to stop recursion.
• Otherwise another loop will be continued and
will show an error.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• If you see the following loop carefully you will
come to know that it will be an infinite loop.
This output will be continued
and hence this is not a sensible
recursive code.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• A correct and sensible recursive code fullfills
following requirements-
• It requires a case which contain recursive
calling. This base case should be reachable to
given parameter / argument. It can be termed
as stoping case which is essential to have.
• It has a recursive case in which function calls
itself.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• Look at the following program -
Base Case
RecursiveCase
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• In this program, execution is going as -
sum_of_n(5)
= 5 + sum_of_n(4)
= 5 + (4 + sum_of_n(3))
= 5 + (4 + (3 + sum_of_n(2)))
= 5 + (4 + (3 + (2 + sum_of_n(1))))
= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3)) As soon as Base Case condition
evaluates to true , it returns 1 and
= 5 + (4 + 6) then function terminates .
= 5 + 10
= 15
Neha Tyagi, KV 5 Jaipur II Shift
How a Recursive Function works?
• In such type of execution, computer sets a
stack which is known as function stack.
• This function stack is a stack of frames.
• At every call of function, new parameter value
gets pushed to the stack. The top of the stack
always contains parameter value of last call.
• When base case evaluates to true, values from
stack needs to pop out one by one and result is
to be returned after calculation.
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• WAP to print a string backwards (using Recursion)
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• WAP to calculate power e.g. an (using Recursion)
Neha Tyagi, KV 5 Jaipur II Shift
Recursive Function
• WAP to print Fibonacci series (using Recursion)
Neha Tyagi, KV 5 Jaipur II Shift
Recursion v/s Iteration
• Recursion trims a solution and solve the problem
mathematically.
• Iteration is a lengthy process which completely
depends on loop.
• Selection of recursion or iteration depends on the
nature of program to be solved.
• Recursive function are slow as compared to iteration.
• Iteration takes more space in memory.
Neha Tyagi, KV 5 Jaipur II Shift
Assignment
1. Write a recursive code to compute and print sum of
squares of n numbers. Value of n is passed as
parameter.
2. Write a recursive code to compute greatest common
devisor of two numbers.
Neha Tyagi, KV 5 Jaipur II Shift
Thank you
Please follow us on our blog
www.pythontrends.wordpress.com
Neha Tyagi, KV 5 Jaipur II Shift
