Implementing math recursion formula

Question

I have such a formula:

I'm tryging to learn how to implement recursion in C, and wrote this code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int a(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    if(n%2 == 0)
        return a(2*(n-1)) + a(2*(n-2));
    if(n%2 != 0)
        return a(2*n) - a(2*(n-1));
}

int main()
{
    int n = 3;
    printf("%d\n", a(n));

    return 0;
}

However, my code gives me segmentation fault, what's the problem?

Put printf("n = %d\n", n); at the beginning of the a function. Then run your program again and you will find out what happens. — Jabberwocky
– Jabberwocky, Commented Feb 18, 2016 at 14:05
I see the problem, but first a question: For the odd case, the image shows that the previous values are subtracted, not added. Your code (both versions), on the other hand, adds for both the even and the odd case. Which is correct? Do you want to subtract for the odd cases? This won't fix your segmentation fault, but the answer is needed to correct your code. — Tom Karzes
– Tom Karzes, Commented Feb 18, 2016 at 14:06
@TomKarzes: It's my mistake. I would like to implement the formula. I will edit the code. — Brian Brown
– Brian Brown, Commented Feb 18, 2016 at 14:07
Why exactly do you need to use recursion? Is the program too fast or consuming too little memory? — Lundin
– Lundin, Commented Feb 18, 2016 at 14:15

Felix M. · Accepted Answer · 2016-02-18 14:20:51Z

3

You want to do this:

int a(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    if(n%2 == 0)
        return a(n-1) + a(n-2);
    else
        return a(n-1) - a(n-2);
}

What you have there is (mathematically) called a sequence. Please take a look at the indices in your sequence then it probably makes more sense. You cannot just substitute 2n-1 there and FOR SURE not 2*(n-1) which is just wrong.

Furthermore: The recursion is not the best way to implement that if you want to expand your sequence into a series. Then you better should start with 0, 1 and do that stuff iteratively.

Hope that helps

edited Feb 18, 2016 at 14:20

answered Feb 18, 2016 at 14:12

Felix M.

2561 silver badge6 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Tom Karzes Over a year ago

This is correct. It's not as efficient as my version, but it works.

Felix M. Over a year ago

Your right. You should replace the != 1 case with an else like Tom Karzes did. I'll edit for future readers.

user3185968 Over a year ago

Sorry, I was confused. But for an optimizing compiler replacing the last condition with else will likely not make a difference.

Felix M. Over a year ago

Wont trust in that. If you can take some optimizing stuff off the compilers shoulder like that, you probably should think of it beforehand. I never "trust" in compilers optimizing everything.

Tom Karzes · Accepted Answer · 2016-02-18 14:14:13Z

2

Try this:

int a(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    if(n%2 == 0)
        return a(n-1) + a(n-2);
    else
        return a(n-1) - a(n-2);
}

The problem is that the n in your function is not the same as the n in your image, which is why it's creating confusion. The thing to realize is that in the even case, you sum the previous two values, and in the odd case you subtract them, as shown above.

answered Feb 18, 2016 at 14:14

Tom Karzes

24.3k3 gold badges28 silver badges46 bronze badges

Comments

Mathieu · Accepted Answer · 2016-02-18 14:13:15Z

1

Your problem comes from indexes:

int a(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    if(n%2 == 0)
        return a(n-1) + a(n-2);
    if(n%2 != 0)
        return a(n-1) - a(n-2);
}

answered Feb 18, 2016 at 14:13

Mathieu

10.1k7 gold badges38 silver badges50 bronze badges

Collectives™ on Stack Overflow

Implementing math recursion formula

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related