CODEWITHSUNDEEP
c++recursionfibonaccifactorial
Alter Ego
Alter Ego

Reputation: 39

Fibonacci series in C++ : Control reaches end of non-void function

while practicing recursive functions, I have written this code for fibonacci series and (factorial) the program does not run and shows the error "Control reaches end of non-void function" i suspect this is about the last iteration reaching zero and not knowing what to do into minus integers. I have tried return 0, return 1, but no good. any suggestions?

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <ctime>
using namespace std;

int fib(int n) {
    int x;
        if(n<=1) {
            cout << "zero reached \n";
            x= 1;
        } else {
            x= fib(n-1)+fib(n-2);
            return x;
        }
    }




int factorial(int n){
    int x;
    if (n==0){
        x=1;
       }
    else {
            x=(n*factorial(n-1));
            return x;
        }

    }

Upvotes: 0

Views: 3814

Answers (8)

Valerii Salov
Valerii Salov

Reputation: 1

While the author is asking what is technically wrong with the recursive function computing the Fibonacci numbers, I would like to notice that the recursive function outlined above will solve the task in time exponentially growing with n. I do not want to discourage creating perfect C++ from it. However, it is known that the task can be computed faster. This is less important for small n. You would need to refresh the matrix multiplication knowledge in order to understand the explanation. Consider, evaluation of powers of the matrix:

power n = 1  | 1 1 |
             | 1 0 | = M^1

power n = 2  | 1 1 |   | 1 1 |   | 2 1 |
             | 1 0 | * | 1 0 | = | 1 1 | = M^2

power n = 3  | 2 1 |   | 1 1 |   | 3 2 |
             | 1 1 | * | 1 0 | = | 2 1 | = M^3

power n = 4  | 3 2 |   | 1 1 |   | 5 3 |
             | 2 1 | * | 1 0 | = | 3 2 | = M^4

Do you see that the matrix elements of the result resemble the Fibonacci numbers? Continue

power n = 5  | 5 3 |   | 1 1 |   | 8 5 |
             | 3 2 | * | 1 0 | = | 5 3 | = M^5

Your guess is right (this is proved by mathematical induction, try or just use)

power n      | 1 1 |^n         | F(n + 1) F(n)     |
             | 1 0 |   = M^n * | F(n)     F(n - 1) |

When multiply the matrices, apply at least the so-called "exponentiation by squaring". Just to remind:

      if n is odd (n % 2 != 0), then M * (M^2)^((n - 1) / 2)
M^n = 
      if n is even (n % 2 == 0), then (M^2)^(n/2)

Without this, your implementation will get the time properties of an iterative procedure (which is still better than exponential growth). Add your lovely C++ and it will give a decent result. However, since there is no a limit of perfectness, this also can be improved. Particularly, there is a so-called "fast doubling" for the Fibonacci numbers. This would have the same asymptotic properties but with a better time coefficient for the dependence on time. When one say O(N) or O(N^2) the actual constant coefficients will determine further differences. One O(N) can be still better than another O(n).

Upvotes: 0

Valerii Salov
Valerii Salov

Reputation: 1

There is nothing wrong with if-else statements. The C++ code applying them looks similar to other languages. In order to emphasize expressiveness of C++, one could write for factorial (as example):

int factorial(int n){return (n > 1) ? n * factorial(n - 1) : 1;}

This illustration, using "truly" C/C++ conditional operator ?:, and other suggestions above lack the production strength. It would be needed to take measures against overfilling the placeholder (int or unsigned int) for the result and with recursive solutions overfilling the calling stack. Clearly, that the maximum n for factorial can be computed in advance and serve for protection against "bad inputs". However, this could be done on other indirection levels controlling n coming to the function factorial. The version above returns 1 for any negative n. Using unsigned int would prevent dealing processing negative inputs. However, it would not prevent possible conversion situation created by a user. Thus, measures against negative inputs might be desirable too.

Upvotes: 0

Oenotria
Oenotria

Reputation: 1702

Presumably the factorial function should be returning n * factorial(n-1) for n > 0.

x=(factorial(n)*factorial(n-1)) should read x = n * factorial(n-1)

Upvotes: 0

Sebastian Mach
Sebastian Mach

Reputation: 39089

Sometimes, your compiler is not able to deduce that your function actually has no missing return. In such cases, several solutions exist:

Assume

if (foo == 0) {
    return bar;
} else {
    return frob;
}

Restructure your code

if (foo == 0) {
    return bar;
}
return frob;

This works good if you can interpret the if-statement as a kind of firewall or precondition.

abort()

(see David Rodríguez's comment.)

if (foo == 0) {
    return bar;
} else {
    return frob;
}
abort(); return -1; // unreachable

Return something else accordingly. The comment tells fellow programmers and yourself why this is there.

throw

#include <stdexcept>

if (foo == 0) {
    return bar;
} else {
    return frob;
}

throw std::runtime_error ("impossible");

Not a counter measure: Single Function Exit Point

Do not fall back to one-return-per-function a.k.a. single-function-exit-point as a workaround. This is obsolete in C++ because you almost never know where the function will exit:

void foo(int&);

int bar () {
    int ret = -1;
    foo (ret);
    return ret;
}

Looks nice and looks like SFEP, but reverse engineering the 3rd party proprietary libfoo reveals:

void foo (int &) {
    if (rand()%2) throw ":P";
}

Also, this can imply an unnecessary performance loss:

Frob bar ()
{
    Frob ret;
    if (...) ret = ...;
    ...
    if (...) ret = ...;
    else if (...) ret = ...;
    return ret;
}

because:

class Frob { char c[1024]; }; // copy lots of data upon copy

And, every mutable variable increases the cyclomatic complexity of your code. It means more code and more state to test and verify, in turn means that you suck off more state from the maintainers brain, in turn means less maintainer's brain quality.

Last, not least: Some classes have no default construction and you would have to write really bogus code, if possible at all:

File mogrify() {
    File f ("/dev/random"); // need bogus init
    ...
}

Do not do this.

Upvotes: 0

johnsyweb
johnsyweb

Reputation: 141770

"Control reaches end of non-void function"

This is a compile-time warning (which can be treated as an error with appropriate compiler flags). It means that you have declared your function as non-void (in this case, int) and yet there is a path through your function for which there is no return (in this case if (n == 1)).

One of the reasons that some programmers prefer to have exactly one return statement per function, at the very last line of the function...

    return x;
}

...is that it is easy to see that their functions return appropriately. This can also be achieved by keeping functions very short.

You should also check your logic in your factorial() implementation, you have infinite recursion therein.

Upvotes: 1

Gorpik
Gorpik

Reputation: 11028

The else section of your factorial() function starts:

    x=(factorial(n)*factorial(n-1));

This leads to infinite recursion. It should be:

    x=(n*factorial(n-1));

Upvotes: 0

Sam DeHaan
Sam DeHaan

Reputation: 10325

In your second base case (n == 1), you never return x; or 'return 1;'

Upvotes: 0

Kaganar
Kaganar

Reputation: 6570

Change

else if (n==1)
        x=1;

to

else if (n==1)
        return 1;

Then fib() should work for all non-negative numbers. If you want to simplify it and have it work for all numbers, go with something like:

int fib(int n) {
    if(n<=1) {
        cout << "zero reached \n";
        return 1;
    } else {
        return fib(n-1)+fib(n-2);
    }
}

Upvotes: 3

Related Questions