Recursion and Backtracking

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	Um_nik	162
3	atcoder_official	161
4	maomao90	160
5	djm03178	158
5	-is-this-fft-	158
7	Dominater069	155
8	adamant	154
9	luogu_official	153
10	awoo	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