Lab Manual 6 23112021 114139am

LAB 6- Recursion
Objectives:
 This lab is aimed at introducing students to recursion and recursive algorithms.
1 Recursion
Recursion is a programming technique that allows the programmer to express operations in
terms of themselves. In C++, this takes the form of a function that calls itself. A useful way to
think of recursive functions is to imagine them as a process being performed where one of the
instructions is to "repeat the process". This makes it sound very similar to a loop because it
repeats the same code, and in some ways it is similar to looping. On the other hand, recursion
makes it easier to express ideas in which the result of the recursive call is necessary to complete
the task. Of course, it must be possible for the "process" to sometimes be completed without
the recursive call. One simple example is the idea of building a wall that is ten feet high; if I
want to build a ten foot high wall, and then I will first build a 9 foot high wall, and then add an
extra foot of bricks. Conceptually, this is like saying the "build wall" function takes a height and
if that height is greater than one, first calls itself to build a lower wall, and then adds one a foot
of bricks.
A basic code of recursive function is
void recursion() {
recursion(); /* function calls itself */
}
int main() {
recursion();
}
The Recursion has two parts to solve a problem.
 Base Case
 The case for which the solution can be stated non-recursively
 The case for which the answer is explicitly known.
 General Case
 The case for which the solution is expressed in smaller version of itself. Also
known as recursive case.
The C++ programming language supports recursion, i.e., a function to call itself. But while using
recursion, programmers need to be careful to define an exit condition from the function;
otherwise it will go into an infinite loop. Recursive functions are very useful to solve many
mathematical problems, such as calculating the power of a number, calculating the factorial of a
number, generating Fibonacci series, etc.
We will see different examples of recursion.
Example#1:
A program to calculate power of a number using recursion.
Basic syntax:
int power ( int x , int n)
if ( n == 0)
return 1; //base case
else
return x * power(x,n-1) //Recursive Step
}
If we pass x=3 and n=4 then what will be34=?
The each recursive step of the above function would be:
This approach of calculating powers leads to the following recursive definition of the power
function.
 Base Case
 x0 = 1
 Recursive Step would be

 For n> 0 , x n =x∗x n−1
Example#2
A program to compute the factorial of a number using recursion.
The Factorial Function will be:
f (n)=
{ 1 if n=0
n⋅f ( n−1) else
Given a positive integer n, the factorial of n is defined as the product of all integers between 1
and n, including n.
Basic Syntax:
int F(int n)
{
if(n==0)
return 1;
else
return n* F(n-1);
}
If we pass 3 to the function F.
Then each recursive step of the above function would be

Example#3
A program that compute Fibonacci series using recursion.
The sequence 1, 1, 2, 3, 5, 8, 13, 21, 34 … is called the Fibonacci sequence.
The basic definition of the Fibonacci series is
fib (n) = 1 if n = 1 or n = 2
fib (n) = fib (n-2) + fib (n-1) if n > 2
Some example of Fibonacci series are
fib (6) = fib (4) + fib (5)
fib (4) = fib (2) + fib (3)
= 1 + fib (2) + fib (1) = 1 + 1 +1 = 3
fib (5) = fib (3) + fib (4)
= fib (1) + fib (2) + fib (2) + fib (3)
= 1 + 1 + 1 + fib(1) + fib(2) = 5
fib(6) =3+5=8
Basic Syntax:
int fib( int n )

{
if ( n <= 2 ) return 1;
else
return fib(n-1) + fib(n-2);
}
If we pass 5 to fib () function then recursive function would be:
1.1 Limitations of Recursion:

As we all know every algorithm has limitations so the recursive algorithms
limitations are
 It requires more memory to store the automatic variable to solve variable to solve the
memory space i.e., to consume more storage space.
 If properly recursion procedure is not checked, then it will create a problem for the
processing and procedure and procedure run out of memory.
 In some problems, it is a time consuming process and is not efficient.
 It will create indefinite lopping process (non – terminating iteration), if condition not be
applied at the proper.
 When a call is made, it takes time to build a stackframe and push it onto the system
stack
 Conversely, when a return is executed, the stackframe must be popped from the stack
and the local variables reset to their previous values – this also takes time
++++++++++++++++++++

Lab Manual 6 23112021 114139am

Uploaded by

Copyright:

Available Formats

Lab Manual 6 23112021 114139am

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab Manual 6 23112021 114139am

Uploaded by

Copyright:

Available Formats

LAB 6- Recursion

We will see different examples of recursion.

A program to calculate power of a number using recursion.

int power ( int x , int n)

The each recursive step of the above function would be:

 Recursive Step would be

A program to compute the factorial of a number using recursion.

The Factorial Function will be:

If we pass 3 to the function F.

Then each recursive step of the above function would be

A program that compute Fibonacci series using recursion.

The sequence 1, 1, 2, 3, 5, 8, 13, 21, 34 … is called the Fibonacci sequence.

The basic definition of the Fibonacci series is

fib (n) = fib (n-2) + fib (n-1) if n > 2

Some example of Fibonacci series are

fib (6) = fib (4) + fib (5)

fib (4) = fib (2) + fib (3)

= 1 + fib (2) + fib (1) = 1 + 1 +1 = 3

fib (5) = fib (3) + fib (4)

= fib (1) + fib (2) + fib (2) + fib (3)

int fib( int n )

1.1 Limitations of Recursion:

You might also like