C++

Forum

 
recursive function

hassan236 (18)
There is the recursive function in my program for finding the factorial of the number. In this program i want to find the factorial of 4. I stored the value 4 in to the variable n through cin. While writing a factorial function, we can stop recursive calling when n is 2 or 1. Below is the code of my program for finding the factorial of the number.
#include <iostream>
using namespace std;
long factorial(long );
int main()
{
long n;
cin>>n;
cout<< "factorial= "<<factorial(n);
}
long factorial(long n)
{
if(n<=2)
return 2;
else
return n*factorial(n-1);
}
The output of this program in console window is factorial= 24 which is the correct output. The return statement causes a function to end immediately and a function may send a value back to the part of the program that called the function. There are two return statements in the called function of the above program. The called function is returning the value 24 to the calling program which is the factorial of 4. The called function is not returning any value of the first return statement to the calling program. I modified the above program. Below is the code of the program in which i changed the first return statement of the called program.
#include <iostream>
using namespace std;
long factorial(long );
int main()
{
long n;
cin>>n;
cout<< "factorial= "<<factorial(n);
}
long factorial(long n)
{
if(n<=2)
return 1;
else
return n*factorial(n-1);
}
The output of this program in console window is factorial= 12 which is not the correct output. Why the called function is returning the value 12 to the calling program instead of 24 after changing the return statement after conditional statement which is if(n<=2)?



jonnin (11437)
you get 12 because you do not multiply by 2 anymore for 2.
so you call it with 4.. which calls it with 3, 2, and 1 ...
in the top one, if its 2, you return 2, so you get 2*3*4 = 24.
in the bottom one, if its 2, you return 1, so you get 1* 3*4

the top one is correct unless you call it with factorial 0 or 1. Those are special cases you need to handle. 0 -> 1, 1 ->1 , 2->2, 3->6, 4 -> 24 ... and so on.
Last edited on
seeplus (6589)
When posting code, it's helpful for those trying to read it if code tags are used:


[code]
//formatted code goes here
[/code]


Also, when asking for input from the console, it's usual for a prompt to be provided sttaing what input is expected.

Consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>

using Num = unsigned long long;

[[nodiscard]]
inline Num factorial(Num n) {
	return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
	Num n {};

	std::cout << "Enter number for factorial: ";
	std::cin >> n;

	std::cout << "factorial= " << factorial(n) << '\n';
}



Enter number for factorial: 4
factorial= 24

Last edited on
keskiverto (10402)
1
2
3
4
5
6
7
 
long factorial(long n)
{
    if (n<=2)
        return X; // should X be 1 or 2?
    else
        return n*factorial(n-1);
}

We call factorial(4)
According to code above, its value is:
4*factorial(3)

It has call factorial(3)
According to code above, its value is:
3*factorial(2)
that is, the value of factorial(4) is
4*3*factorial(2)

The factorial(2) returns X
The real value of factorial(4) is therefore:
4*3*X


On the other hand, the factorial of 2 is also 2*1, that is 2. Not 1.
The factorial of 4 is 4*3*2*1, not 4*3*1.
Geckoo (362)
Hello. Respectfully you have to format your code in order to get some readability. It's good for you - it's good for us. Unsigned long long integer is the largest (64 bits) integer data type in C++. The maximum you can get is 18446744073709551615. Out of this integer your value is truncated. So you should check your entry.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
// https://en.wikipedia.org/wiki/Factorial
#include <iostream>

unsigned long long factorial(int n) {
	return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() 
{
    int n;
    std::cout << "Enter number for factorial (max 20) : ";
    std::cin >> n;

    n > 20 ? std::cout << "no more 20 I said!" << std::endl 
           : std::cout << "factorial = " << factorial(n) << std::endl;
	
    return 0;
}


Out of context, when I write a large code, I like to put useful functions inside a structure or a class as static members. This way I can easily reuse them. Just a little tip for friends :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>

struct utility {
    // https://en.wikipedia.org/wiki/Factorial
    static unsigned long long factorial(int n) {
        return n <= 1 ? 1 : n * factorial(n - 1);
    }
    // display date/time
    static void displayDate() {
        std::cout << __TIMESTAMP__ << std::endl;
    }
};

int main()
{
    int n;
    utility::displayDate();
    std::cout << "Enter number for factorial (max 20) : ";
    std::cin >> n;

    n > 20 ? std::cout << "no more 20 I said!" << std::endl 
           : std::cout << "factorial = " << utility::factorial(n) << std::endl;

    return 0;
}


For fun :)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>

 // https://en.wikipedia.org/wiki/Factorial
 unsigned long long factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

int main()
{
    int f = 20;

    for(int i = 1; i <= f; ++i)
        std::cout << "factorial (" << i << "!) = " << factorial(i) << std::endl;

    return 0;
}



factorial (1!) = 1
factorial (2!) = 2
factorial (3!) = 6
factorial (4!) = 24
factorial (5!) = 120
factorial (6!) = 720
factorial (7!) = 5040
factorial (8!) = 40320
factorial (9!) = 362880
factorial (10!) = 3628800
factorial (11!) = 39916800
factorial (12!) = 479001600
factorial (13!) = 6227020800
factorial (14!) = 87178291200
factorial (15!) = 1307674368000
factorial (16!) = 20922789888000
factorial (17!) = 355687428096000
factorial (18!) = 6402373705728000
factorial (19!) = 121645100408832000
factorial (20!) = 2432902008176640000

@seeplus you used an inline function - and I guess that we should. Without it, do you think that there is a waste of memory - even using a recursive function? I have a doubt. Thanks ++
Last edited on
jonnin (11437)
I too am curious about the inline, but..
the zero propagation makes this interesting for use with floating point values, or pseudo-floating point values where you keep the power of 10 aside from the other digits. At 'only' 20 you already use 4 of your digits as zeros. I don't know what it looks like in binary, but there is probably a similar redundancy if you spent some time looking at it... after all, every value after the first few are shifted from a 2, 4, 8 value..
anyway, for whatever nutty reason, you can squeeze a few more out of it by some sort of zero reduction, in whatever base.
unfortunately, I don't know that double gains much, even though it 'drops' the zeros it doesn't have the sig figs to keep up so you approximate pretty soon.
Geckoo (362)
It seems to me that there are some alternatives un order to work with bigger integers than unsigned long long. Something like __uint128 ++
Last edited on
JLBorges (13770)
> you used an inline function - and I guess that we should. Without it, do you think that there is a waste of memory ...

In pre-historic days, the primary intent of the inline specifier for a function was to provide a strong hint to the optimiser - 'inline substitution of this function is preferred'. Over a period of time, as optimisers became more intelligent, this usage of inline has become an obsolete relic.

cppreference:
... compilers are free to use inline substitution for any function that's not marked inline, and are free to generate function calls to any function marked inline. Those optimization choices do not change the rules regarding multiple definitions and shared statics listed above.

(since C++17)
Because the meaning of the keyword inline for functions came to mean "multiple definitions are permitted" rather than "inlining is preferred", that meaning was extended to variables.
https://en.cppreference.com/w/cpp/language/inline#Explanation
Geckoo (362)
Thank you @JLBorges for the clever answer.
There are many other ways to do factorial computations. Some of them are very interesting using vector and multiplication ++

https://www.geeksforgeeks.org/factorial-large-number/
Last edited on
lastchance (6980)
Like so:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;


const int UNIT = 1000000000;
const int WIDTH_UNIT = 9;


void simplify( vector<unsigned long long> &V )
{
   unsigned long long carry = 0;
   for ( int i = 0; i < V.size() || carry > 0; i++ )
   {
      if ( i < V.size() ) carry += V[i];
      unsigned long long block = carry % UNIT;
      carry /= UNIT;
      if ( i < V.size() ) V[i] = block;
      else                V.push_back( block );
   }
}


int main()
{
   int N = 170;
   vector<unsigned long long> F = { 1 };

   for ( int i = 1; i <= N; i++ )
   {
      for ( auto &e : F ) e *= i;
      simplify( F );
   }
   cout << "Factorial(" << N << ") = ";
   cout << F.back();   for ( int i = F.size() - 2; i >= 0; i-- ) cout << setw( WIDTH_UNIT) << setfill( '0' ) << F[i];
   cout << "\n\n" << setprecision( 15 ) << tgamma( N + 1.0 ) << '\n';
}

Last edited on
seeplus (6589)
Something like __uint128


That's not yet C++ standard and isn't supported by all compilers (eg not by VS).

If a integral number larger than allowed for with unsigned long long (usually uint64) then there are various large integer libraries available.

@seeplus you used an inline function


As per JLBorges answer for C++17 re permitted multiple definitions, we mark all of our 'utility' functions inline for this reason. As factorial is recursive, the compiler would ignore the 'original' meaning of inline anyhow as you can't 'inline' code for a run-time recursive function.

Note lastchance's usage of tgamma() to obtain the factorial. It uses an argument of N + 1 as tgamma() calculates (N - 1)! for natural numbers.

https://en.cppreference.com/w/cpp/numeric/math/tgamma

PS Changed wording as per JLBorges post below to run-time recursive.

Last edited on
JLBorges (13770)
> you can't 'inline' code for a recursive function.

Inline substitution may be performed for any function, including recursive functions.
The only requirement is that the observable behaviour of the program is not changed. 

1
2
3
4
5
6
7
8
9
10
11
 
static unsigned long long fact( unsigned int n ) noexcept 
{ return n < 2 ? 1 : n * fact(n-1) ; } // recursive

unsigned long long foo() noexcept // evaluated at compile time
{ return fact(10) ; } // return 3628800

unsigned long long bar() noexcept // evaluated at compile time
{ return fact(12) / fact(10) ; } // return 132

unsigned long long baz( unsigned int n ) noexcept 
{ return fact(n) ; } // loop (inline substitution of the recursive function fact)

https://gcc.godbolt.org/z/MbKqvT1z6
seeplus (6589)
OK - for a function that can be evaluated at compile time. My bad wording - I should have said run-time inline for recursion.

Also, the functions can be marked as constexpr

1
2
3
4
5
6
7
8
9
10
 
using Num = unsigned long long;

[[nodiscard]]
constexpr Num factorial(Num n) noexcept {
	return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
	static_assert(factorial(5) == 120);
}

Last edited on
JLBorges (13770)
> OK - for a function that can be evaluated at compile time.

Inline substitution may be performed for any function, as long as the observable behaviour of the program is not changed.

1
2
3
4
5
 
static unsigned long long fact( volatile unsigned int n ) noexcept 
{ return n < 2 ? 1 : n * fact(n-1) ; } // can't be evaluated at compile-time

unsigned long long baz( unsigned int n ) noexcept 
{ return fact(n) ; } // loop (inline substitution of the recursive function fact)

https://gcc.godbolt.org/z/jdczP3jWW
seeplus (6589)
Yes - any modern optimising compiler (if instructed) is free to optimise the generated code anyhow it thinks appropriate whilst maintaining the original program behaviour. As JLBorges mentioned above, the original purpose of inline as an optimisation hint to the compiler is now largely redundant as modern C++ compilers are so much better at optimisation than their historical versions - with the C++17 meaning prevalent.
Ganado (6809)
Also worth noting that sometimes inline (referring to "forcing" inline via the compiler) can make things faster, but other times it can make things slower (due to instruction cache size limits, I think). It can sometimes be a delicate balance.
seeplus (6589)
inline doesn't and never has forced inlining for the compiler. It was only a guide to the compiler to consider inlining that function. The compiler was/is quite at liberty to ignore it. Also if the code is inlined by the compiler this can make the size of the generated code larger. If the size of the generated code file is important then you may not want functions inlined. With VS you can instruct the compiler to optimize/favour either speed or size.
jonnin (11437)
visual has the nonstandard force inline which supposedly does inline regardless -- unless its not possible. Its not generally possible to inline recursion if the recursive calls are actually made, and there are similar circumstances where it can't do it.

you can also skip all this and exploit #include or other macros to force inline a bit of code in extreme circumstances.
JLBorges (13770)
oggin (51)

This recursive factorial will run out of stack memory somewhere between 14000 and 15000.
It is slowed down a bit by recursion.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
 

#include<string>
#include<iostream>

std::string operator * ( std::string a, std::string b) {
	#define ltrim0(s)  (s).erase(0, (s).find_first_not_of("0"))
	int flag=0;int La=a.length();int Lb=b.length();
	char n,carry,ai;
	std::string c;
	c.resize(La+Lb,'0');
	if (La>Lb) 
	{
		std::swap(a,b);std::swap(La,Lb);
	}
     for (int i=La-1;i>=0;i--)
     {
        carry=0;ai=a[i]-48 ;  
        for(int j=Lb-1;j>=0;j--)
    {
     n = ai * (b[j]-48) + (c[i+j+1]-48) + carry;
     carry =n/10;c[i+j+1]=n % 10+48;
}
    c[i]+=carry;
    }
	return ltrim0(c);
}

const std::string factorial(int x) {
	#define str(n) std::to_string ((n))
	if(x<=1) return "1";
	return (str(x) * factorial(x-1));
}
    
    
    int main()
    {
    std::cout<<factorial(1000)<<std::endl;
    std::cout<<"press return to end . . ."<<std::endl;
    std::cin.get();
    	return 0;	
    }

Last edited on
Topic archived. No new replies allowed.