Thread: difference between a recursive function and a function with a while loop

  1. 06-04-2023 #1
    cooper1200
    cooper1200 is offline
    Registered User
    Join Date
    Apr 2019
    Posts
    808

    difference between a recursive function and a function with a while loop

    i have the following simple program to calculate factorials.
    Code:
    #include <stdio.h>
#include <stdlib.h>

double Factorial( int );
double Fact( int );

int main()
{
    int x = 24;
    double AnswerOne = Factorial( x );
    double AnswerTwo = Fact( x );

    printf("%lf\n", AnswerOne);
    printf("%lf\n", AnswerTwo);

    return 0;
}

double Factorial( int number )
{
    if ( number == 1 )
        return 1;

    return number * Factorial( number - 1 );
}

double Fact( int Num )
{
  double Answer = 1;

  while (Num != 0)
    Answer *= Num--;

  return Answer;
}
    Up to 24! the answers agree but after that they differ Is it the way floating points are stored that causes the error?
  2. 06-04-2023 #2
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    How do they differ?
    Code:
    $ ./a.out 
620448401733239409999872.000000
620448401733239409999872.000000

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    At 25!, I see this

    $ ./a.out
    15511210043330986055303168.000000
    15511210043330983907819520.000000
    15511210043330985984000000 is the true value




    DBL_DECIMAL_DIG is typically 17.

    It doesn't matter how many you print, only the first 17 are meaningful.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
  3. 06-04-2023 #3
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > Is it the way floating points are stored that causes the error?
    Everything about floating point needs you to have your wits about you.

    > return number * Factorial( number - 1 );
    Every result may be pushed into a general purpose register.

    > Answer *= Num--;
    Answer may exist purely in a floating point register until the calculation is complete.

    For example, the x87 numeric co-processor does all it's internal work in 80-bit extended double precision, and only converts to 64-bit double when doing load/store.

    The recursive function is likely to be the product of doubles, whereas the loop is likely to be the product of extended doubles.

    So as soon as x! has more digits than DBL_DECIMAL_DIG, you're on your own.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
  4. 06-04-2023 #4
    cooper1200
    cooper1200 is offline
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    Quote Originally Posted by Salem View Post
    How do they differ?
    Code:
    $ ./a.out 
620448401733239409999872.000000
620448401733239409999872.000000

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    At 25!, I see this

    $ ./a.out
    15511210043330986055303168.000000
    15511210043330983907819520.000000
    15511210043330985984000000 is the true value




    DBL_DECIMAL_DIG is typically 17.

    It doesn't matter how many you print, only the first 17 are meaningful.
    is there one that is bigger but can handle big numbers ie 100!
  5. 06-04-2023 #5
    flp1969
    flp1969 is offline
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    You should compare with <= 1 in Factorial routine because 0!=1. And number must be >=0.
    double has 53 bits of precision, while unsigned long long int has 64. This means while double will hold the scale factor with exponent up to 1023 (and 100! is an integer with 157 digits), it won't hold the precise value due to lack of significant bits. Using double you can calculate 17! because log2(17!)=48.3,. maybe 18! (since log2(18!)=52.5). With unsigned long long int you can calculate up to 20!, because log2(20!)=61.1.

    100! is exactly     93326215443944152681699238856266700490715968264381 62146859296389521759999322991560894146397615651828 625369792082722375825118521091686400
    0000000000000000000000 but using double you'll get 93326215443944102188325606108575267240944254854960571509166910400 40799506424293714863269403045051289804298929694447 4898258737204311236641477561877016501813248 (wrong! use "%.0f" format in printf() to see).

    For double, anything with 16 decimal digits or more is always an approximation, including integers.

    Edit: You can calculate up to 22! with double, but just because the result is filled with zeros to the right. But 23! has more than 16 upper digits, followed by zeros and cannot be represented exactly.
    Last edited by flp1969; 06-04-2023 at 06:11 AM.
  6. 06-04-2023 #6
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > is there one that is bigger but can handle big numbers ie 100!
    Use a bignum library like The GNU MP Bignum Library

    Just because doubles can store numbers up to 10308 doesn't mean you get all 308 digits.
    You get the most significant 17 digits - always!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. converting a for loop to a recursive function
    By wildhare21 in forum C Programming
    Replies: 4
    Last Post: 06-10-2013, 09:28 PM
  2. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  3. how to make a non-recursive function from recursive
    By dyjo in forum C Programming
    Replies: 1
    Last Post: 12-03-2010, 01:54 AM
  4. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 10:13 AM
  5. transforming this loop into a recursive function question
    By transgalactic2 in forum C Programming
    Replies: 17
    Last Post: 01-22-2009, 05:11 AM

Tags for this Thread