Recursion

What is Recursion

  • When functions call themselves
  • This is to call the function with different input
  • The function will continue to run until it meets the tail
  • The tail is the final iteration of a recursive function.
  • The tail will be activated by base condition is meet
  • After the program reaches the tail it evaluates all previous method calls

Example of Recursion

A common example of recursion is the power function

  • It first recieves the base and the exponent
  • It will return the base * the method
  • However, the method has the exponent one less
  • Eventually the exponent will become 0 and you can return 1

Copy

public int timesTableR(int base,int exponent){
    if(exponent<=0){
        return 1; 
    }
    return base*timesTableR(base,exponent-1);
}

Applications of Recursion

Recursion is used in alot of applications.
Here are some notable ones

  • Sorting Algorithims. Namely:quick sort and radix sort
  • Depth First Search(DFS) used for graph theory
  • Math: Fibonnacci Sequence and the Akermann Function

Pros and Cons of Recursion

Pros Cons
Easy to Understand and requires minimal Statements Slower than iterative and more memory intensive. As it leave a memory trail to the tail.
Preferred in problem with complex data structure like linked lists or graph theory If Base case is not set, it can cause problems like crashing and stack overflow.
Useful in multiprogramming and multitasking enviroments Each function will occupy memory in stack. This will lead to stack overflow error.