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
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: helps 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.net/group/MWSDmqGsZm/contest/223339/problem/A https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/B https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/C https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/D https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/E https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/L https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/P https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/Q https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/Y https://cses.fi/problemset/task/1068 https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/O https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/I https://leetcode.com/problems/n-th-tribonacci-number/ https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/S https://codeforces.net/group/MWSDmqGsZm/contest/223339/problem/V https://binarysearch.com/problems/Phone-Number-Combinations https://leetcode.com/problems/powx-n/description/ https://codeforces.net/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.net/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.
