Question

Unrolling Recursion
The objective of this problem is to simulate recursion using stacks and loops. A synthetic linear recursive procedure for this problem is provided in Code Fragment 1. A recursive function such as the one described is intuitive and easily understandable. On calling myRecursion(input), the execution first checks for the stopping condition. If the stopping condition is not met, then operations inside the recursive call are performed. This can include operations on local variables. The operations inside the function can result in changes to the input. The recursive function is again called using the modified input.

public static int myRecursion(input)
{
   if (recursion stopping condition)
       return value;
   //perform some operations
   ...
   //modified input = make changes to input
   ...
   return myRecursion(modified input)
}
Programming languages internally execute recursion using stacks: To understand the call stack operations performed during execution, let us consider a call to myRecursion(input). Assuming that the recursion stopping criteria is satisfied at a recursive depth of 2, the recursion trace during execution is illustrated in Figure 1.
Figure 1

valuel myRecursion(input0) value mvRecursion( inpu myRecursion(input2) Figure 1

Before calling the first level recursion using input1, the current state of level 0 recursion is pushed onto a stack for future processing. Similarly, before calling the second level recursion using input2, the current state of level 1 recursion is pushed onto the stack for future processing. After execution of second level of recursion, when the stopping condition is satisfied, value is returned. Following which recursion at level 1 continues to execute using the returned value.
The depth of the recursion can sometimes exceed the allowed capacity resulting in "Stack Overflow Error". You can verify this by executing a recursive procedure to compute the sum of first n integers with n = 10000. Our goal in this problem to re-write recursive functions using stacks and while loops. The idea is to simulate the stacked recursive function call. In order to create the user defined stack, we need to first define a class whose object stores the current values of local variables used inside the recursion function (lines 5 through 8 in Code Fragment 1. We also need to store the stage of the current recursion if a recursive call can start more than one recursions (multiple recursions). Thus, we would need only one stack to perform even multiple recursions. A sample snapshot class for the myRecursion function is illustrated in Code Fragment 2.
You should create an object containing the current status values of local variables and push it to the stack before executing the deeper recursive function as discussed in the class. Implement the following problem first in the recursive fashion and then simulate the recursion using stacks and loops:

public class myRecursionSnapShot {
/**
define all local variables as private members
*/
private int stage;

public myRecursionSnapShot() {
}

public myRecursionSnapShot (local variables, int stage) {
//local variable assignments
this.stage = stage;
}
/**
public get functions to obtain the variable of variables
*/

/**
public get functions to obtain the variable of stage
*/

public int getStage() {
return stage;
}
/**
public get functions to assign the variable of variables
*/

/**
public get functions to assign the variable of stage
*/
public void setStage(int stage) {
this.stage = stage;
}
}

1. Sum of first n positive integers.
2. nth number in the Fibonacci series.

Answer 1

1.

public class MyClass {
  
public static int Sum_recursion(int n)
{   
//here is the stopping condition
if(n==0)
{
return n;
}
return n+ Sum_recursion(n-1); //performing changes adding every n and number less than n
  
}
public static void main(String args[]) {
// intializing n
int n=5;
System.out.println(Sum_recursion(n));// calling Function and printing the answer
  
}
}

Ml Result... CPU Time: 0.12 sec(s), Memory: 29728 ki lobyte 15

2.

public class Fibonacci {
  
public static int fib(int n)
{   
//here is the stopping condition
if(n==1 || n==0 )
{
return n;
}
return fib(n-1)+ fib(n-2); //performing changes
  
}
public static void main(String args[]) {
// intializing n
int n=10;
System.out.println(fib(n));// calling function and printing the answer
  
}
}

O Execute Save My Pr Result... CPU Time: 0.12 sec(s), Memory: 30092 kilobyte(s