Recursion are difficult because when solving recursive problems we think in looping way or sequential manner which is not usefull in solving recursive problems.So recursion problems are solved by using BRI (Big Recursive Idea)

Basically there are two types of recursion one is direct and another one is indirect

There are 2 types of recursion ->

   1.   Head Recursion
   2.  Tail Recursion

PROBLEM: HOW MANY PARROTS?

Passengers on the Tropical Paradise Railway (TPR) look forward to seeing dozens of colorful parrots from the train windows. Because of this, the railway takes a keen interest in the health of the local parrot population and decides to take a tally of the number of parrots in view of each train platform along the main line. Each platform is staffed by a TPR employee (see Figure 6-1), who is certainly capable of counting parrots. Unfortunately, the job is complicated by the primitive telephone system. Each platform can call only its immediate neighbors. How do we get the parrot total at the main line terminal?

TAIL RECURSION APPROACH

1. Count the parrots visible from the station platform.
2. Add this count to the total given by the previous station.
3. Call the next station to pass along the running sum of parrot counts.
4. Wait for the next station to call with the total parrot count, and then pass this total up to the previous station

HEAD RECURSION APPROACH

1. Call the next station.
2. Count the parrots visible from the station platform.
3. Add this count to the total given by the next station.
4. Pass the resulting sum up to the previous station.

BIG RECURSIVE IDEA

Each entity cares about what not how..... (simple thats it)

PROBLEM: COMPUTING THE SUM OF AN ARRAY OF INTEGERS

STEP 1 -> write a iteraive solution

int iterativeArraySum(int integers[], int size) {
 int sum = 0;
 for (int i = 0; i < size; i++) {
 sum += integers[i];
 }
 return sum;
}

STEP 2 -> write a dispatcher function

dispatcher function should follow 2 rules->

RULE 1 : It handles trival case without calling a function

Trivial case occurs when size is 0 or size is 1,when size is zero sum is 0 & when size is 1 then sum is itself that number

RULE 2 :

Dispatch function should pass less work to main function,so here dispatch function will pass array with size - 1 to main function

int arraySumDelegate(int integers[], int size) {
     if (size == 0) return 0;
     int lastNumber = integers[size - 1];
     int allButLastSum =   iterativeArraySum(integers, size - 1);
     return lastNumber + allButLastSum;
}

then make it recursive (function calls itself)

int arraySum(int integers[], int size) { if (size == 0) return 0; int lastNumber = integers[size - 1]; int allButLastSum = arraySum(integers, size - 1); return lastNumber + allButLastSum; }

COMMON MISTAKES

1. TO MANY PARAMETERS

When you use tail recursion method you pass to many methods as compared to iterative solution,to avoid this first write iterative solution then think about parameters then think about recursion.

2. GLOBAL VARIABLE

Avoid use of global variables while using recursions.

QUESTION : recursive function that counted the number of zeros appearing in an array of integers

int zeroCountIterative(int numbers[], int size) {
 int sum = 0;
int count = 0;
 for (int i = 0; i < size; i++) {
 if (numbers[i] == 0) count ++;
 }
 return count;
}

int count;
int zeroCountRecursive(int numbers[], int size) {
 if (size == 0) return count;
 if (numbers[size - 1] == 0) count++;
 zeroCountRecursive(numbers, size - 1);
}

int zeroCountRecursive(int numbers[], int size) {
 if (size == 0) return 0;
int count = zeroCountRecursive(numbers, size - 1);
if (numbers[size - 1] == 0) count++;
return count;
}