**Goal:**↵
• Understand recursion↵
• Understand applications of recursion↵
• Learn how to brute-force using recursion↵
• Assess time complexity of recursive algorithms↵
• Use backtracking for efficient brute-force↵
↵
Recap on Functions↵
• A function is a block of code which runs the code inside with the↵
parameters it is given.↵
• Syntax:↵
**int add(int a, int b) {**↵
**return a + b;**↵
**}**↵
****↵
↵
**What is Recursion?**↵
Recursion happens when a function calls itself on a different set of↵
input parameters.↵
Used when the solution for current problem involves first solving a↵
smaller sub-problem.↵
Example: factorial(N) = factorial(N-1) * N↵
↵
**Recursive Function**↵
A function that calls itself is a recursive function↵
Example:↵
The above function will find the sum from 0 to the given parameter.↵
**int sum_0_to_n(int n) {**↵
**if (n <= 0) return 0;**↵
**return sum_0_to_n(n-1) + n;**↵
**}**↵
****↵
↵
**Recursive Tree**↵
A recursive tree is similar to a “mind map” of the↵
function call. Each node/vertex is the function call.↵
Value inside the node is the parameter.↵
Recursive tree of previous example for n = 3↵
[Your text to link here...](http://codeforces.com/e776d7/Screenshot from 2023-07-31 01-59-35.png)↵
Recursive trees are useful to help us understand↵
how the function acts.↵
↵
**Basic Structure of a Recursive Function**↵
• Parameters to start the function↵
• Appropriate base case(s) to end the recursion↵
• Recursively solve the sub-problems↵
• Process the result and return the value↵
↵
**Tougher example:**↵
Fibonacci function:↵
int fib(int n) {↵
if (n == 0) return 0;↵
if (n == 1) return 1;↵
return fib(n-1) + fib(n-2);↵
}↵
Recursive tree:↵
https://codeforces.com/a4c557/Screenshot from 2023-07-31 02-01-37.pngelps in visualization of recursion call and helps to understand how recursion stored in stack memory.↵
↵
**When do we need recursion?**↵
Recursion is usually used in complex situations where iteration is not↵
feasible.↵
• Brute-force↵
• Backtracking↵
• Dynamic Programming↵
• Graph/Tree Problems↵
• Etc.↵
↵
_Using Recursion to Brute-Force_↵
We can use recursion to go through every possible sub-problem. Also↵
useful when going through every combination/subset of a list.↵
Examples:↵
• Print all binary strings of a given length.↵
• Print all subsets of a given vector.↵
↵
_Time complexity of_↵
_Recursive Brute-Force_↵
• Can be calculated as the number of recursive calls multiplied by↵
additional complexity of the function.↵
• Can also be thought of as sum of time complexity of each layer of the↵
recursive tree.↵
↵
Example functions:↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n-1);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n/2);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n-1);↵
recurse(n-1);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n/2);↵
recurse(n/2);↵
}↵
↵
**Some Good Questions to build logic on Recursion:-**↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/A ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/B ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/C ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/D ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/E ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/L ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/P ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/Q ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/Y ↵
https://cses.fi/problemset/task/1068 ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/O ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/I ↵
https://leetcode.com/problems/n-th-tribonacci-number/ ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/S ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/V ↵
https://binarysearch.com/problems/Phone-Number-Combinations ↵
https://leetcode.com/problems/powx-n/description/ ↵
https://codeforces.com/problemset/problem/476/B ↵
https://leetcode.com/problems/k-th-symbol-in-grammar/description/ ↵
https://cses.fi/problemset/task/1623 ↵
https://cses.fi/problemset/task/1624 ↵
https://leetcode.com/problems/different-ways-to-add-parentheses/ ↵
↵
Resources↵
•https://bit.ly/39lNlVT (very detailed explanation)↵
•https://codeforces.com/blog/entry/92031 (advanced)↵
•https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/(Must to read)↵
Note:- gfg article ko tumhare bhai ne contribute kiya hai XD.↵
↵
• Understand recursion↵
• Understand applications of recursion↵
• Learn how to brute-force using recursion↵
• Assess time complexity of recursive algorithms↵
• Use backtracking for efficient brute-force↵
↵
Recap on Functions↵
• A function is a block of code which runs the code inside with the↵
parameters it is given.↵
• Syntax:↵
**int add(int a, int b) {**↵
**return a + b;**↵
**}**↵
****↵
↵
**What is Recursion?**↵
Recursion happens when a function calls itself on a different set of↵
input parameters.↵
Used when the solution for current problem involves first solving a↵
smaller sub-problem.↵
Example: factorial(N) = factorial(N-1) * N↵
↵
**Recursive Function**↵
A function that calls itself is a recursive function↵
Example:↵
The above function will find the sum from 0 to the given parameter.↵
**int sum_0_to_n(int n) {**↵
**if (n <= 0) return 0;**↵
**return sum_0_to_n(n-1) + n;**↵
**}**↵
****↵
↵
**Recursive Tree**↵
A recursive tree is similar to a “mind map” of the↵
function call. Each node/vertex is the function call.↵
Value inside the node is the parameter.↵
Recursive tree of previous example for n = 3↵
Recursive trees are useful to help us understand↵
how the function acts.↵
↵
**Basic Structure of a Recursive Function**↵
• Parameters to start the function↵
• Appropriate base case(s) to end the recursion↵
• Recursively solve the sub-problems↵
• Process the result and return the value↵
↵
**Tougher example:**↵
Fibonacci function:↵
int fib(int n) {↵
if (n == 0) return 0;↵
if (n == 1) return 1;↵
return fib(n-1) + fib(n-2);↵
}↵
Recursive tree:↵
h
↵
**When do we need recursion?**↵
Recursion is usually used in complex situations where iteration is not↵
feasible.↵
• Brute-force↵
• Backtracking↵
• Dynamic Programming↵
• Graph/Tree Problems↵
• Etc.↵
↵
_Using Recursion to Brute-Force_↵
We can use recursion to go through every possible sub-problem. Also↵
useful when going through every combination/subset of a list.↵
Examples:↵
• Print all binary strings of a given length.↵
• Print all subsets of a given vector.↵
↵
_Time complexity of_↵
_Recursive Brute-Force_↵
• Can be calculated as the number of recursive calls multiplied by↵
additional complexity of the function.↵
• Can also be thought of as sum of time complexity of each layer of the↵
recursive tree.↵
↵
Example functions:↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n-1);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n/2);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n-1);↵
recurse(n-1);↵
}↵
↵
void recurse(int n) {↵
if (n == 0) return;↵
recurse(n/2);↵
recurse(n/2);↵
}↵
↵
**Some Good Questions to build logic on Recursion:-**↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/A ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/B ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/C ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/D ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/E ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/L ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/P ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/Q ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/Y ↵
https://cses.fi/problemset/task/1068 ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/O ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/I ↵
https://leetcode.com/problems/n-th-tribonacci-number/ ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/S ↵
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/V ↵
https://binarysearch.com/problems/Phone-Number-Combinations ↵
https://leetcode.com/problems/powx-n/description/ ↵
https://codeforces.com/problemset/problem/476/B ↵
https://leetcode.com/problems/k-th-symbol-in-grammar/description/ ↵
https://cses.fi/problemset/task/1623 ↵
https://cses.fi/problemset/task/1624 ↵
https://leetcode.com/problems/different-ways-to-add-parentheses/ ↵
↵
Resources↵
•https://bit.ly/39lNlVT (very detailed explanation)↵
•https://codeforces.com/blog/entry/92031 (advanced)↵
•https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/(Must to read)↵
Note:- gfg article ko tumhare bhai ne contribute kiya hai XD.↵
↵
