Lab # 06

Data Structures & Algorithms

Summer 2024

Instructor

Student Name

CMSID

Department

Semester
 Lesson Set Use recursion to solve a
problem
6
Purpose 1. To understand the concepts of recursion.
2. To Implement recursive functions to solve problems.
3. To Visualize recursion with stack diagrams.

Procedure 1. Students should read the Pre-lab Reading assignment before coming to the
lab.
2. Students should complete the Pre-lab Writing assignment before coming to
lab.
3. In the lab, students should complete Labs 3.1 through 3.4 in sequence.
Your instructor will give further instructions as to grading and completion of
the lab.
4. Students should complete the set of lab tasks before the next lab and get
them checked by their lab instructor.

Contents Pre-requisites Completion Page

Time Number

Pre-lab Reading Assignment - 20 min 3

Pre-lab Writing Assignment Pre-lab Reading 10 min 8

Lab 6

Lab 6.1 Pre-lab reading 30 min 3

Recursion

Lab 6.2 Basic concepts - 9

Lab Tasks

2 | Page
 PRE-LAB READING ASSIGNMENT

Recursion The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called a recursive function. Using a
recursive algorithm, certain problems can be solved quite easily.

Recursion is an amazing technique with the help of which we can reduce the
length of our code and make it easier to read and write. A task that can be defined
with its similar subtask, recursion is one of the best solutions for it.

For example; The Factorial of a number.

int fact(int n);

int main()
{
int n;
cout << "Enter a positive integer: ";
cin >> n;
cout << "Factorial of " << n << " = " << fact(n);
return 0;
}
int fact(int n)
{
if(n > 1)
return n * fact(n - 1);
else
return 1;
}

Types of
Direct Recursion: The most typical kind of recursion is direct recursion. A
Recursion
function immediately calls itself when using direct recursion. In other words, a
new set of parameters, often generated from the previous call, are passed to the

3 | Page
 function when it is called. The function keeps calling itself until it encounters a
base case, at which point it stops and starts returning results to the calls that came
before it in the call stack.

Indirect Recursion: A sort of recursion known as indirect recursion occurs when

one function calls another, which then calls the original function. In other words,
the function uses another function to call itself indirectly.

Three Every recursive function should adhere to the three rules of recursion as a
Laws of fundamental rule.
Recursion

1) Base Every recursive function needs to have a base case, or the circumstance in which
Case the recursion ends. The base case, then, is the simplest example that the function
can solve without recursing, to put it another way.

int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}

The base case in this illustration is when num is equal to 0. The function returns
1, which ends the recursion when num is 0.

2) Every recursive function should advance, which implies that with each recursive
Forward call, it should get closer to the base case. In other words, the function must move
Progress closer to the answer.

int sumOfDigits(int num) {

if (num == 0) {
return 0;
} else {
return num % 10 + sumOfDigits(num / 10);
}
}

Every time this function is called recursively, the size of the number is decreased
by eliminating the rightmost digit, coming closer to the base case.

3) Design The design guideline states that every recursive function should solve a problem
Rule by breaking it down into one or more smaller instances of the same problem. In
other words, the function should decompose the issue into more manageable
subproblems.

int fibonacci(int n) {

4 | Page
 if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}

The computation of the nth Fibonacci number in this function is split into two
smaller computations of the (n-1)th and (n-2)nd Fibonacci numbers. Up until the
base case is achieved, this process is repeated.

Properties ● Performing the same operations multiple times with different inputs.

● In every step, we try smaller inputs to make the problem smaller.

● Base condition is needed to stop the recursion otherwise infinite loop will
occur.

Steps The algorithmic steps for implementing recursion in a function are as follows:

1. Define a base case: Identify the simplest case for which the solution is
known or trivial. This is the stopping condition for the recursion, as it
prevents the function from infinitely calling itself.
2. Define a recursive case: Define the problem in terms of smaller
subproblems. Break the problem down into smaller versions of itself, and
call the function recursively to solve each subproblem.
3. Ensure the recursion terminates: Make sure that the recursive function
eventually reaches the base case, and does not enter an infinite loop.
4. Combine the solutions: Combine the solutions of the subproblems to
solve the original problem.

Problems The Tower of Hanoi is a classic problem in computer science that demonstrates
the power of recursion. It consists of three rods and a number of disks of different
sizes, which can slide onto any rod. The puzzle starts with all the disks stacked in
ascending order of size on one rod, the largest disk at the bottom and the smallest
at the top. The objective is to move the entire stack to another rod, following
these rules:

1. Only one disk can be moved at a time: You can only move the top disk of
any stack.

2. A disk can only be placed on top of a larger disk or on an empty rod: You

5 | Page
 cannot place a larger disk on top of a smaller disk.

We have three pegs: A, B, and C. The initial configuration of the disks is as

follows:

The smallest block should be moved to Tower C first. Then, as seen in the
diagram to the right, transfer the center block to Tower B.

By moving the smallest block in Tower B over the middle block, we may begin
to solve the subproblems in this phase, as shown in the above left diagram.

Later, transfer the largest block from Tower A to Tower C and the smallest block
from Tower B to the vacant Tower A, as shown in the above right diagram.

6 | Page
 Then, as illustrated in the above diagram, we combine the solution to arrive at the
ultimate outcome by moving the middle block over the largest block from Tower
B to Tower C and transferring the smallest block from Tower A to Tower C.

Advantag Recursion offers several advantages, such as reducing the number of lines of code
es and and making the code more readable and cleaner. It is particularly useful for
Disadvant solving problems related to data structures and algorithms, such as graphs and
ages trees, where recursive solutions can be more intuitive and elegant. Additionally,
recursion can lead to lower time complexity by eliminating unnecessary function
calls.

However, recursion also has its disadvantages, including higher stack space
consumption and longer processing times. Debugging recursive programs can be
challenging, as errors can be harder to trace compared to iterative solutions.
Despite these drawbacks, recursion remains a crucial technique in programming,
and mastering it is essential for tackling a variety of technical problems often
encountered in interviews and real-world applications.

Learn To gain a deeper understanding of how recursion works, it is essential to study

More various recursive programs in C++. Like Fibonacci series, factorial calculation,
power of a number, reversing a number, and checking for prime numbers. A wide
range of applications and demonstrate the fundamental principles of recursion. By
examining the code and understanding how each function calls itself, students can
better grasp the concept and mechanics of recursion.

7 | Page
 PRELAB WRITING ASSIGNMENT

Fill in the 1. In a recursive function, the condition used to stop the recursion is known as the
blanks
__________.

2. When a function calls itself without any modification to its arguments or state, it

leads to __________ recursion.

3. A recursive function must have at least one __________ case and one or more

recursive cases to prevent infinite recursion.

4. To prevent stack overflow in a deeply recursive function, one can use

__________ recursion, where the recursive call is the last operation in the

function.

5. In some cases, a recursive function can be transformed into an __________

solution to improve performance and avoid stack overflow issues.

8 | Page
 Lab 6.2 Lab Tasks

Write a recursive function in C++ to generate the Fibonacci series up to a given number of terms.

Steps:

1. Define a recursive function that calculates the Fibonacci number for a given position.
2. Use the base case to return the first two Fibonacci numbers (0 and 1).
3. Use the recursive call to compute the sum of the two preceding Fibonacci numbers.
4. Return the Fibonacci number at the specified position and print the series.

Screenshot should be paste here with your Name and CMS in comments tag.

Develop a recursive function in C++ to check if a given number is a prime number.

Steps:
1. Define a recursive function that checks the divisibility of the number by integers up to its
square root.
2. Use the base case to handle small numbers (e.g., numbers less than or equal to 2).
3. Use the recursive call to check the number's divisibility by incrementing the divisor.
4. Return whether the number is prime based on the recursive checks.

Screenshot should be paste here with your Name and CMS in comments tag.

Write a recursive function in C++ to reverse the digits of a given integer.

Steps:
1. Define a recursive function that extracts the last digit and appends it to the reversed
number.
2. Use the base case to stop the recursion when the number becomes zero.
3. Use the recursive call to process the remaining digits of the number.
4. Return the reversed number.

Screenshot should be paste here with your Name and CMS in comments tag.

9 | Page