Thursday, March 13, 2014

Understanding Recursion

What is recursion - In computer science, it is essentially a method/function calling itself.

What do you think can go wrong? Like infinite loops (using for, while) you could have an endless program that will run as far as memory limits allows. However like we can prevent infinite loops we can have methods call themselves safely. Based on certain conditions we can return from the method. This condition is the base case (there maybe multiple base cases as well). Other rules must be present so that eventually all other cases reduce towards the base cases(s).

Consider the method:
What will be the output if a positive integer is passed in for n?

Suppose we want the sum of first 5 numbers. It can be broken down as follows:
sum(5) = sum(4) + 5
           = sum(3) + 4 + 5
           = sum(2) + 3 + 4 + 5
           = sum(1) + 2 + 3 + 4 + 5
           = 1 + 2 + 3 + 4 + 5

Recursion is a way of thinking - trying to find the solution to a problem by thinking about a smaller version of the same problem. The simplest problem is the base case.

A popular example is the Fibonacci series. The series goes 1, 1, 2, 3, 5, 8, 13...
The first and second terms are defined to be 1. Subsequent terms are the sum of the previous two terms. To define it more formally:

fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

Writing some code:

Another example - notice the slight difference in the order of calls in the two options. What do you think is the output if both methods are called with the same number?

Factorial - factorial of n is the product of all numbers 1 to n. For example 5! = 5*4*3*2*1=120. More formally:

factorial(0) = 1
factorial(n) = factorial(n-1)*n

Factorial is undefined for negative numbers.