A
recursive function in C++ is a function that calls itself. Here is an example of a poorly-written recursive function:
01 | void CountDown(int nValue) |
04 | cout << nValue << endl; |
When CountDown(10) is called, the number 10 is printed, and CountDown(9) is called. CountDown(9) prints 9 and calls CountDown(8). CountDown(8) prints 8 and calls CountDown(7). The sequence of CountDown(n) calling CountDown(n-1) is continually repeated, effectively forming the recursive equivalent of an infinite loop.
In the lesson on the stack and the heap, you learned that every function call causes data to be placed on the call stack. Because the CountDown() function never returns (it just calls CountDown() again), this information is never being popped off the stack! Consequently, at some point, the computer will run out of stack memory, stack overflow will result, and the program will crash or terminate. On the authors machine, this program counted down to -11732 before terminating!
This program illustrates the most important point about recursive functions: you must include a termination condition, or they will run “forever” (or until the call stack runs out of memory).
Stopping a recursive function generally involves using an if statement. Here is our function redesigned with a termination condition:
01 | void CountDown(int nValue) |
04 | cout << nValue << endl; |
Now when we run our program, CountDown() will count down to 0 and then stop!
Let’s take a look at another recursive function that is slightly more useful:
7 | return SumTo(nValue - 1) + nValue; |
Recursive programs can often be hard to figure out just by looking at them. It’s often instructive to see what happens when we call a recursive function with a particular value. So let’s see what happens when we call this function with nValue = 5.
SumTo(5) called, 5 <= 1 is false, so we return SumTo(4) + 5.
SumTo(4) called, 4 <= 1 is false, so we return SumTo(3) + 4.
SumTo(3) called, 3 <= 1 is false, so we return SumTo(2) + 3.
SumTo(2) called, 2 <= 1 is false, so we return SumTo(1) + 2.
SumTo(1) called, 1 <= 1 is true, so we return 1. This is the termination condition.
Now we unwind the call stack (popping each function off the call stack as it returns):
SumTo(1) returns 1.
SumTo(2) returns SumTo(1) + 2, which is 1 + 2 = 3.
SumTo(3) returns SumTo(2) + 3, which is 3 + 3 = 6.
SumTo(4) returns SumTo(3) + 4, which is 6 + 4 = 10.
SumTo(5) returns SumTo(4) + 5, which is 10 + 5 = 15.
Consequently, SumTo(5) returns 15.
One question that is often asked about recursive functions is, "Why use a recursive function if you can do many of the same tasks iteratively (using a
for loop or
while loop)?”. It turns out that you can always solve a recursive problem iteratively — however, for non-trivial problems, the recursive version is often much simpler to write (and read).
Fibonacci numbers
One of the most famous mathematical recursive algorithms is the Fibonacci sequence, as Fibonacci sequences appear in many places in nature, such as branching of trees, the spiral of shells, the fruitlets of a pineapple, an uncurling fern frond, and the arrangement of a pine cone.
Here is a picture of a Fibonacci spiral:
Each of the Fibonacci numbers is the length of the side of the square that the number appears in.
Fibonacci numbers are defined mathematically as:
| F(n) = | 0 if n = 0
1 if n = 1
f(n-1) + f(n-2) if n > 1 |
Consequently, it’s rather simple to write a recursive function to calculate the nth Fibonacci number:
01 | int Fibonacci(int nNumber) |
07 | return Fibonacci(nNumber-1) + Fibonacci(nNumber-2); |
14 | for (int iii=0; iii < 13; iii++) |
15 | cout << Fibonacci(iii) << " "; |
Running the program produces the following result:
0 1 1 2 3 5 8 13 21 34 55 89 144
Which you will note are exactly the numbers that appear in the Fibonacci spiral diagram.
While it’s possible to write the Fibonacci function iteratively, it’s much more difficult!
No comments:
Post a Comment