Recursion

A function calls itself until specific condition is met. Example:

void print(int now, int target){
    if(now==target) return;
    cout<<now<<endl;
    print(now+1, target);
}
int main(){
    print(1,11);
    return 0;
}

What if there’s no if condition in print() ??

Then the function calls itself again and again and it never ends. Also when a function calls itself, then it will not completed yet, so number of uncompleted functions increases, which is known as Stack overflow.

So the if condition which terminates this series if the condition is satisfied is called Base Condition.

---

BACK TRACKING

Until now the structure of a recursive function is:

1. Base condition

2. Task

3. Function call

What if we reverse we do the Task after function call ???

Then, N function calls will be filled in stack space, and then while each function is getting completed Task will be implemented.

In this way, instead of completing N tasks first and clearing stack space, we are calling function N times and doing Task each time while function call is getting completed.

This is called Back Tracking.

void print(int now, int target){
    if(now==target) return;
    print(now+1, target);
    cout<<now<<endl;  
}
int main(){
    print(1,11);
    return 0;
}

---

TYPES OF RECURSION

1) Parameterized Recursion:

void print(int n, int sum){
    if (n<1){ cout<<sum; return; }
    print(n-1, sum+n);
}
int main(){
    print(10,0);
    return 0;
}

Here, the state is managed at parameters, and sum is printed finally.

2) Functional Recursion:

int print(int n){
    if (n<1) return 0;
    return n+print(n-1);
}
int main(){
   cout<< print(10);
    return 0;
}

Instead of printing, it is returning the value.

Also, Functional recursion is like backtracking. It goes till end and starts working from end to start.

Similarly, it also works from start to end too.

Simply, u can see recursion is calling from start to end and returning from end to start.

---

FEW BASIC PROBLEMS ON RECURSION :

1) Reverse an array

void reverse(int i, int n,  vector<int> &v){
    if(i==n/2) return;
    swap(v[i],v[n-1-i]);
    reverse(i+1,n, v);
}
int main() {
    vector<int> v={1,2,3,4,5};
    reverse(0,v.size(),v);
    for(int x:v) cout<<x<<endl;

    return 0;
}

2) Check if the given string is palindrome or not

bool check(int i, int n, string s){
    if (i==n/2) return true;
    if(s[i]!=s[n-1-i]) return false;
    return check(i+1,n,s);
}
int main(){
    string str="malayalam";
    cout<<check(0,str.size(),str);
    return 0;
}

---

MULTIPLE RECURSION CALLS

i-th Fibonacci number

int fibb(int i){
if (i <= 1) return i;
return fibb(i-1)+fibb(i-2);
}

int main(){
int n;
cin>>n;
cout<<fibb(n);
return 0;
}

Time complexity will be 2^n for this program, so a slightly improved one is:

int fibb(int a, int b, int n, int i){
if(i==n) return b;
return fibb(b,a+b,n,i+1);
}

int main(){
int n;
cin>>n;
if (n <= 1) cout<< n;
cout<<fibb(0,1,n, 0);
return 0;
}

---

RECURSION ON SUB SEQUENCES

1) Print all sub sequences of an array

Consider an array [3,1,2]. The sub sequences will be :

[3] [1] [2] [3,1] [3,2] [1,2] [3,1,2] [ ]

Here, regardless of the size of the array, to get all sub sequences ( which are continuous or non continuous ), the approach is take / not take the each element.

So in the seq(), at first we take a element with push_back at i-Th position and go to next position, or we don’t take that element at i-Th position with pop_back and proceed to next position.

Finally when we cover all positions and reach at i==n, we stop and add final array to result to collect all answers.

void seq(int i, int n, vector<int> &v, vector<int> &a, vector<vector<int>> &result){
    if(i==n){ result.push_back(a); return; }
    a.push_back(v[i]);
    seq(i+1,n,v,a,result);
    a.pop_back();
    seq(i+1,n,v,a,result);

}

int main(){
    vector<int> v={3,1,2};
    vector<int> temp;
    vector<vector<int>> result;
    seq(0,v.size(),v, temp, result);
}

2) Print sub sequence whose sum is k

Consider an array [1,2,1]. The sub sequences whose sum will be 2 are :

[1,1] [2]

Same approach as above but at i==n, if sum is k, we store in result, else we don’t.

void seq(int i, int n, vector<int> &v, vector<int> &a, vector<vector<int>> &result, int sum, int k){
    if(i==n){ if(sum == k) result.push_back(a); return; }
    a.push_back(v[i]);
    seq(i+1,n,v,a,result, sum+v[i],k);
    a.pop_back();
    seq(i+1,n,v,a,result, sum-v[i],k);

}

int main(){
    vector<int> v={3,1,2};
    vector<int> temp;
    vector<vector<int>> result;
    seq(0,v.size(),v, temp, result, 0, 2);
}

3) Count number of sub sequence whose sum is k

Same approach as above, but just like fibonacci series, we return sum of left plus right; and in base case we return 1 if sum==k else return 0.

int seq(int i, int n, vector<int> &v, vector<int> &a, int sum, int k){
    if(i==n){ if(sum == k) return 1; return 0; }
    a.push_back(v[i]);
    int l = seq(i+1,n,v,a, sum+v[i],k);
    a.pop_back();
    int r = seq(i+1,n,v,a, sum,k);
    return l + r;

}

int main(){
    vector<int> v={3,1,2};
    vector<int> temp;
    cout<<seq(0,v.size(),v, temp, 0, 3);
}

---