# Recursion and Iteration

Recursion means defining a problem in terms of itself. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2).

For example, we can define the operation “find eiffel tower” as:

• If you are already at eiffel tower, stop moving. (base condition)
• Ask someone which way to go and move until unsure.
• find eiffel tower. (tail recursion)

Above solution can be define in two steps. First, we don’t go to eiffel tower if we are already at eiffel tower. Secondly, we do some simple action that makes us problem simpler to solve. Finally, we execute the same algorithm.

# Parts of a Recursive Algorithm

• Every recursive method must have a base case – a condition under which no recursive call is made – to prevent infinite recursion.
• Every recursive method must make progress toward the base case to prevent infinite recursion.
• Recursive Call

To understand the above concept, here is simple example that print `n` numbers. Base conditon would then be `n = 0`.

```package com.javalatte.itcuties.recursioniteration;

public class SimpleRecursion {

public static void main(String[] JavaLatte) {
printN(5);
}

public static void printN(int n) {
if (n == 0) { // base condition
return;
}
System.out.print(n + " ");
printN(n - 1); // move towards base conditon
}
}
```

Sometimes a method has more to do following a recursive call; it gets done only after the recursive call (and all calls it makes) are finished.

```package com.javalatte.itcuties.recursioniteration;

public class SimpleRecursion1 {

public static void main(String[] JavaLatte) {
printN(3);
}

public static void printN(int n) {
if (n == 0) { // base condition
return;
}
System.out.println("Before Recursion : " + n);

printN(n - 1); // move towards base conditon

System.out.println("After Recursion : " + n);
}
}
```

# How Recursion Really Works

• At runtime, a stack of activation records (ARs) is maintained: one AR for each active method, where “active” means: has been called, has not yet returned.
• Each AR includes space for: method’s parameters, method’s local variables and return address where to start executing after the method returns.
• When a method is called, its AR is pushed onto the stack. The return address in that AR is the place in the code just after the call (so the return address is the “marker” for the previous “clone”)
• When a method is about to return, the return address in its AR is saved, its AR is popped from the stack, and control is transferred to the place in the code referred to by the return address.

# Factorial

Recursion definition

• factorial of 0 is 1
• factorial of N (for N > 0) is N * factorial (N-1)

Iterative definition

• factorial of 0 is 1
• factorial of N (for N>0) is N*N-1* … *3*2*1

Example: FactorialRecursion.java

```package com.javalatte.itcuties.recursioniteration;

public class FactorialRecursion {

public static void main(String[] JavaLatte) {
System.out.println(factorial(3));
}

static int factorial(int n) {
if (n == 0) {
return 1; // base condition
} else {
return n * factorial(n - 1);
}
}
}
```

The call `factorial(3)` leads to three recursive calls when all calls are still active, the runtime stack would be as shown below.

 N: 0 <- top of stack Returned 1 N: 1 Returned 1 N: 2 Returned 2 N: 3 Returned 6

Example:: FactoralIterative.java

```package com.javalatte.itcuties.recursioniteration;

public class FactoralIterative {

public static void main(String[] JavaLatte) {
int N = 3;
int tmp = N;
for (int i = N - 1; i >= 1; i--) {
tmp = tmp * i;
}
System.out.println("Factorial(" + N + ") : " + tmp);
}
}
```

# Fibonacci

In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence
1,1,2,3,5,8,13,21,34,55,89,144….
or
0,1,1,2,3,5,8,13,21,34,55,89,144….

Recursion definition
fib(x) = fib(x-1) + fib(x-2) where f(0)=1 and f(1)=1

To print N-th Finbonacci number
Example: FibonacciRecursion.java

```package com.javalatte.itcuties.recursioniteration;

public class FibonacciRecursion {

public static void main(String[] JavaLatte) {
System.out.println(fib(5));
}

public static int fib(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return (fib(n - 1) + fib(n - 2));
}
}
}
```

To print Finbonacci Series
To obtain the sequence, we start with 1 and 1 after which every number is the sum of the previous two numbers.
Example: FibonacciIterative.java

```package com.javalatte.itcuties.recursioniteration;

public class FibonacciIterative {

public static void main(String[] JavaLatte) {
fib(6);
}

public static void fib(int n) {
if (n == 0 || n == 1) {
System.out.print(n + " ");
} else {
System.out.print("1 1 ");
int first = 1;
int second = 1;
for (int i = 1; i < n; i++) {
int next = first + second;
System.out.print(next + " ");
first = second;
second = next;
}
}
}
}
```

Few doubt comes into mind that is recursion usually make your code faster and take less memory? The answer is No. Then why we use recursion because sometimes makes your code much simpler!

# Recursion vs. Iteration

• Roughly speaking, recursion and iteration perform the same kinds of tasks:
- Solve a complicated task one piece at a time, and combine the results.
• Emphasis of iteration:
- keep repeating until a task is done. Example: loop counter reaches limit.
• Emphasis of recursion:
- Solve a large problem by breaking it up into smaller and smaller pieces until you can solve it; combine the results. Example: recursive factorial function.
• Recursion usually slower due to the overhead of maintaining the stack.
• Recursion usually uses more memory for the stack.
• Some data structures like trees are easier to explore using recursion

# Which is Better Recursion or Iteration

• Depends on problem
- The factorial is pretty artificial, it is so simple that it really doesn’t matter which version you choose.
• Recursive is not always better
- Fibonacci using recursion takes O(n^2) steps for large n where as iterative approach is linear; it takes O(n) steps.

# Binary Search

A binary search search algorithm finds the position of a specified input value within an array sorted.
In each step, the algorithm compares the search value with the value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special “not found” indication is returned.

Example: BinarySearchRecursion.java

```package com.javalatte.itcuties.recursioniteration;

import static com.javalatte.itcuties.recursioniteration.BinarySearchIterative.binarySearch;

public class BinarySearchRecursion {

public static void main(String[] JavaLatte) {
int[] array = new int[]{4, 5, 6, 8, 23, 34, 45, 65, 78, 89, 94, 142, 33, 221, 566};
int searchElement = 45;

int index = binarySearch(array, searchElement);
if (index == -1) {
} else {
System.out.println(searchElement + " is found");
}
}

public static int binarySearch(int[] arr, int value) {
return binarySearch(arr, value, 0, arr.length - 1);
}

/**
* Recursive function
*
* @param arr input array
* @param value search value
* @param low 0
* @param high length-1
* @return index
*/
public static int binarySearch(int[] arr, int value, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
return binarySearch(arr, value, mid + 1, high);
} else {
return binarySearch(arr, value, low, mid - 1);
}
}
}
```

Example: BinarySearchIterative.java

```package com.javalatte.itcuties.recursioniteration;

public class BinarySearchIterative {

public static void main(String[] JavaLatte) {
int[] array = new int[]{4, 5, 6, 8, 23, 34, 45, 65, 78, 89, 94, 142, 33, 221, 566};
int searchElement = 46;

int index = binarySearch(array, searchElement);
if (index == -1) {
} else {
System.out.println(searchElement + " is found");
}

}

public static int binarySearch(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + high;
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}

return -1;
}
}
``` 