07_Recursion-01.
md 2024-06-18
Recursion - 01
What is Recursion?
Bookish Way:
How to Apply?
When to apply recursion:
1 / 14
07_Recursion-01.md 2024-06-18
Recursion Explanation with Examples:
2 / 14
07_Recursion-01.md 2024-06-18
3 / 14
07_Recursion-01.md 2024-06-18
Examples of Recursion:
1.
4 / 14
07_Recursion-01.md 2024-06-18
2.
Recursive/Recurrence Relation:
5 / 14
07_Recursion-01.md 2024-06-18
Recursion Components:
6 / 14
07_Recursion-01.md 2024-06-18
Example of Recursion(Factorial):
Stack Overflow in Recursion:
7 / 14
07_Recursion-01.md 2024-06-18
Factorial with Recursion:
Dry Run:
Code:
8 / 14
07_Recursion-01.md 2024-06-18
#include <iostream>
using namespace std;
int getFactorial(int n)
{
if (n == 0)
{
return 1;
}
int finalAns = n * getFactorial(n - 1);
return finalAns;
}
int main()
{
int n;
cout << "Enter value of n: ";
cin >> n;
int ans = getFactorial(n);
cout << "Factorial of " << n << " is " << ans << endl;
return 0;
}
H.W : Head Recursion and Tail Recursion:
Counting with Recursion:
Code (n->1):
#include <iostream>
using namespace std;
void printCounting(int n)
{
if (n == 0)
{
return;
}
cout << n << " ";
printCounting(n - 1);
}
int main()
{
int n;
9 / 14
07_Recursion-01.md 2024-06-18
cout << "Enter value of n: ";
cin >> n;
printCounting(n);
return 0;
}
Code (1->n):
#include <iostream>
using namespace std;
void printCounting(int n)
{
if (n == 0)
{
return;
}
printCounting(n - 1);
cout << n << " ";
}
int main()
{
int n;
cout << "Enter value of n: ";
cin >> n;
printCounting(n);
return 0;
}
Power with Recursion:
Code:
#include <iostream>
using namespace std;
int pow(int n)
{
if (n == 0)
{
return 1;
}
int finalAns = 2 * pow(n - 1);
return finalAns;
10 / 14
07_Recursion-01.md 2024-06-18
int main()
{
int n;
cout << "Enter value of n: ";
cin >> n;
int ans = pow(n);
cout << ans;
return 0;
}
Fibonacci with Recursion:
Dry Run:
11 / 14
07_Recursion-01.md 2024-06-18
Code:
#include <iostream>
using namespace std;
int fibonacci(int n)
{
if (n == 0 || n == 1)
{
return n;
12 / 14
07_Recursion-01.md 2024-06-18
}
int ans = fibonacci(n - 1) + fibonacci(n - 2);
return ans;
}
int main()
{
int n;
cout << "Enter value of n: ";
cin >> n;
int ans = fibonacci(n);
cout << ans;
return 0;
}
Sum with Recursion:
Dry Run:
Code:
#include <iostream>
using namespace std;
int getSum(int n)
{
13 / 14
07_Recursion-01.md 2024-06-18
if (n == 1)
{
return 1;
}
int ans = getSum(n - 1) + n;
return ans;
}
int main()
{
int n;
cout << "Enter value of n: ";
cin >> n;
int ans = getSum(n);
cout << ans;
return 0;
}
14 / 14
