Data Science prep

DSA -Day2

Aditya Kosuru's photo
Aditya Kosuru
·

3 min read

Prerequisites(surface understanding) :

  1. you should know the basics of CPP(STL, etc)

  2. recursion and looping

  3. learn about the Fibonacci series, tower of Hanoi, working and program

  4. pointers

  5. basic knowledge of stacks, queues, and double-linked lists

  6. big - o notations

Note: - the concepts would be roughly revised

Recursion:

NOTE: try to understand the given example it will enhance your understanding

The best way to understand Reactions is, to assume every time you call the functions again as a separate if condition for the given new input values.
you visualize better if you think of recursion as a series of numbers like
1,2,3,4,5…(here, pick any number 5 = (1+4) = 1+(1+3) = 1+1+1+(1+2) = 1+1+1+1+(1+1), here you can see any number can be found until you know the condition to find next number and the first number recursion works you similarly using recursive case and base case, you call the function changing the initial value according to the recursive case until you find the base case value)
2,4,6,8,…

Q1 Write a function that takes two inputs N and M and outputs the number of unique paths from the top left corner to the bottom right corner of an N by M grid one key constraint is that you can only move

Sol: try to write all possible cases to find recursive conditions it is mandatory to understand the solution and relations with as many examples as possible so never hesitate to try out as many examples as possible

in the above image, you can see some examples and their routs Now try to find any relations/recursion cases

if you look closely you can see that the 3×3 matrix is the sum of 2×3 and 3×2 matrix is this coincidence no
if you look closely all the cases of the 2×3 routs and 3×2 routs differ by one block in 3×3 routs and it also makes sense for this to occur since (2×3 over 3×2)-(3×3) is one block

so the recursive case is function(m,m) = function(m-1,n)+funtion(m,n-1)

and base case is function(1,1) = 1

now we can write recursive functions using these two

#include <iostream>
using namespace std;

int uniquePaths(int N, int M) {
    if (N == 1 || M == 1) {
        return 1;
    }

    return uniquePaths(N - 1, M) + uniquePaths(N, M - 1);
}

int main() {
    int N, M;

    cout << "Enter the number of rows (N): ";
    cin >> N;
    cout << "Enter the number of columns (M): ";
    cin >> M;

    cout << "The number of unique paths is: " << uniquePaths(N, M) << endl;

    return 0;
}

Types of recursions

  1. Direct
    example :-

     void fun(int n)

 {
     if (n > 0) {
         cout<<n<< " ";
         fun(n - 1);
     }
 }

  2. Indirect

    example:-

     #include <iostream> 
 using namespace std; 
 void funB(int n); 
 void funA(int n) 
 { 
     if (n > 0) { 
         cout <<" "<< n; 
         funB(n - 1); 
     } 
 } 
 void funB(int n) 
 { 
     if (n > 1) { 
         cout <<" "<< n; =
         funA(n / 2); 
     } 
 }

  3. tailed and non-tailed

    Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call.

    example:-

    return function(n); (this is tailed if the last line is of this type)

    return 1+function(n); (this is non-tailed since it is not finished after calling the function it still has to add 1)

NOTE:- this concept of tailed and non-tailed is used to determine whether to use loop or recursion because tailed recursion has more space complexity than in loop and has the same time complexity

data structures