Intro:

Definition:

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

Tracing:

• A very important example to understand the recursions:

Properties of recursion:

• Properties:

1. Base case.
2. A set of rules, also known as recurrence relation that reduces all other cases towards the base case. Note that there could be multiple places where the function may call itself.

Notes:

1. Any code before the recursion call will be called at the calling time.
2. Any code after the recursion call will be called at the returning time.

Examples:

• Reverse a string: Print a string in reverse order: You can easily solve this problem iteratively, i.e. looping through the string starting from its last character. But how about solving it recursively?

C/C++:

void printReverse(const char *str) {
  if (!*str)
    return;
  printReverse(str + 1);
  putchar(*str);
}

Java:

private static void printReverse(char [] str) {
  helper(0, str);
}

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