|
|
|
|
|
|
|
The following diagram shows rabbits and its two
auxiliaries working to determine how many rabbits there are at
the end of 3 months.
Arguments | ^ Returned values
3 v | 3
*-------------*
| rabbits |
*-------------*
| ^ | ^
3 | | 3 | *------------*
| | *-------------* |
v | 2 v | 1
*-------------* *-------------*
| previous | | penultimate |
*-------------* *-------------*
2 | ^ 1 | ^
v | 2 v | 1
*-------------* *-------------*
| rabbits | | rabbits |
*-------------* *-------------*
| ^ | ^
2 | | 2 | *------------*
| | *-------------* |
v | 1 v | 1
*-------------* *-------------*
| previous | | penultimate |
*-------------* *-------------*
1 | ^ 0 | ^
v | 1 v | 1
*-------------* *-------------*
| rabbits | | rabbits |
*-------------* *-------------*
Each of the three cooperating functions can initiate a chain of calls that ends in a call to itself. Thus, the cooperating functions exhibit indirect, rather than direct, recursion.
The recursion bottoms out in calls to rabbits
when the value of n is either 0 or 1. Thus, rabbits is not a
particularly efficient function, because it twice computes
the value of rabbits (1).