// functions and recursions, a tasteful combination

With most of the basics tackled, I moved on to functions as well as another concept that comes with it and is fundamental to a lot of languages, recursion. Because of the ability of functions to contain a problem and define it using parameters, we are able to implement recursion whose whole idea is to divide the problem into simpler instances of itself. In a more practical sense, the parameterization that's brought by functions blends well with recursion, and this can be done by using simpler parameters repeatedly until it reaches a base case from which it terminates.

The way I see it, functions and recursions are the bread-and-butter of programming when we try to solve problems through the divide-and-conquer approach.

Like the last post, these concepts are mostly familiar to me but there are also bits of the syntax that are specific to C only, which I will briefly mention by the end of this post.

The Problem

Create a program that asks for an integer n and lists all prime numbers from 1 to n. Start by a creating recursive function that determines whether an integer is prime or not. Next, ask for an integer n, then loop through all the integers from 1 to n. Check each integer if it is prime by using the function earlier then print the integer if it is prime.

Looks simple enough. Breaking the problem down, there are three things that I need to do:

• recursive function that checks if a number is prime
• user input for a number n
• loop from 1 to n that calls the function and prints the number if it's prime

For this program, I only need a single int variable n.

The Recursive Function
Starting with the hard bit of the program, I first needed to figure out how to check the number if it's prime and then express that recursively. Initially, I thought of dividing the numbers by the first four prime numbers, however, I realized that this method only works for numbers below 100. Since I need a more general description for prime numbers, I looked for its definition.

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

From this, we can infer that primes can only be expressed as a product of 1 and itself, and any number that can be divided by any smaller number means it is not a prime. Iteratively, this is easy to do since I can just make a loop dividing num from num - 1 to 2, unfortunately, this is not the case with recursion.

Luckily, recursive functions, in general, can be divided into two parts: the base case and the recursive case. The base case is essentially the predefined outcome for the simplest version of the problem, hence base, whereas the recursive case reduces the parameters of the next function call until we get to the base case. The base case is very important as it decides when should the program stop calling itself (since otherwise, the function would continue on and on).

For example, a Fibonacci sequence is a sequence where each number is the sum of the two previous ones, but since we don't know what the "two previous ones" mean, we have to define it ourselves, and that acts as the base case.
Recursive Case:
F_n = F_{n - 1} + F_{n - 2}
Base Cases:
F₁ = 1
F₂ = 1

Since the function should check if a number n is divisible by numbers less than num, my function will have two parameters, int num and int div with div being the parameter that will be reduced every recursive call.

int isPrime(int num, int div);

In this problem, if the function finds a number that can divide num, it should immediately conclude that the number is not prime, however, if it haven't, it should continue looking for a smaller number by putting div - 1 as the new parameter. This will be the recursive case.

if (num % div == 0) {
    return 0; // num is not prime
} else {
    return isPrime(num, div - 1);
}

On the other hand, the logical base case would be when div is equal to 1 because that would mean that function have gone through all the numbers and found nothing that can divide num. Overall:

int isPrime(int num, int div) {
    // BASE CASE
    if (div == 1) {
        return 1; // num is prime
    // RECURSIVE CASE
    } else {
        if (num % div == 0) {
            return 0; // num is not prime
        } else {
            return isPrime(num, div - 1);
        }
    }
}

The Other Parts
For the user input, I simply added a prompt for the user then used scanf as usual, storing it in n. After that, I added the loop that will go through all the numbers from 2 to n and call the function. If the function returns 1, it should print the number.

int n;
printf("Enter a positive integer: ");
scanf("%d", &n);

printf("\nThe prime numbers from 1 to %d are: ", n);
for (int i = 2; i <= n; i++) {
    if (isPrime(i, i - 1) == 1) {
        printf("%d ", i);
    }
}

One thing that I haven't mentioned yet is that in C, the compiler issues out a warning when a function is called before it was declared. The order doesn't really matter because the program can run just fine, but it helps with efficiency and memory consumption as the program doesn't need to pass (read the code) more than once. So, either declare the function below main or add a prototype of the function on top of the code.

Conclusion
All in all, this has been a nice refresher for me about functions and recursions, and it's definitely nice to see them in the context of C. But aside from that, I had a glimpse of how the compiler works with respect to the functions declared on the program, which is new knowledge from me. With regards to recursion, obviously, it's overkill to use recursion for a simple loop as recursion tends to be costly, so for every problem that involves repetition, I believe that as a programmer, it is good practice that we use these concepts only whenever it is appropriate.