How recursion works


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


int main()
{
  int f = Fact(5);
  cout << f << endl;
  return 0;
}
To see how recursion works, let's consider the resursive function computing a factorial number.

In particular:

  • A function call to Fact in turn makes another function call to Fact. See the diagram on the left.
  • This means that we will end up with a "stack" of function calls which are many copies of the Fact function. See the diagram below:
    ------------------------------- time ------------------------------>
    Fact(5)
    main()

    Fact(5)
    called     		...
    Fact(1)
    Fact(2)
    Fact(3)
    Fact(4)
    Fact(5)
    main()

    Fact(1)
    called     		...
    Fact(2)
    Fact(3)
    Fact(4)
    Fact(5)
    main()

    Fact(1)
    returned     		...
    main()

    Fact(5)
    returned

No base case implies an infinite recursion

If a function doesn't have a base case, it will keeping making a recursive function call infinitely, consuming the entire stack and crashing the program.

Practice Problems

  1. (Mandatory) Make change 
    ~$ ./change
Enter amount: 134
Change to give is: QQQQQNPPPP

~$ ./change
Enter amount: 32
Change to give is: QNPP
    Solution.
  2. Any thoughts on how you could modify to print out coins in increasing value?
  3. Write a recursive function void factors(int n) that prints out the factorization of n. Use firstfactor(int) that you guys defined for me in a previous homework (see below). 
    
// Returns the smallest factor of n
int firstfactor(int n)
{
  int i = 2;
  while(n % i != 0)
    i++;

  return i;
}
    Take a look at my solution
  4. Printing in binary 
    ~$ ./binary
Enter non-negative integer: 127
In binary that's 1111111

~$ ./binary
Enter non-negative integer: 11
In binary that's 1011

~$ ./binary
Enter non-negative integer: 65536
In binary that's 10000000000000000
    Solution
  5. Fibonacci Numbers
  6. Computing Continued Fractions
  7. Writing Continued Fractions in HTML