-3
#include<bits/stdc++.h>
#define big 1000000007
using namespace std;
long long n,k;
int fobo(int);
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        k=fobo(n)%big;
        printf("%d",k);
        printf("\n");
    }
    return 0;
}
int fobo(int m)
{
    if(m==1)
        return 0;
    if(m==2)
        return 1;
    return 3*fobo(m-1)+2*fobo(m-2)+5;
}

The above code is for printing the sum of a special kind of Fibonnacci series following the relation given in the recurrence relation inside the function fobo . The code works fine on my machine but on testing in any online judge , the same code shows SIGSEGV error. There is no use of any arrays in the program , accessing unknown memory that i know of. I guess these are the some of the major requirements for having a SIGSEGV error. I cant find any in here . Please help me in resolving or finding the error.

soumya dubey
  • 63
  • 1
  • 1
  • 10
  • 1
    `hobo(n)` is `fobo`? – Hatted Rooster Feb 15 '16 at 19:42
  • 1
    `#include` aaaaaaaaarrrrrrrrrrrgggggggggghhhhhhhhhhhhh – Lightness Races in Orbit Feb 15 '16 at 19:45
  • `long long n,k; /* ... */ scanf("%d",&n);` Why `long long`? – dxiv Feb 15 '16 at 19:46
  • technically it's not a Fibonacci sequence but rather a sequence with a recurrence relation. Fibonacci refers specifically to the sequence 0, 1, 1, 2, 3, 5, 8, 13, ... where a[n] = a[n-1] + a[n-2]; even the Lucas sequence (2, 1, 3, 4, 7, 11, 18, ...) is not a Fibonacci sequence because it uses different starting numbers. – Jason S Feb 15 '16 at 19:47
  • @PreferenceBean well i am kind of new to the stage of competitive programming . And i have been taught to use it. is it not a good thing ? – soumya dubey Feb 15 '16 at 19:48
  • 1
    It's extraordinarily popular in competitive programming in certain countries, and it drives me crazy. Here's why: http://stackoverflow.com/q/31816095/560648 – Lightness Races in Orbit Feb 15 '16 at 19:50
  • @JasonS i have mentioned in the statement that it is not a Fibonacci series but a modified one. – soumya dubey Feb 15 '16 at 19:51
  • @PreferenceBean oops .. thank you for mentioning out that. will keep this thing noted – soumya dubey Feb 15 '16 at 19:59
  • @soumyadubey -- but it's not a Fibonacci sequence. It's not a "special kind of Fibonacci series". It's almost a [Lucas sequence](https://en.wikipedia.org/wiki/Lucas_sequence) which *does* generalize, except for the "+5" term at the end. I don't know, you can call it what you want, but certain things have specific criteria that make them the way they are, like a sonnet (iambic pentameter + specific rhyme schemes) or a tricycle (three wheels) or Fibonacci sequence (1,1,2,3,5,8,13,etc) and if you modify them, they're no longer that thing. – Jason S Feb 15 '16 at 21:10

1 Answers1

4

If I had to guess, this looks like a stack overflow error. Try feeding 0 into fobo. When that happens, your base cases don't trigger because neither one checks for zero. You then call fobo(-1) and fobo(-2), which will start a chain of recursive calls of the form fobo(-2), fobo(-3), fobo(-4), etc. until you eventually overflow the stack.

To fix this, consider adding in a new base case for 0 in your code, or alternatively put in a general check to handle the case where the input is negative.

EDIT: Based on the comments, I think the main issue here is that if you call this function with a large input, you'll get a stack overflow before the recursion terminates. To address this, consider computing your values bottom-up using dynamic programming. I suspect that's what the question is ultimately trying to get at. Alternatively, use a different recursive formulation amenable to tail call elimination. If you're not familiar with these techniques, look online - you'll learn a lot in the process!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065