-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRecursion.java
More file actions
158 lines (153 loc) · 3.93 KB
/
Recursion.java
File metadata and controls
158 lines (153 loc) · 3.93 KB
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
/*
public class Recursion {
//decreasing order print
public static void printDec(int n){
if((n==1)){
System.out.println(n);
return;
}
System.out.print(n + " ");
printDec(n-1);
}
// increasing order print
public static void printInc(int n){
if(n==1){
System.out.print(n+" ");
return;
}
printInc(n-1);
System.out.print(n+" ");
}
public static void main(String[] args) {
int n=10;
printInc(n);
}
}
*/
/*
// factorial of a no.
public class Recursion {
public static int fact(int n){
if(n==0){
return 1;
}
int fnm1 = fact(n-1);
int fn = n * fnm1;
return fn;
}
public static void main(String[] args) {
int n= 5;
System.out.println(fact(n));
}
}
*/
/*
//print sum of first n natural no
public class Recursion {
public static int calSum(int n){
if(n==1){
return 1;
}
int fnm1 = calSum(n-1);
int fn = n + fnm1;
return fn;
}
public static void main(String[] args) {
int n= 5;
System.out.println(calSum(n));
}
}
*/
/*
// fibonnacci series
public class Recursion {
public static int fib(int n){
if(n==0 || n ==1){
return n;
}
int fnm1 = fib(n-1);
int fnm2 = fib(n-2);
int fn = fnm1+fnm2;
return fn;
}
public static void main(String[] args) {
int n= 2;
System.out.println(fib(n));
}
}
*/
/*array is sorted or not
public class Recursion {
public static boolean isSorted(int arr[],int i){
if(i==arr.length-1){
return true;
}
if(arr[i] > arr[i+1]){
return false;
}
return isSorted(arr, i+1);
}
public static void main(String[] args) {
int arr[]= {1,2,3,4};
System.out.println(isSorted(arr, 0));
}
}
*/
/*
public class Recursion {
//find first occurence of an element
public static int firstOccurence(int arr[], int key, int i){
if(i == arr.length){
return -1;
}
if(arr[i] == key){
return i;
}
return firstOccurence(arr, key, i+1);
}
// last occurence of a element...
public static int lastOccurence(int arr[],int key, int i){
if(i == arr.length){
return -1;
}
int isFound = lastOccurence(arr, key, i+1);
if(isFound == -1 && arr[i]==key){
return i;
}
return isFound;
}
public static void main(String[] args) {
int arr[]= {8,3,6,9,5,10,2,5,3};
System.out.println(firstOccurence(arr, 5, 0));
System.out.println(lastOccurence(arr, 5, 0));
}
}
*/
//print x^n
public class Recursion {
public static int power(int x,int n){
if(n==0){
return 1;
}
int Xnm1 = power(x, n-1);
int Xn =x*Xnm1;
return Xn;
}
public static int optimizedPower(int a,int n){
if(n==0){
return 1;
}
int halfPower = optimizedPower(a, n/2);
int halfPowerSq = halfPower*halfPower;
//n is odd
if(n %2 !=0){
halfPowerSq = a * halfPowerSq;
}
return halfPowerSq;
}
public static void main(String[] args) {
int a =2;
int n =5;
System.out.println(optimizedPower(a, n));
}
}