Recursion Assignment Help

1. Introduction to Recursion

Recursion is a programming tool which provides a powerful yet simple way of approaching numerous problems. Recursive functions can be summarized as a process being performed where one of the step is to "repeat the process". This makes it similar to a loop because of its ability to repeat the same lines of a code.

In programming context, if a piece of code allows you to call a function inside that same function, then it can be labelled as a recursive call of the function. Recursion makes it simpler to express ideas where the result of the recursive call is important to complete a task.

2. A simple example of Recursion

Let us take a simple example of recursive programming involving computing factorials. Factorial of a non-negative integer n denoted as n! can be computed as the product of all positive integers less than or equal to n.

For example,

factorial (5) is the same as 5*4*3*2*1, 
and 
factorial (3) is 3*2*1.

A point to be noted is that the factorial of a number is equal to the product of the same number and the factorial of the number immediately below it.

For example,

factorial (5) is the same as 5 * factorial (4).

The Recursive function in the part of code requires a condition to make it understand when to stop. Since factorials of numbers less than 1 does not make any sense, we stop at the number 1 and return the factorial of 1 (which is 1). Therefore, the factorial function will be as follows:

Number factorial function:

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

The stopping point as discussed previously is called the base case. A base case is the bottom point of a recursive function where the operation is able to return an answer directly without calling the recursive function again. It is mandatory for all the recursive programs to have at least one base case. Otherwise the condition of infinite loop i.e. the program would run forever or until it ran out of memory or stack space.

3. Iteration vs. Recursion

Iteration and Recursion are both key Computer Science concepts that are used in creating numerous algorithms and developing software products.

Read more about Iteration and Recursion here

4. Steps in Recursive programming

Let us go through the following sequence of steps to achieve recursive programming.

1. Often a seed or base initial value is required in order to start with Recursive programming. This can be achieved using a parameter passed to the function. Also, we can accomplish this by providing a gateway function that is non-recursive in nature. This sets up a seed value for the recursive function calculation.
2. Ensure, whether the current value or values being calculated or processed matches the base case. In the cases where it matches the base case, process and return the value.
3. Smaller or simpler sub-problems can be used to represent the answers in a simpler and easy way.
4. Execute or perform the algorithm on the sub-problems designed in the previous step.
5. Formulate the answer by combining the results.
6. Return the results.

5. Recursion in C++

5.1 Calculating Sum of Natural numbers using Recursion

PROGRAM:
#include< iostream>
using namespace std;
int sumofnum(int k);
int main()
{
int k;
cout << "Enter a natural number:";
cin >> k;
cout << "Sum of numbers = " << sumofnum(n);
return 0;
}
Int sumofnum(int k)
{
if(k != 0)
return k + sumofnum(k - 1);
return 0;
}
OUTPUT:
Enter a natural number: 10
Sum of numbers = 55

5.2 Calculation of H.C.F using Recursion

PROGRAM:
#include < iostream>
using namespace std;
int cal_hcf(int k1, int k2);
int main()
{
int k1, k2;
cout << "Enter the value of two natural numbers: ";
cin >> k1 >> k2;
cout << "H.C.F of the entered numbers " << k1 << " & " <<  k2 << " is: " << cal_hcf(k1, k2);
return 0;
}
int cal_hcf(int k1, int k2)
{
if (k2 != 0)
return cal_hcf(k2, k1 % k2);
else 
return k1;
}

OUTPUT:
Enter the value of two natural numbers: 366 60
H.C.F of the entered numbers 366 and 60 is: 6

6. Recursion in JAVA

6.1 Computation of Factorial of a number

PROGRAM:
class Cal_factorial {
int factorial(int k) {
int answer;
if ( k ==1) return 1;
answer = factorial (k-1) * k;
return answer;
}
}
class FactRecursion {
public static void main (String args[]) {
Cal_factorial f =new Cal_factorial();
System.out.println(“Using recursion Factorial of 3 is “ + f.factorial(3));
System.out.println(“Using recursion Factorial of 4 is “ + f.factorial(4));
System.out.println(“Using recursion Factorial of 5 is “ + f.factorial(5));
}
}
OUTPUT:
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120

6.2 Fibonacci Series computation using Recursion

PROGRAM:
public class Recursion {  
static int k1=0,k2=1,k3=0;      
static void Fibo(int ct){      
if(ct>0){      
k3 = k1 + k2;      
k1 = k2;      
k2 = k3;      
System.out.print(" "+k3);     
Fibo(ct-1);      
}      
}        
  
public static void main(String[] args) {  
int ct=15;      
System.out.print(k1+" "+k2); 
Fibo(ct-2);     
}  
}  

OUTPUT:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

7. Advantages and Disadvantages of Recursion

7.1 Advantages

1. Recursion Reduce unnecessary calling of function.
2. Recursion makes program elegant and cleaner.
3. Through Recursion one can Solve problems in easy way while its iterative solution is very big and complex.
4. All algorithms can be defined recursively which makes it easier to visualize and prove.
5. If the speed of the program is vital then, you should avoid using recursion.

7.2 Disadvantages

1. It is very difficult to debug and understand the Recursive solution.
2. In Recursive function the availability of an if statement is necessary somewhere to make the function to return back without executing recursive call, otherwise the function will never return.
3. Recursion is not usually considerable when the program is small and running on a commodity hardware and takes a lot of stack space,
4. More processor time is involved in Recursion.
5. Recursions are generally slower and uses more memory. Instead, a loop can be used.

8. Applications of Recursion

8.1 Real life Applications

1. Mitosis is a process in which a cell divides itself into half to make two identical copies. Mitosis takes place in all types of cells in the human body except few. More importantly, the human body builds itself using recursion algorithm.
2. Recursion is used in one of those lifts with shiny mirror like inside wall. The view is recursive. There is a wall, within a wall and it continues. If you have a mirror in front of another mirror, it is a recursive view. However, this is a recursion without a terminating condition.
3. Fractals is an abstract mathematical concept, but nature often surprisingly employs fractal geometry in the form of naturally occurring frost crystals.
4. While browsing, following a bunch of links and then hitting the 'back' button makes us follow another series of links are all example of recursion.

8.2 Applications in Computer Science

1. The famous Tower of Hanoi game comes under the context of Recursion. The objective of the puzzle is to move the entire stack to another rod. The key solution to this problem is to realize that the problem can be broken into smaller modules until a solution is reached.
2. Recursion can be used to solve computer science problems such as Fibonacci series, factorial, sum of numbers, calculation of highest common factor and so.
3. A linked list is a recursive data structure. It is either empty or consists of a node followed by a linked list which demonstrates the use of recursion.
4. It is possible to solve Sudoku puzzles in reasonable amounts of time, using a simple recursion algorithm.
5. Sorting algorithms in data structures can also be implemented using recursion algorithm.