Day 19 | Recursion | C++

We are moving ahead and learning algorithms, but the basics should be strong before we do it. We will soon see what dynamic programming is but before that, we need to understand what is recursion.

What is Recursion?

In very simple language we define recursion as a function further calling itself.

Formally we can define it as the repeated application of a recursive procedure or definition.

There are all the definitions we required. Let's get into stuff like why we even need this.

Why do we need recursion at all?

Let's understand why we define functions in our codes -

We define functions so we can break our code into smaller logical units.

Let's say you have 2 code snippets which calculate the digits of a number and check if the code is even or not like this

void doing_something(int n){
    int cnt = 0;
    while(n > 0){
        cnt++;
        cnt/=10;
    }
    bool is_even = cnt % 2 == 0;
}

Now it is quite easy to understand but generally, we have more complicated code in competitive programming as well as in projects.

We can actually break code into smaller units

int count_digits(int n){
    int cnt = 0;
    while(n > 0){
        cnt++;
        n /= 10;
    }
    return cnt;
}
bool is_even(int n){
    return n % 2 == 0;
}
void doing_something(int n){
    int cnt = count_digits(n);
    bool is_even = is_even(cnt);
}

Advantages of breaking into smaller logical units are

1. doing_something() method is more readable now, and sometimes we don't care how something is happening. For example, we want digit count in doing_something, we don't care how it is happening here. Using method provides that abstraction of just calling a function. Note: Not caring means we believe it will be correct and focus on the logic we need to do here. For example, we can be calling a method to connect to the database, we don't care how it is actually doing it but only that we are connecting to the database.

2. Re-usable methods, we do not need to write complete logic again to do something.

3. Fewer errors and easier debugging. Let's say our digit_count method is returning the wrong result, we have to only edit in one place.

Basic point is that we break code into functions and when we call that function it will return the correct result.

If it does not provide the correct result we fix the function that is not giving the correct result.

But how does it comes down recursion?

Let's take an example of running laps in a park. Your coach instructs you to run 10 laps. After 1 lap you are tired, but you instruct yourself 9 laps and similarly 8, 7, ... 1, and then when you are at 0 laps, you stop.

If you believe your coach to be the main() method, calling the run_laps() method, then run_laps() is further calling itself for further laps.

Something like this

void run_laps(int lap_count){
    if(lap_count == 0){
        // code to stop here or simply
        return;
    }
    //code to run 1 lap
    run_a_lap();
    run_laps(lap_count - 1);
}

How does recursion help us solving problems in competitive programming?

Let's say we have to calculate the nth Fibonacci number

We define nth fibonacci number as

F(N) = F(N-1) + F(N-2)

or as

nth fibonacci = (n-1)th fibonacci + (n-2)th fibonacci

Note: F(0) = 1, F(1) = 1

To solve this let's say we create a method that calculates nth Fibonacci like this (empty for now)

int fibonacci(int n){
}

We know two base cases, let's add them

int fibonacci(int n){
    if(n == 0 || n == 1)return 1;
}

We assume Fibonacci(n) returns the correct result, so Fibonacci(n-1) will also return the correct result answer so will Fibonacci(n-2).

So we can simply return sum of fibonacci(n-1) and fibonacci(n-2) for fibonacci(n);

int fibonacci(int n){
    if(n == 0 || n == 1)return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

Difference between iterative code and recursive code | Something for college notes xD

Iterative code is actually doing it just in a loop

For example, Fibonacci can be solved in a loop as well like this

int prev = 1;
int prev2 = 1;
int cur = 1;
for(int i = 2; i <= n; i++){
    cur = prev + prev2;
    prev2 = prev;
    prev = cur;
}

Recursion	Iteration
Recursion uses selection structure.	Iteration uses repetition structure.​
Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on some condition (base case) and Infinite recursion can crash the system.	An infinite loop occurs with iteration if the loop condition test never becomes false and Infinite looping uses CPU cycles repeatedly.​
Recursion terminates when a base case is recognized.	An iteration terminates when the loop condition fails.​
Recursion is usually slower than iteration due to the overhead of maintaining the stack.	An iteration does not use the stack so it's faster than recursion.
Recursion uses more memory than iteration.	Iteration consumes less memory.
Recursion makes the code smaller.	Iteration makes the code longer.

You don't need to remember it too much, it is just here for theory. You can come back to it in the future. Read it to see if there are any new terms here, just try to understand. Even I don't remember this theory much. I took it from tutorialspoint.com :p

How to write recursion code?

To write recursion code you need to do the following

1. Break the problem into smaller parts For Example - Fib(n) could be solved by calculation Fib(n-1) and Fib(n-2)

2. Write Bases cases to stop breaking the problem into further smaller parts For Example - We hard-coded answers for cases of Fib(0) and Fib(1)

3. Merge results from smaller parts to the answer of current parts For Example - Adding result of Fib(n-1) and Fib(n-2) gives answer for Fib(n)

Let's solve a problem using recursion

Let's solve this problem - Find Nth Factorial using recursion.

You can find my complete implementation here

Step 1 - Breaking into smaller problems

We know that N! (N factorial) = N x N-1 x N-2 x ... x 1

Therefore (N-1)! = N-1 x N-2 x ... x 1

So we can write N! = N x (N-1)!

Hence Fact(N) can be calculated if we calculate Fact(N-1)

int factorial(int n){
    return factorial(n-1);
}

Step 2 - Write Bases Cases

We need to stop at some point. We know that Factorial(1) = 1,

so we can use this as the base case

int factorial(int n){
    if(n == 1)return 1;
    return factorial(n-1);
}

Step 3 - Merging Smaller Cases to find results for the correct problem

If we find the answer for Factorial(N-1), we need to multiply it with N in order to get the answer for Factorial(N).

int factorial(int n){
    if(n == 1)return 1;
    return n * factorial(n-1);
}