Tutorial by Examples

What is recursion: In general, recursion is when a function invokes itself, either directly or indirectly. For example: // This method calls itself "infinitely" public void useless() { useless(); // method calls itself (directly) } Conditions for applying recursion to a probl...

The following method computes the Nth Fibonacci number using recursion. public int fib(final int n) { if (n > 2) { return fib(n - 2) + fib(n - 1); } return 1; } The method implements a base case (n <= 2) and a recursive case (n>2). This illustrates the use of re...

The following method computes the sum of integers from 0 to N using recursion. public int sum(final int n) { if (n > 0) { return n + sum(n - 1); } else { return n; } } This method is O(N) and can be reduced to a simple loop using tail-call optimization. In f...

The following method computes the value of num raised to the power of exp using recursion: public long power(final int num, final int exp) { if (exp == 0) { return 1; } if (exp == 1) { return num; } return num * power(num, exp - 1); } This illustrates ...

Below is a recursive code to reverse a string /** * Just a snippet to explain the idea of recursion * **/ public class Reverse { public static void main (String args[]) { String string = "hello world"; System.out.println(reverse(string)); //prints dlrow oll...

Consider the Node class having 3 members data, left child pointer and right child pointer like below. public class Node { public int data; public Node left; public Node right; public Node(int data){ this.data = data; } } We can traverse the tree construct...

Recursion can be categorized as either Head Recursion or Tail Recursion, depending on where the recursive method call is placed. In head recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function). In ta...

If a recursive call goes "too deep", this results in a StackOverflowError. Java allocates a new frame for every method call on its thread's stack. However, the space of each thread's stack is limited. Too many frames on the stack leads to the Stack Overflow (SO). Example public static vo...

Consider the following naive method for adding two positive numbers using recursion: public static int add(int a, int b) { if (a == 0) { return b; } else { return add(a - 1, b + 1); // TAIL CALL } } This is algorithmically correct, but it has a major problem. ...