Recursion

We've been wanting to ask this for a long time - "So what is Recursion?"

According to LeetCode, Recursion is an approach to solving problems using a function that calls itself as a subroutine.

You might wonder how we can implement a function that calls itself. The trick is that each time a recursive function calls itself, it reduces the given problem into subproblems. The recursion call continues until it reaches a point where the subproblem can be solved without further recursion.

A recursive function should have the following properties so that it does not result in an infinite loop:

1) A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer.
2) A set of rules, also known as recurrence relation that reduces all other cases towards the base case.

For example, try reversing a string "Hello" with Java. We make a call until the base case is met - in this case, the index is equal to the string length. Then, we print out the last alphabet of the string.

public class reverseString{

   public static void reverseString(char[] str) {
     helper(0,str);
   }

   public static void helper(int index, char[] str) {
     if(str == null || index >= str.length) {
       return;
     }
     helper(index+1,str);
     System.out.print(str[index]);
   }

   public static void main(String[] args) {
     String word = "Hello";

       reverseString(word.toCharArray());
   }
}

The recursive function makes the call the following way. The runtime complexity is O(n) while the space complexity is also O(n) because each function call of recursive algorithm takes O(n) space.

Tail Recursion

If we place a constraint by not allocating extra space for another array, which is to say we must do this by modifying the input array in-place with O(1) extra memory. 

public class tailCall{

  public static void reverseString(char[] s) {
      helper(0, s.length - 1, s);

  }

  public static void helper(int head,int tail,char[] s) {
      if(head >= tail) {
        for(int i = 0; i < s.length; i++)
         System.out.print(s[i]);
        return;
      }
      char tmp = s[head];
      s[head] = s[tail];
      s[tail] = tmp;

      helper(head + 1, tail - 1, s);
  }

  public static void main(String[] args) {
    String word = "Hello";

      reverseString(word.toCharArray());
  }
}