May_DSA_Batch/Recursion.java at main · himanshubuyerteam/May_DSA_Batch · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
class Recursion
{

    // public static void pd(int n)
    // {
    //     for(int i=n;i>=1;i--)
    //     {
    //         System.out.println(i);
    //     }
    // }
    //SC-o(n)
    //Tc-o(n)
    public static void pd(int n)
    {
        if(n==0)
            return;
        System.out.println(n);
        pd(n-1);
    }


    //SC-o(n)
    //Tc-o(n)
    public static void pi(int n)
    {
        if(n==0)
            return;
        pi(n-1);
        System.out.println(n);
    }

    //SC-o(n)
    //Tc-o(n)
    public static void pdi(int n)
    {
        if(n==0)
            return;
        System.out.println(n);
        pdi(n-1);
        System.out.println(n);
    }
    public static void f2()
    {
        System.err.println("F2 L2");
    }

    //SC-o(n)
    //Tc-o(n)
    public static int fact(int n)
    {
        if(n==0)
            return 1;
        int rans = fact(n-1);
        int mans = rans*n;
        return mans;
    }
    //SC-o(n)
    //Tc-o(n)
    public static int product(int a,int b)
    {
        if(b==1)
            return a;
        int rans = product(a, b-1);
        int mans = rans + a;
        return mans;
    }


    public static int product_line(int a,int b)
    {
        if(b==1)
            return a;
        return product_line(a, b-1)+a;
    }
    //SC-o(n)
    //Tc-o(n)
    public static int pow(int base, int power)
    {
        if(power==1)
            return base;
        int rans = pow(base, power-1);
        int mans = rans*base;
        return mans;
    }
    //SC-o(log n)
    //Tc-o(log n)
    public static int pow_opt(int base,int power)
    {
        if(power == 1)
            return base;
        int rans = pow_opt(base, power/2);
        if(power%2!=0)
            rans = rans * rans * base;
        else
            rans = rans * rans;
        return rans;
    }

    public static int fib(int n)
    {
        if(n<=1)
            return n;
        int ra1 = fib(n-1);
        int ra2 = fib(n-2);
        int mans = ra1+ra2;
        return mans;
    }
    public static int climbStair(int n)
    {
        if(n<=1)
            return 1;
        int ra1 = climbStair(n-1);
        int ra2= climbStair(n-2);
        return ra1+ra2;
    }
    public static int mazePath(int sr,int sc,int dr,int dc)
    {
        if(sr==dr && sc ==dc)
            return 1;
        if(sr>dr || sc>dc)
            return 0;
        int ra1 = mazePath(sr, sc+1, dr, dc);
        int ra2 = mazePath(sr+1, sc, dr, dc);
        return ra1+ra2;
    }
    public static int mazePath_path(int sr,int sc,int dr,int dc,String path)
    {
        if(sr==dr && sc ==dc)
        {
            System.out.println(path);
            return 1;
        }
        if(sr>dr || sc>dc)
            return 0;
        int ra1 = mazePath_path(sr, sc+1, dr, dc,path+"R");
        int ra2 = mazePath_path(sr+1, sc, dr, dc,path+"D");
        return ra1+ra2;
    }
    public static void f1()
    {
        System.out.println("F1 L1");
        f2();
    }
    public static void print()
    {
        System.out.println("Hello");
        f1();
        System.out.println("Bye");
    }
    public static void main(String[] args) {
        // print();
        // pd(5);
        // pi(5);
        // pdi(5);
        int ans = mazePath_path(0,0,2,2,"");
        // System.out.println(ans);
        System.out.println("Number of Ways is -->"+ans);

    }
}