## What is Recursion

Like the "Shingle Guy" (shown on the right) installing multiple rows of roof shingles,

A

The process of recursion can be used whenever a problem can be corrected by solving one or more smaller versions of the same problem and then combining the results.

**recursion**involves performing the same task repeatedly until it is complete.A

**recursive program**,**function**, or**procedure**is one that invokes itself in processing the problem it is programmed to resolve.The process of recursion can be used whenever a problem can be corrected by solving one or more smaller versions of the same problem and then combining the results.

*To prevent***infinite recursion**, a base (trivial) case that requires no recursion must be part of the recursive solution.## Examples

**Factorials - n! (n Factorial)**

One of the simplest examples of a problem that can be resolved using a recursive algorithm is calculating the factorial of a number.

The

**factorial of a number**is the product of all positive integers from 1 to the number. In mathematical notation, a factorial is represented by the symbol ” ! ”.

For example, 5! = 5 * 4 * 3 * 2 * 1 = 120

Computing 5! can be thought of as 5*4!

5! = 5*4! = 5 *24 = 120

or more generally as

n! = n *(n-1)! for n > 0.

Also, by definition 0! is equal to one.

**Non Recursive Solution for Computing Factorial (5)**

**public static void main(String[] args)**

{

int num, fact; fact = 1;

num = 5;

for (int i=1; i<=num; i++)

{

fact = fact * i;

}

System.out.println ("Factorial (" + num + "!) is " + fact);

}{

int num, fact; fact = 1;

num = 5;

for (int i=1; i<=num; i++)

{

fact = fact * i;

}

System.out.println ("Factorial (" + num + "!) is " + fact);

}

**Recursive Solution for Computing Factorial(5)**

To implement the factorial problem using recursion, we observe that:

factorial (n) = n * factorial (n-1) = n * (n-1) * factorial ((n-1) -1) and so forth, until n-1 = 1.

We can create a function which takes an argument

*n*, and returns

*n*multiplied by the factorial of (n-1), except in the base case where n = 1, when it returns 1.

*This implements the factorial problem using recursion:*

**public static void main(String[] args)**

{

int num = 5;

System.out.println("Factorial (" + num + "!) is " + fact(num));

}

public static int fact (int n)

{

if (n == 0 || n ==1)

{

return 1;

} else

{

return (n * fact(n-1));

}

}{

int num = 5;

System.out.println("Factorial (" + num + "!) is " + fact(num));

}

public static int fact (int n)

{

if (n == 0 || n ==1)

{

return 1;

} else

{

return (n * fact(n-1));

}

}

You will note we have created a static method. The only reason we have done this is so we can call our methods within the run method. This will be one of the few times we will actually creat static methods on this class.

**Steps involved in the Recursive Solution for Computing Factorial (5)**

The following diagram shows how the function fact, which takes an

*int*as an input parameter and returns an

*int*as a result, calls itself until it reaches the base case where

*n = 1*.

**Finding the Greatest Common Divisor (GCD)**

Another example of a problem suited to recursion is

**Euclid's solution**to calculating the

*(GCD) for two integers,*

**g**reatest**c**ommon**d**ivisor*a*and

*b*.

The

**GCD**is the largest integer that divides into both numbers evenly. We can use trial-and-error to find the greatest common divisor of two whole numbers (12 and 18).

For example,

- 12 is evenly divisible by 1, 2, 3, 4, 6, and 12
- 18 is evenly divisible by 1, 2, 3, 6, 9, and 18
- Both numbers are evenly divisible by 1, 2, 3, and 6
- 6 is the largest common divisor

**Euclidean Algorithm**can also be used to find the GCD.

*Euclid's solution is defined as:*

GCD (a,b) is a if b==0

else

GCD (a,b) is GCD (b, modulus(a/b))

**Note:**The modulus is the remainder when a is divided by b and is computed in Java by using the % operator

For example, if a=187 and b=77

187 % 77 = 33

77 % 33 = 11

33 % 11 = 0

Therefore, 11 is the greatest common divisor.

*We can create a recursive function that uses Euclid's Algorithm to find the GCD of two integers.*

**public static void main(String[] args)**

{

int n1= 27;{

int n1= 27;

*int n2 = 18;*

int ans = gcd(n1,n2);int ans = gcd(n1,n2);

**System.out.println("The gcd of " + n1 + " and " + n2 + " is " + ans);**

}

public static int gcd(int a, int b)

{

if (b == 0)

{

return a;

} else

{

return gcd(b, a % b);

}

}}

public static int gcd(int a, int b)

{

if (b == 0)

{

return a;

} else

{

return gcd(b, a % b);

}

}

**Steps Involved in the Recursive Solution for Calculating GCD**

The function is defined with

**two int**values as input parameters (

*a*and

*b*) and returns an

**int**as a result. The function calls itself until it reaches the base case where b = 0.

**The 3 Laws of Recursion**

When creating recursive algorithms, it is important to follow these 3 rules:

The first rule states that we have to have a condition that we can finally say "I know the answer to that question". This is the point where we can finally send back a piece of the puzzle up the recursive call chain to help solve our original questions.

The second rule states that we need to make some change that will take us in the right direction. For instance, in the Fibonacci definition, each time we make a new call to our method, we are decreasing the number so it will become closer and closer to our base case Fib(1) or Fib(0) . This is needed in conjunction with rule 1 to prevent infinite recursive calls.

Finally, the third rule is what actually makes our method a recursive one. If we write a method which never in fact calls itself, we cannot define it as a recursive method.

- A recursive algorithm must have a
**base case**. - A recursive algorithm must change its state and move toward the base case.
- A recursive algorithm must call itself, recursively.

The first rule states that we have to have a condition that we can finally say "I know the answer to that question". This is the point where we can finally send back a piece of the puzzle up the recursive call chain to help solve our original questions.

The second rule states that we need to make some change that will take us in the right direction. For instance, in the Fibonacci definition, each time we make a new call to our method, we are decreasing the number so it will become closer and closer to our base case Fib(1) or Fib(0) . This is needed in conjunction with rule 1 to prevent infinite recursive calls.

Finally, the third rule is what actually makes our method a recursive one. If we write a method which never in fact calls itself, we cannot define it as a recursive method.