Recursion Intro - Eishaaya/GMRDataStructuresTest GitHub Wiki
Recursion is the practice of a function repeatedly calling itself to a achieve a result. This is a completely different process than looping, but, achieves a similar outcome. Recursion is often used to created highly compact code that may run more efficiently or be more intuitive than non-recursive code. A core concept of recursion is that it automatically saves the state of the program at each "iteration". Some of the other basic principles of recursion are iterations and base cases.
A recursive function calls itself repeatedly to do the same process multiple times. In order to return useful information, a recursive function returns a value combined with a function call to itself. However, when a function calls itself it runs into the possibility of infinite recursion. Base cases are the solution to this problem. Base cases prevents this problem by acting as a reference or ending point for the recursion. They are coded to return out of the function, or a single value, and not another function call, therefore preventing more method calls and allowing the stack to empty. In addition, recursion uses the built-in stack to handle each level of calling itself in order to save the values of the previous function call. At some point, (different from loops) this stack will have so many frames, it will give out, resulting in a stack overflow exception.
Here is an example of a non recursive function that returns a factorial of a specified number.
/// <summary>
/// A function that non-recursively calculates factorial numbers
/// </summary>
/// <param name="factorialNumber">the number to finf the factorial for</param>
/// <returns>the total value</returns>
public int nonRecursiveFactorial(int factorialNumber)
{
//Negative Check
if(factorialNumber < 0)
{
throw new InvalidOperationException("No good answer can be found for negative factorials");
}
//Collect Parameter into factorial processing temporary variable
int returnCalculatedFactorial = factorialNumber;
//Loop to calculate factorial
for (int i = 1; i < factorialNumber; i++)
{
returnCalculatedFactorial *= i;
}
//return calculated factorial
return returnCalculatedFactorial;
}Notice how in this example, there is a central for loop which runs the calculation. In fact, one may notice that the for loop is the only part that is calculating anything. We are able to reformulate this into a recursive function below.
/// <summary>
/// A function that recursively calculates factorial numbers
/// </summary>
/// <param name="factorialNumber">the number to find the factorial for</param>
/// <returns>the total value</returns>
public int factorial(int factorialNumber)
{
//Base cases
if(factorialNumber < 0)
{
throw new InvalidOperationException("No good answer can be found for negative factorials");
}
if(factorialNumber == 0)
{
return 0;
}
if(factorialNumber == 1)
{
return 1;
}
//Return the previous value multipled against the current value
return factorial(factorialNumber - 1) * factorialNumber;
}In advanced cases we may need more exit conditions to adjust for the difference in outputs. For example the Fibonacci sequence can be calculated via a recursive function because it is a mathematical rule that can be recursively followed. NOTE: This code is done for an example and not for actually usage (extremely inefficient at high iterations).
/// <summary>
/// A function that recursively returns the fibbonacci sequence
/// </summary>
/// <param name="location">the location of the value to generate</param>
/// <returns>The value at location</returns>
public int fibbonacci(int location)
{
//Base Cases
if(location < 0)
{
throw new NotImplementedException("Negative values for Fibbonacci have not been accounted for.");
}
if(location == 0)
{
return 0;
}
else if(location == 1)
{
return 1;
}
else if(location == 2)
{
return 1;
}
//Return the sum of the value 2 positions ago with the value a position ago
return fibbonacci(location - 2) + fibbonacci(location - 1);
}- Recursively count down from a starting number to an ending number.
- Create a recursive function which takes in an integer array and return the sum of the elements in the array.
- Hint: Use another parameter for index.
- Create a recursive function which reverses a string.
- Hint: Very similar to the recursive sum function from above.
- Create a recursive function that will display an increasing triangle shape in a console window. The top of the triangle will have one '*' character, and the bottom of the triangle will have five '*' characters in a row.