18.5: Recursive Factorial Function Call Tree

Last updated
Save as PDF

Page ID: 54382

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In order to better understand recursion, a recursion tree can help show how the recursive calls interact.

The factorial function recursion tree. — Figure \(\PageIndex{1}\): Factorial Recursion Tree.

When the initial call to factorial function occurs from main, the main will start into the fact() function (shown as step 1). Since the argument of 5 is not a base case, the fact() function must call fact() again with the argument of n-1 or 4 in this example (step 2). And, again, since 4 is not the base case, the fact() function must call fact() again with the argument of n-1 or 3 in this example (step 3).

This process continues until the argument passed into the fact() function meets the base case which is when the arguments is equal to 1 (shown as step 5). When this occurs, only then is a return value provided to the previous call (step 6). This return argument is then used to calculate the previous multiplication which is 2 times 1 which will return a value to the previous call (as shown in step 7). This process will continue (steps 8, 9, and 10) until the main has a final answer.

Since the code being executed is the same, each instance of the fact() function is different from any other instance only in the arguments and any local values (none in this example).

It should also be noted that the height of the recursion tree is directly associated with the amount of memory used by the recursive function. For problems where the recursion tree is very large, this can have a negative impact on overall performance of a recursive routine.