Write a recursive function to print first N even natural numbers in C-CodePudding

even though I think my syntax is correct, the compiler shows a segmentation fault, and I don't get why.

#include<stdio.h>

void even(int n);

int main() {
    even(20);
    return 0;
}

void even(int n) {
    if (n % 2 == 0) {
        even(n - 2);
        printf(" %d", n);
    }
}

I tried to print even natural numbers using recursions in c, but it does not print anything and just resets my compiler, and when I ran it on an online code runner it displayed a segmentation fault. it would be helpful if someone could point out any syntax errors or explain to me how can I solve this question

CodePudding user response：

It's not that important but still something you need to know...

When you write

the compiler shows a segmentation fault

it's not correct. Compilers don't give segmentation faults for your program. A compiler turns your code into an executable program file (assuming that your code has no syntax errors). The segmentation fault comes when you execute your program if your program is doing something illegal or something that can't be handled by your system.

So what is wrong with your program?

A recursive function must have a condition that makes the recursion stop. In your program there is the condition

if (n % 2 == 0) {

that controls whether recursion shall go on or stop. What this mean is:

if n is even go on with recursive calls
if n is odd stop recursive calls

So calling your even function using an odd value like even(5) will immediately stop recursion, i.e. nothing will be printed at all. That is not what you want...

Calling your even function with an even number like even(20) will give a recursive call.

Your recursive call is

even(n - 2);

Since n is even n - 2 will also be even, i.e. you'll do a recursive call using a new even number as argument. That will lead to yet another recursive call using a new even number as argument. And that will lead to yet another recursive call using a new even number as argument. And that will lead to yet another recursive call using a new even number as argument. And ....

It will never stop! It will go on forever... unless something bad happens - like a segmentation fault for instance.

And that is what happened in your case. The likely explanation is that you ran out of stack memory. Every recursive call used "a little" stack memory and due to doing recursive calls again and again, all stack memory was used and your system responded with a segmentation fault.

You can fix that by changing the condition so that it only accepts values where n is greater than zero. Like

if (n > 0 && n % 2 == 0) {

If you do that you won't get segmentation fault for even(20). The output will be:

2 4 6 8 10 12 14 16 18 20

Unfortunately that is not exactly what you wanted. The code only printed 10 numbers. You wanted it to print 20 numbers. So the "fix" is not fully what you want. And further, odd arguments is still not working.

So it's time to reconsider the program design.

Let's write a recursive function that will do "something" N times.

It could look like:

void even(int n)
{
    if (n <= 0)
    {
        // End recursion
        return;
     }

     printf("Doing something... %d\n", n);

     // Do recursive call with decremented argument
     even(n - 1);
}

Calling this function with even(5) will generate the output:

Doing something... 5
Doing something... 4
Doing something... 3
Doing something... 2
Doing something... 1

That's not too bad... it did something exactly 5 times as requested. Now we just need to do the right thing, i.e. print the next even natural number. That sound easy but there is a problem... What is the next natural number?

With the current code there is no way of knowing that.. We need to pass some extra information in each recursive call. But we don't want to change the prototype of the function. It has to void even(int n);

The common solution is to introduce a helper function that handles the "extra information" Like:

#include<stdio.h>

void even(int n);

int main() 
{
    even(5);
    return 0;
}

void even_recursive(int next, int n)
{
    if (n <= 0)
    {
        // End recursion
        return;
    }

    printf("next %d\n", next);

    // Do recursive call with new next-value and decremented n argument
    even_recursive(next   2, n - 1);
        
}

void even(int n)
{
    even_recursive(2, n);
}

Output

next 2
next 4
next 6
next 8
next 10

The first 5 even natural numbers as required.

BTW:

The even_recursive function can also be written as:

void even_recursive(int next, int n)
{
    if (n > 0)
    {
        printf("next %d\n", next);
        even_recursive(next   2, n - 1);
    }   
}

to make it a bit shorter.

CodePudding user response：

A recursive routine must have two behaviors:

For some designated “base” case or cases, it performs the desired operation without calling itself.
For other cases, it performs the desired operation in part by calling itself to perform some reduced version of the operation.

Given an even n, your routine never reaches a base case, because, when n is even, n % 2 == 0 is true, and the routine calls itself with even(n - 2), which passes another even number to itself.

Here is a correct version:

void even(int n)
{
    if (0 < n)
    {
        even(n-1);
        printf("%d\n", 2*n);
    }
}

The base case is when n is zero (or negative). In this base case, the desired operation is to do nothing; zero natural numbers are printed.

The recursive case is when n is positive. In this case, the routine prints the first n even natural numbers in two parts: It calls even(n-1) to print the first n-1 even natural numbers, and then it directly prints the next even natural number.