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 /predownloaded/fa/a4/faa428c10383195b64392dbc7df20e55d4f2d40a.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.net/a4c557/Screenshot from 2023-07-31 02-01-37.png

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.