-
Notifications
You must be signed in to change notification settings - Fork 0
/
recursive_functions.c
238 lines (206 loc) · 5.45 KB
/
recursive_functions.c
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
/*
========================================================================================
Author : Gabriel Hochmann
Date : July 10, 2024
File : recursive_functions.c
Source : Recursion (List 1) - Professor Rômulo Silva
Description : A C source file that implements recursive functions.
========================================================================================
*/
#include "recursive_functions.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
// Function to print numbers in ascending order recursively
void printNumbersAscending(int num)
{
if (num > 1)
{
printNumbersAscending(num - 1);
printf("%d\n", num - 1);
}
}
// Function to print numbers in descending order recursively
void printNumbersDescending(int num)
{
if (num > 1)
{
printf("%d\n", num - 1);
}
printNumbersDescending(num - 1);
}
// Function to calculate summation recursively
int summation(int n)
{
if (n == 0)
{
return 0;
}
return n + summation(n - 1);
}
// Function to calculate factorial recursively
int factorial(unsigned int n)
{
if (n == 0)
{
return 1;
}
return n * factorial(n - 1);
}
// Function to calculate super factorial recursively
int superFactorial(unsigned int n)
{
if (n == 0)
{
return 1;
}
return factorial(n) * superFactorial(n - 1);
}
// Function to calculate power recursively
unsigned int power(unsigned int base, unsigned int exp)
{
if (exp == 0)
{
return 1;
}
return base * power(base, exp - 1);
}
// Function to calculate exponential factorial recursively
int exponentialFactorial(unsigned int n)
{
if (n == 0)
{
return 1;
}
return power(n, exponentialFactorial(n - 1));
}
/*
=================================================================================================
Catalan Number Implementations:
=================================================================================================
*/
/**
* catalanNumber_1:
* This implementation computes the nth Catalan number using the direct formula:
* C(n) = (2n!) / ((n+1)! * n!)
*
* Efficiency: This method is straightforward but limited by the factorial calculation.
* For large n, calculating factorials can result in overflow and is computationally expensive
* due to the large values involved.
*
* It is accurate only for small values of n (up to n = 6).
*/
int catalanNumber_1(unsigned int n)
{
if (n == 0)
{
return 1;
}
return (factorial(2 * n)) / (factorial(n + 1) * factorial(n));
}
/**
* catalanNumber_2:
* This implementation computes the nth Catalan number using dynamic programming.
* It recursively computes the sum of products of previously computed Catalan numbers.
*
* Efficiency: This method is computationally expansive because it involves a double
* recursive call that calculates the Catalan numbers for all values less than n.
* It avoids factorial overflow issues but is inefficient for large values of n due to
* repeated calculation.
*
* It correctly computes up to n = 19.
*/
int catalanNumber_2(unsigned int n) // Most efficient way, correctly computes up to n = 19
{
if (n == 0)
{
return 1;
}
int sum = 0;
for (unsigned int i = 0; i < n; ++i)
{
sum += catalanNumber_2(i) * catalanNumber_2(n - 1 - i);
}
return sum;
}
/**
* catalanNumber_3:
* This implementation computes the nth Catalan number using the recursive formula:
* C(n) = (2*(2n-1)*C(n-1)) / (n+1)
*
* Time Complexity: O(n)
* Space Complexity: O(n) (due to recursion stack)
*
* Efficiency: This method is theoretically faster than the dynamic programming approach
* (catalanNumber_2) because it has a lower time complexity (O(n) vs. O(n²)). However,
* due to the accumulation of rounding errors and integer overflow during the multiplication
* and division operations, it is less precise for larger values of n.
*
* It correctly computes up to n = 17.
*
* In summary, while this method is faster for small values of n, it sacrifices precision
* for larger n compared to the recursive dynamic programming method (catalanNumber_2).
*/
int catalanNumber_3(unsigned int n) // So so way, correctly computes up to n = 17
{
if (n == 0)
{
return 1;
}
return (2 * (2 * n - 1) * catalanNumber_3(n - 1)) / (n + 1);
}
// Function to check if a string is palindrome recursively
int isPalindrome(const char *str, int len)
{
if (len <= 1)
{
return 1;
}
if (*str != *(str + len - 1))
{
return 0;
}
return isPalindrome(str + 1, len - 2);
}
// Function to revert an array recursively
void revertArrayRecursive(int v[], int start, int end)
{
if (start >= end)
{
return;
}
int temp = v[end];
v[end] = v[start];
v[start] = temp;
return revertArrayRecursive(v, start + 1, end - 1);
}
// Function to revert an array (wrapper function)
void revertArray(int v[], int n)
{
revertArrayRecursive(v, 0, n - 1);
}
// Function to calculate Ackermann's function recursively
int ackermann(unsigned int m, unsigned int n)
{
if (m == 0)
{
return n + 1;
}
else if (n == 0)
{
return ackermann(m - 1, 1);
}
else
{
return ackermann(m - 1, ackermann(m, n - 1));
}
}
// Function to sum digits of a number recursively
int sumDigits(int n)
{
if (n == 0)
{
return 0;
}
return (n % 10) + sumDigits(n / 10);
};