Lecture 03 - Recursion

Recursion

→ A function calling itself is known as Recursion.

• usually recursion take more time and memory than loops.

• also there is risk of stack overflow for large values.

/*  SYNTAX
return_type function_name(parameters) {

    // Base case (termination condition)
    if (condition) 
    {
        return base_result;
    }

    // Recursive case (function calls itself)
    return function_name(modified_parameters);
}
*/

Example :

Factorial of a Number

1. Factorial → basic property : n! = n * (n-1)!

   base condition : 1 ! = 1

    #include <iostream>
    using namespace std;
    int factorial(int n){            // O(n)
        if (n==1) return 1;          // base condition
        return n * factorial(n-1);   // calling same function with modified arguments
    }
    int main(){
        int n;
        cin >> n;
        cout << "Factorial : " << factorial (n) << endl;
    }
   

Leetcode 509 - Fibonacci Number

2. Fibonacci → Base condition : fib(n) = fib(n-1) + fib(n-2)

    #include <iostream>
    using namespace std;
    int fibonacci(int n){          // O(2ⁿ)
        if (n==0) return 0;        // base condition 1
        else if (n==1) return 1;   // base condition 2
        return fibonacci(n-1) + fibonacci (n-2); // recursive calling
    }
    int main(){
        int n;
        cin >> n;
        cout << "fibonacci : " << fibonacci (n) << endl;
    }
   

Tower of Hanoi

3. Tower of Hanoi (TOH)

   base condition : move disc 1 from A to C

    #include <iostream>
    using namespace std;
    void TOH(char A , char B , char C, int n){
        if(n==1) {    // base condition
            cout<< n << " : " << A << " to " << C << endl;
            return;    // important to return to avoid infinite recursion 
        }
        TOH (A, C, B, n-1); // modified for n-1 disc
        cout<< n << " : " << A << " to " << C ;
        cout << endl;
        TOH (B, A, C, n-1); // modified for n-1 disc
    }
    int main(){
        int n;
        cin >> n;
        cout << "moves : " << endl;
        TOH('A', 'B', 'C', n);
        return 0;
    }
   

Leetcode 231 - Power of Two

• find if given number is power of 2

#include <iostream>
using namespace std;
bool powerOfTwo(double n){
    if (n<1) return 0;        // base condition 1
    else if (n==1) return 1;  // base condition 2
    return powerOfTwo(n/2);   // recursive call
}
int main(){
    double n;
    cin >> n;
    if(powerOfTwo(n)) cout<< "YES";
    else cout<<"NO";
    return 0;
}

Leetcode 342 - Power of Four

• find if given number is power of 4

#include <iostream>
using namespace std;
bool powerOfFour(double n){
    if (n<1) return 0;        // base condition 1
    else if (n==1) return 1;  // base condition 2
    return powerOfFour(n/4);  // recursive call
}
int main(){
    double n;
    cin >> n;
    if(powerOfFour(n)) cout<< "YES";
    else cout<<"NO";
    return 0;
}

Leetcode 3304 - Find the Kth character in the string.

• not recursion ; go check out the question

#include <iostream>
using namespace std;
char KthChar(int n){
    string str = "a";  // given
    string temp ="";
    int ch = 1;
    while (ch<=n){     // making string
        for(char i : str){
            if(i=='z') temp+='a';
            else temp += (char)i+1;
        }
        str=str+temp;
        temp="";
        ch*=2;
    }
    cout<<str<<endl;
    return str[n-1]; 
}
int main(){
    int n;
    cin >> n;
    cout<<KthChar(n);
    return 0;
}