Computing the Nth Fibonacci Number and power of a number

Computing the Nth Fibonacci Number

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 recursion to compute a recursive relation

However, while this example is illustrative, it is also inefficient: each single instance of the method will call the function itself twice, leading to an exponential growth in the number of times the function is called as N increases. The above function is O(2N), but an equivalent iterative solution has complexity O(N). In addition, there is a "closed form" expression that can be evaluated in O(N) floating-point multiplications.

Computing the Nth power of a number

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 the principles mentioned above: the recursive method implements a base case (two cases, n = 0 and n = 1) that terminates the recursion, and a recursive case that calls the method again. This method is O(N) and can be reduced to a simple loop using tail-call optimization.

Traversing a Tree data structure with recursion

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 constructed by connecting multiple Node class's object like below, the traversal is called in-order traversal of tree.

public static void inOrderTraversal(Node root) {
	if (root != null) { 
		inOrderTraversal(root.left); // traverse left sub tree
		System.out.print(root.data + " "); // traverse current node
		inOrderTraversal(root.right); // traverse right sub tree
	}
}

As demonstrated above, using recursion we can traverse the tree data structure without using any other data structure which is not possible with the iterative approach.

Reverse a string using Recursion

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 olleh
	}
	public static String reverse(String s) {
		if (s.length() == 1) {
			return s;
		}
 
		return reverse(s.substring(1)) + s.charAt(0);
	}
}

Computing the sum of integers from 1 to N

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 fact there is a closed form expression that computes the sum in O(1) operations.

Basic Programs

Learn All in Tamil © Designed & Developed By Tutor Joes | Privacy Policy | Terms & Conditions