Recursion Concepts With Parameters - STRIVERS-A2Z-DSA-SHEET Learning

Parameterized Recursion

In basic recursion, global variables or implicit logic are sometimes used to control the recursion state. Parameterized recursion involves passing all required information as parameters to the recursive function. This approach results in:

Better control over recursion flow
Cleaner and more maintainable code
Independence from external or global state

Now, let's understand parameterized recursion with the help of a few examples.

Example 1: Print Value `X`, `N` Times

Problem: Given two numbers X and N, print the value X exactly N times using recursion.

Recursive Approach With Parameters

1#include <bits/stdc++.h>
2using namespace std;
3
4void printXNTimes(int x, int n) {
5    if (n == 0) return;     // base case
6    cout << x << " ";       // print the value
7    printXNTimes(x, n - 1); // recursive call with reduced n
8}
9
10int main(){
11    int x = 4, n = 5;
12    
13    // Printing X, N number of times
14    printXNTimes(x, n);
15    
16    return 0;
17}

Explanation: Each recursive call prints the value x once and decreases n by 1 until n reaches zero, which terminates recursion.

Example 2: Print Numbers from 1 to N

Problem: Given a number N, print all the numbers from 1 to N.

To solve this problem, both head and tail recursion work.

Head Recursion (Work Happens After Recursion)

1#include <bits/stdc++.h>
2using namespace std;
3
4// Recursive function to print numbers from 1 to N
5void print1ToN(int n) {
6    if (n == 0) return;
7    print1ToN(n-1);             // recursive call before printing
8    cout << n << " ";           // print after recursion call
9}
10
11int main(){
12    int n = 5;
13    
14    // Printing 1 to N
15    print1ToN(n);
16    
17    return 0;
18}

Explanation: Each recursive call decreases the value of N and calls the function recursively with the updated value until it reaches 0. On the return path, each call prints the value N until the first call made is returned.

If we wish to use Tail recursion to print the numbers from 1 to N, then we need to introduce an index parameter i.

Tail Recursion (Work Happens Before Recursion)

1#include <bits/stdc++.h>
2using namespace std;
3
4// Recursive function to print numbers from 1 to N
5void print1ToN(int i, int n) {
6    if (i > n) return;
7    cout << i << " "; // print before recursion call
8    print1ToN(i + 1, n);    // recursive call after printing
9}
10
11int main(){
12    int n = 5;
13    // Printing 1 to N
14    print1ToN(1, n);
15    return 0;
16}

Example 3: Print Numbers from N to 1

Printing the numbers from N to 1 is similar to printing the numbers from 1 to N.

While printing the numbers from 1 to N, head recursion was used (where work happens after the recursion call). This had printed the numbers in the order from 1 to N.

Now, in order to print the numbers from N to 1, tail recursion can be used. In the tail recursion, work (printing the number) happens before the recursion call. This will print the numbers in decreasing order from N to 1.

Printing N to 1 (Using Tail Recursion)

1#include <bits/stdc++.h>
2using namespace std;
3
4// Recursive function to print numbers from N to 1
5void printNto1(int n) {
6    if (n == 0) return;
7    cout << n << " ";           // print before recursion call
8    printNto1(n-1);             // recursive call after printing
9}
10
11int main(){
12    int n = 5;
13    
14    // Printing N to 1
15    printNto1(n);
16    
17    return 0;
18}

Explanation: Each recursive call prints the value of N and decreases the value of N by 1 and calls recursively the function with the updated value until it reaches 0. This prints the numbers from N to 1.

If we wish to use Head recursion to print the numbers from N to 1, then we need to introduce an index parameter i.

Printing N to 1 (Using Head Recursion)

1#include <bits/stdc++.h>
2using namespace std;
3
4// Recursive function to print numbers from N to 1
5void printNto1(int i, int n) {
6    if (i > n) return;
7    printNto1(i+1, n);           // recursive call before printing
8    cout << i << " ";           // print after recursion call
9}
10
11int main(){
12    int n = 5;
13    
14    // Printing N to 1
15    printNto1(1, n);
16    
17    return 0;
18}

Explanation: Each recursive call increases the value of i by 1 until i becomes greater than n. On the return trip, each recursive call prints the value of i. This prints all the numbers from N to 1 using Head Recursion.

Head Recursion vs. Tail Recursion

Aspect	Head Recursion	Tail Recursion
Order of Execution	Recursive calls before performing work	Work performed before recursive calls
Loop Conversion	Harder to convert directly into a loop	Easily convertible into a loop
Compiler Optimization	Generally harder to optimize	Easier to optimize via tail call elimination
Typical Use Cases	Tree traversals, backtracking	Loop-like computations, accumulations