Factorials - Classic Recursion Example

[Arslan7041]

Im having a difficult time understanding HOW exactly the factorial based recursion example works. The example is given in the tutorials section of this website and I've reproduced it below:

#include <iostream>
using namespace std;

long factorial (long a)
{
  if (a > 1)
   return (a * factorial (a-1));
  else
   return 1;
}

int main ()
{
  long number = 9;
  cout << number << "! = " << factorial (number);
  return 0;
}

Now, can someone walk me through this step-by-step? How does this work and why doesn't the output simply display a 1 because of the else return 1?

[Ispil]

Well, the way it works that the function factorial will return, if a is greater than one, the product of a and what factorial would return when passed a-1. The function call of a-1 would then call a-2, and so on, until you end up with a-a+1=1. That factorial function would return one. The factorial function above it (a-a+2) would then multiply a and what was returned (1), yielding 2, and pass it above to factorial(a-a+3). This would repeat until you end up with factorial(a).

This would be a way to represent it:

factorial(a):
  return factorial(a-1)*a:
    return (factorial(a-2)*(a-1))*a:
      return ((factorial(a-3)*(a-2))*(a-1))*a:
        return (((factorial(a-4)*(a-3))*(a-2))*(a-1))*a:
         return...

[andywestken]

Getting to code to speak for itself!

Andy

#include <iostream>
#include <string>
using namespace std;

long factorial (long a, unsigned depth = 0)
{
  cout << string(depth, ' ') << "factorial(" << a << ")\n";
  if (a > 1) {
    long v = factorial (a-1, depth+1);
    cout << string(depth, ' ') << "return " << (a * v)
         << "\t= " << a << " * factorial(" << (a-1) << ") (= " << v << ")\n";
    return a * v;
  } else {
    cout << string(depth, ' ') << "return 1" << "\n";
    return 1;
  }
}

int main ()
{
  long number = 9;
  long value  = factorial (number);
  cout << "\n";
  cout << number << "! = " << value << "\n";
  return 0;
}

factorial(9)
 factorial(8)
  factorial(7)
   factorial(6)
    factorial(5)
     factorial(4)
      factorial(3)
       factorial(2)
        factorial(1)
        return 1
       return 2 = 2 * factorial(1) (= 1)
      return 6  = 3 * factorial(2) (= 2)
     return 24  = 4 * factorial(3) (= 6)
    return 120  = 5 * factorial(4) (= 24)
   return 720   = 6 * factorial(5) (= 120)
  return 5040   = 7 * factorial(6) (= 720)
 return 40320   = 8 * factorial(7) (= 5040)
return 362880   = 9 * factorial(8) (= 40320)

9! = 362880

[Arslan7041]

@Ispil: Thank you for your response. So my understanding is that the 1 is actually returned to the factorial function itself, correct? Because return values always return to the function that called them, and in this case the function calls itself and hence the value of 1 is returned to itself. Am I understanding this correctly?


@Andywestken: Im completely lost as to what you are doing in that code. And I am entirely unfamiliar with "string(depth...)".

[andywestken]

string(depth, ' ') is using the string (size_t n, char c); form of the string constructor, so I'm saying create a string with depth spaces, to get the line indenting to work (depth = recursion depth, which I added as a parameter to the function.)

The extra code is just to print out the function name and what it returns so should be easy enough to follow.

Andy

[Ispil]

Arslan, exactly.