Recursion and Backtracking

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

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); }

Resources •https://bit.ly/39lNlVT (very detailed explanation) •https://mirror.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.

yami9's blog