Recursion

About recursion. We have seen about functions in previous post is. So what happens if the function calls itself? This is called a recursive function. For example

int sum(int a, int b) {
	return sum(a, b);
}

Let’s look at the function. sum takes 2 variables and returns an int value. But what will happen if he called himself inside? Of course it will run indefinitely and I certainly don’t want that. Is it really necessary?

Would it be clear with an example? For example, we wanted to print from 1 to N. Of course it’s easy to do. We can solve this by using while or for loop. But how do you do it using Recursion?

• So, we have a function that can print a single number, and within that function, we recursively call the function. But when do we stop? We stop when we reach our limit, represented by N. Therefore, our function needs to have two input variables: the first one is the number that we need to print, and the second one is the limit. If the first number is equal to the limit, we don’t need to print anything, and we don’t have to do anything. If they are not equal, we print the first number and then call the function again with the first variable incremented by 1 and the same limit.

• We need to print N, but before that, we print numbers from 1 to N-1. Therefore, we recursively call the function before printing the number. That’s the basic idea. If the number is 0, we don’t need to print anything or make any further calls.

The part written after calling itself will be done after the part called has stopped or finished thinking about it. If it seems complicated, refrain from using loops until you have a good understanding of recursive functions.

//recursive
#include <iostream>
using namespace std;

void rec1( int now, int n ) {
	cout << now << " ";

	if( now == n ) {
		return;
	}
	rec1( now+1, n );
}

void rec2( int now, int x ) {
	if( now == 0 ) {
		return;
	}
	rec2( now-1, x );
	cout << now << " ";
}

int main() {
	int n; cin >> n;
	
	rec1( 1, n ); cout << endl;
	rec2( n, n ); cout << endl;

	return 0;
}