in c++
Statement Purpose: Purpose of this Lab is to familiarize the students with the use and power of recursion in C++. They will learn what types of problems can be solved using recursion. They will also be taught what are the merits and demerits of using recursion. The students will learn how to solve the problems like finding factorial of any number, binary search, and merge sort using recursion. Activity Outcomes: After completing the activities given at the end of this lab material, the students will learn how to write simple C++ programs using recursion. They will understand how to use recursion for solving various problems like: Finding sum of all even integers from 1 to any given number Finding and returning the difference of all integers from 1 to any given number. Reversing the elements of an array without using any extra array Displaying an integer number in reverse Theory Review: Recursion The idea of calling one function from another immediately suggests the possibility of a function calling itself. The function-call mechanism in C++ supports this possibility, which is known as recursion. Recursion is a powerful general-purpose programming technique and is the key to numerous critically important computational applications, ranging from combinatorial search and sorting methods that provide basic support for information processing to the Fast Fourier Transformation for signal processing. Types of Problems that can be solved using Recursion Recursion solves large problems by reducing them to smaller problems of the same form. For example, finding factorial of any number, generating Fibonacci sequence, any number raised to the power of any number, binary search, merge sort, Tower of Hanoi etc. Advantages and disadvantages of using Recursion Recursion reduces the size of code for solving a specific problem as compared to its iterative counterpart. Recursion consumes more space in memory than iterative code because of recursive calls which use stack. Recursive code is simpler to write but difficult to understand. Characteristics of a Recursive Method 1. A simple base case which is used to terminate the recursive call. 2. A way of getting our larger problem closer to the base case i.e. a way to chop out part of the larger problem to get a somewhat simpler problem. 3. A recursive call which passes the simpler problem back into the method. Practice Activity with Lab Instructor: Activity: 1. Create a project with the name Recursion 1 Project. 2. Create a main class with the name " SumNums": 3. Write a recursive method "SumNums" inside the SumNums class to find the sum of all integers from first to second integer. For example, if first integer is 5 and second integer is 10, your program should find the sum 5+6+7+8+9+10-45 using recursion. Solution: Before writing the code for this method, let us try to understand this problem. In order to find the sum of integers from first integer 'a' to second integer 'b' using recursion, we use the following procedure: Our recursive method should find the sum from 'a' to 'b'. Suppose first integer 'a' is 5 and second integer 'b' is 10. Then we can divide this larger problem into smaller problem at each step until we reach some base case as follow: SumRec(5, 10) = 10 + 9 + 8 + 7 + 6 + 5 Moving one step closer towards the base case = 10 + SumRec(5,9) Moving one step more towards the base case = 10 + 9+ SumRec(5,8) Moving one step further towards the base case = 10 +9+8+ SumRec(5, 7) Moving one step more towards the base case = 10 + 9 + 8 + 7+ SumRec(5, 6) This is the Base Case. When second integer i.e. 'B' becomes equal to first integer i.e. 'A', the method should return the first integer i.e. 'A' = 10 + 9 + 8 + 7 + 6 + SumRec(5,5) = 10 + 9 + 8 + 7 + 6 + 5 = 45 The code for this program: 5 #include
using namespace std; 8 int sumNums(int a, int b) if(assb) return a; else return b + sumNums(a, b-1); int main() int a,b; cout > a; cout > b; if (a > b) int temp= a; a = b; b.temp: 5 Enter element 2---> 6 Enter element 3---> 7 Enter element 4---> 8 Enter element 5---> 9 Array elements before reversing are [5,6,7,8,9,1 Array elements after reversing are [9,8,7,6,5,] Program ended with exit code: 4. Add a method named RevIntRecursive() in the RevIntRecursive C++ file which displays an integer number in reverse. When you run the program, the output will look like: 12345 What number do you want to reverse the digits of: >reverseDigits(12345) is 54321 Program ended with exit code