Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

5.12. One more example

In the previous example I used temporary variables to spell out the steps, and to make the code easier to debug, but I could have saved a few lines:

This program uses recursion to calculate the factorial of the passed argument. It is the condensed version of the example on the previous page.

#include <iostream> using namespace std; int factorial (int n) { if (n == 0) { return 1; } else { return n * factorial (n-1); } } int main () { cout << factorial(3) << endl; }

From now on I will tend to use the more concise version, but I recommend that you use the more explicit version while you are developing code. When you have it working, you can tighten it up, if you are feeling inspired.

After factorial, the classic example of a recursively-defined mathematical function is fibonacci, which has the following definition:

\[\begin{split}\begin{aligned} && fibonacci(0) = 1 \\ && fibonacci(1) = 1 \\ && fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);\end{aligned}\end{split}\]

Translated into C++, this is

This program uses recursion to calculate the nth number in the fibonacci sequence.

#include <iostream> using namespace std; int fibonacci (int n) { if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } int main () { cout << fibonacci(3) << endl; }

If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if we assume that the two recursive calls (yes, you can make two recursive calls) work correctly, then it is clear that we get the right result by adding them together.

You have attempted of activities on this page