-
Notifications
You must be signed in to change notification settings - Fork 0
/
Recursion.cpp
132 lines (126 loc) · 3.6 KB
/
Recursion.cpp
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
#include <iostream>
using namespace std;
/*
FIND THE FACTORIAL FOR GIVEN NUMBER ‘N’.
FIND THE FIBONACCI NUMBER FOR GIVEN TERM ‘N’.
SOLVE ABOVE QUESTIONS USING TAIL RECURSION.
SOLVE TOWER OF HANOI PROBLEM FOR ‘N’ DISCS.
*/
long factorialNonTail(long n)
{
if (n == 0 || n == 1)
return 1;
else
return n * factorialNonTail(n - 1);
}
long factorialTail(long n, long result = 1)
{
if (n == 0 || n == 1)
return result;
else
return factorialTail(n - 1, result * n);
}
long fibonacciNonTail(long n)
{
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return fibonacciNonTail(n - 1) + fibonacciNonTail(n - 2);
}
long fibonacciTail(long n, long a = 0, long b = 1)
{
if (n == 1)
return a;
else if (n == 2)
return b;
else
return fibonacciTail(n - 1, b, a + b);
}
void TOH(int n, char A, char B, char C) // source, auxiliary, destination
{
if (n == 1)
{
cout << A << " to " << C << endl;
return;
}
TOH(n - 1, A, C, B);
cout << A << " to " << C << endl;
TOH(n - 1, B, A, C);
}
void displayMenu()
{
cout << "1. Factorial of Number Using Non Tail Rcursion\n"
<< "2. Factorial of a Number Using Tail Recursion\n"
<< "3. Find nth Fibonacci Number using Non Tail Recursion\n"
<< "4. Find nth Fibonacci Number using Tail Recursion\n"
<< "5. Tower of Hanoi Solver\n"
<< "Enter 0 to exit\n\n";
}
int main()
{
system("cls");
long choice, n;
cout << "Recursion MultiTools By SakshamJr!\n";
cout << "----------------------------------\n\n";
do
{
displayMenu();
cout << "Enter the Tool You Want to Use: ";
cin >> choice;
switch (choice)
{
case 1:
system("cls");
cout << "Enter the Number: ";
cin >> n;
cout << "Factorial = " << factorialNonTail(n) << endl;
break;
case 2:
system("cls");
cout << "Enter the Number: ";
cin >> n;
cout << "Factorial = " << factorialTail(n) << endl;
break;
case 3:
system("cls");
cout << "Enter n: ";
cin >> n;
if (n == 1)
cout << "1st Fibonacci Number = 0";
else if (n == 0)
cout << "0th Fibonacci Number Doesnt Exist!\n";
else
cout << n << "th Fibonacci Number = " << fibonacciNonTail(n) << endl;
break;
case 4:
system("cls");
cout << "Enter n: ";
cin >> n;
if (n == 1)
cout << "1st Fibonacci Number = 0";
else if (n == 0)
cout << "0th Fibonacci Number Doesnt Exist!\n";
else
cout << n << "th Fibonacci Number = " << fibonacciTail(n) << endl;
break;
case 5:
system("cls");
cout << "Enter Number of Disc in Tower of Hanoi: ";
cin >> n;
cout << "The Tower of Hanoi of " << n << " discs can be solved by moving: \n";
TOH(n, 'A', 'B', 'C');
cout << "One Disc at a time!\n";
break;
case 0:
cout << "Thanks For Using Recursion Multitools by SakshamJr!\n";
break;
default:
cout << "Enter Valid Choice!\n";
break;
}
cout << endl;
} while (choice != 0);
return 0;
}