Problem with Recursion

Question

Hello, I am running into a little pickle. For class I have an assignment (below), I came up with a solution but I keep getting an error, that says;

"'factorial' : recursive on all control paths, function will cause runtime stack overflow;"

If someone could help me, I've been working on this for about an hour and I'm stumped!

Assignment

Write a C++ program that will output the number of distinct ways in which you can pick k objects out of a set of n objects (both n and k should be positive integers). This number is given by the following formula:

C(n, k) = n!/(k! * (n - k)!)

Your program should use 2 value-returning functions. The first one should be called Factorial and should return n!, The second functions should be called Combinations and should return n!/(k! * (n - k)!). Test your program for different values of n and k 5 times (count-controlled loop).

---

#include <iostream>
using namespace std;
int factorial(int);
int combination(int, int);


void main(void)
{
    int objects, set_number, count; 
    count = 1; 
        while(count <= 5)
        {
            cout << "Please enter in number of objects ";
            cin >> objects; 
            cout << "Please enter in the number of Sets ";
            cin >> set_number;
            count++;
        }

    cout << "The Factorial is " << factorial(set_number) << " & the combination is " << combination << endl;
    cout << endl; 
}

// Factorial 
int factorial(int set_number)
{
    int cal;
    cal = set_number * factorial(set_number - 1);
    return cal; 
}

//  Combination
int combination(int objects, int set_number)
{
    int com_total, cal_set, cal_obj, min_sum, cal_min;

    cal_set = set_number * factorial(set_number - 1);
    cal_obj = objects * factorial(objects - 1);

    //n!/(k! * (n - k)!)
    min_sum = set_number - objects; 
    cal_min = min_sum * factorial(min_sum- 1);
    com_total = cal_set / (cal_obj * cal_min);
    return com_total; 
}

Answer 1

There are two critical elements to a recursive function definition:

• a recursive call to itself
• a termination condition

You appear to be missing the termination condition. How would factorial() quit calling itself forever?

Answer 2

You defined a recursive function (i.e. basically a function that calls itself), but you have not defined an exit condition. You are calling factorial again right before the return, so the function will never end, calling itself over and over again.

You need to add a branch in there, i.e.

if (set_number == 0)
{
   return 1;
}
else
   return set_number * factorial(set_number - 1);

Answer 3

This function will result in infinitive recursion because it never stops calling itself:

int factorial(int set_number)
{
    int cal;
    cal = set_number * factorial(set_number - 1);
    return cal; 
}

This is what you want:

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

Answer 4

You are missing a base case. Factorial should return 1 for set_number <= 1

Answer 5

Your factorial function doesn't terminate on one, it just recurses indefinitely.

int factorial(int set_number)
{
    if (set_number <= 1)
        return 1;
    return set_number * factorial(set_number - 1);
}

Your coding style is also pretty poor, it looks very C-like. There's no need for factorial and combination to be defined after main, and you declare all your vars at the top, no declarations and initializations mixed?

Also, your main function doesn't actually do what the specification says it should - you never initialized or assigned to the combinations variable nor called the combination function, your variables are terribly named, etc. But this is your homework, not mine.

Answer 6

int factorial(int set_number)
{   
   return set_number == 1?1:set_number * factorial(set_number - 1);
}