A recursive function in C++ is a function that calls itself. Here is an example of a poorly-written recursive function:
void CountDown(int nValue)
{
using namespace std;
cout << nValue << endl;
CountDown(nValue-1);
}
int main(void)
{
CountDown(10);
return 0;
}
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:
void CountDown(int nValue)
{
using namespace std;
cout << nValue << endl;
// termination condition
if (nValue > 0)
CountDown(nValue-1);
}
int main(void)
{
CountDown(10);
return 0;
}
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:
// return the sum of 1 to nValue
int SumTo(int nValue)
{
if (nValue <=1)
return nValue;
else
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:
int Fibonacci(int nNumber)
{
if (nNumber == 0)
return 0;
if (nNumber == 1)
return 1;
return Fibonacci(nNumber-1) + Fibonacci(nNumber-2);
}
// And a main program to display the first 13 Fibonacci numbers
int main(void)
{
using namespace std;
for (int iii=0; iii < 13; iii++)
cout << Fibonacci(iii) << " ";
return 0;
}
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!
 7.11 — Namespaces
|
 Index
|
 7.9 — The stack and the heap
|
hi nice post, i enjoyed it
its NOT diff 2 ryt a fibo sequence iteratively :P !!!
mind-blowing!
When I tried to add comment something called wp-comments-post.php got downloaded.Any problem?
I get that too occasionally. I’m not sure why. It seems to happen after doing something that causes a page reload (eg. making a post or a comment). However, instead of reloading and redisplaying the page, it gets confused and tries to download the .php file. I’m not sure if it’s a browser issue or a PHP issue or a server issue.
Edit: I updated a plugin that may be the cause of this issue. Let me know if you receive this error in the future.
[...] 2007 Prev/Next Posts « 7.8 — Function Pointers | Home | 7.10 — Recursion » Friday, August 10th, 2007 at 4:56 [...]
hay alex.. thanks lot man.. i know recursive function.. but after read this article.its so easy to solve recursive. now i completely understand recursive function. thanks lot
cheers
void quiz(int i)
{
if (i > 1)
{
quiz(i / 2);
quiz(i / 2);
}
cout << “*”;
}
if quiz (5) ??? then how many time start printed?
get confused for this one..
how is going to solve step by step.. like u solved example one. .. ?
Hey this functin is going to print * 15 times.
7 times…
hey,
I wanted to ask about the efficiency of Recursion versus using for loop or while.
btw: your articles are great! I enjoy very much to read.
thanks,
khen.
Iterative functions (those using a for or while loop) are almost always more efficient than their recursive counterparts. The reason for this is because every time you call a function there is some amount of overhead that takes place. Iterative functions avoid this overhead.
That’s not to say iterative functions are always a better choice. Sometimes the recursive implementation of a function is so much cleaner and easier to follow that incurring a little extra overhead is more than worth it for the benefit in maintainability.
Note that the recursive implementation of a Fibonacci number generator is very inefficient. For example, to calculate Fibonacci(5), it calculates Fibonacci(4) and Fibonacci(3). To calculate Fibonacci(4), it recalculates Fibonacci(3), and so forth. In general, it will take an exponential number of calls to calculate the number; that is, it is O(exp(n)) in both time and space. See this code for a demonstration.
That is very true. It’s much more efficient to write an iterative version. I often see this question come up on job applications. They’ll ask you to write a Fibonacci function, but the thing they are really interested in is whether you understand that the recursive version of Fibonacci is too inefficient to use for practical purposes.
Iterative function that does the same. It’s quite simple to do in a loop as you can just start adding the numbers up as you work up the sequence. It’s easy to figure out when you look at the sequences working from left to right.
0 1 1 2 3 5 8 13 21 34 55 89 144
int Fibonacci2(int nNumber) { int fibnum =0, fibminus2=0, fibminus1=1; if (nNumber == 0) return 0; if (nNumber == 1) return 1; for (int iii=2; iii <= nNumber; iii++) { fibnum = fibminus1 + fibminus2; fibminus2 = fibminus1; fibminus1 = fibnum; } return fibnum; }It is correct
a better link would be this, as ideone allows you to run code as well.
Hahaha… apparently Linux doesn’t believe in stack overflows. I ran your stack overflowing program and it just kept going all the way past -4,000,000, when I stopped it. It didn’t even need to allocate any additional memory, I’m disappointed!
Never tried doing that before, now I’m gonna see if I can fork bomb this beast!
recursion is a funcion, that call itself repeatly.which have 3 must condition for doing program
program recusively three conditions are
1.the problem should be writen in recursive form.
2.should have a stopping condition.
3.
can you help me deal with this??
i have to make a program using recursion in which,for example…the user will input 3 and 2
add it using recursion by means of 3+1+1 and that it outputs 5.. help me pls…
Here’s an extension of the fibonacci sequence to negative numbers. The results are a little counter-intuitive for negative numbers, cf. http://en.wikipedia.org/wiki/Negafibonacci for details.
#include <iostream> typedef int integer; /* Fibonacci sequence is defined as: When n = 0 then 0; When n = 1 then 1; When n > 1 then (n - 1) + (n - 2) When n = -1 then -1; When n < -1 then (n + 2) - (n + 1) */ integer fibonacci(integer i) { switch(i) { case 0: return 0; break; case 1: return 1; break; case -1: return -1; break; default: if(i > 1) { return fibonacci(i - 1) + fibonacci(i - 2); } if(i < 1) { return fibonacci(i + 2) - fibonacci(i + 1); } } } int main() { using namespace std; for(int i = 0; i < 10; i++) { cout << fibonacci(i) << endl; } for(int i = 0; i > -10; i--) { cout << fibonacci(i) << endl; } return 0; }Task One: Recursion versus iteration
The following is a recursive method for determining “something”. You need to figure out what is being
determined. You also need to describe an iterative method for determining the same something.
Algorithm main
Purpose ???
Input Nothing
Output ???
BEGIN main
DECLARE N of type INTEGER
DECLARE result of type REAL
PRINT ‘‘Enter Number of Elements.’’
GET N
DECLARE data[N] of type REAL
READ data
CALL zamolo WITH data, N-1 RETURNING result
DISPLAY result
END main
it don’t know
Hi,
In the below program, what’s making it to go to infinite loop?
void CountDown(int nValue)
{
cout << nValue < 0 )
CountDown(nValue-1);
}
int main(void)
{
CountDown(10);
return 0;
}
At the end 0 is printed continuosly. What will be the reason behind it? Can you please explain?
Sorry there is a formatting issue in the above question.
cout << nValue < 0 )
CountDown(nValue-1);
It’s while(nValue<0). Sorry again.
You supplied the initial value (10) for CountDown to use, but then didn’t implement any way for it to stop at 0. Your “while(nValue” instead.
Then again, I don’t see why this works at all. Right from the start, “10 < 0" is false, so it shouldn't print anything at all…
Oh god damnit. This forum software sucks balls and butchered my reply. Now it makes no sense, AND I can’t even delete it or edit it!
Is there actually a use of fibonacci numbers in C++? Apart from in a maths program!
Hey there.
I’m just another guy who’s been reading through your tutorials (not always in a linear fashion) and I liked this one – especially coming from the previous article dealing with stack memory.
I noticed something – when I write recursive statements, I don’t use a return statement until I break the recursion. I noticed that you use return statements as part of your recursion. For example:
// return the sum of 1 to nValue int SumTo(int nValue) { if (nValue <=1) return nValue; else return SumTo(nValue - 1) + nValue; }When I’ve written code like this, I wouldn’t have thought to put the function call after a return statement in the else block. (In practice, it yields the same results.) You may have stated this, but I may have missed it – does using a return statement in front of the recursive function prevent the stack from filling up? Based on how you stated stacks worked in the previous tutorial, this seems to make sense…by issuing a return statement, the function variables and whatnot are removed from the stack each time it recurses so it doesn’t build up. Am I right or am I missing something? It seems to make sense, but something isn’t quite right….
As a side note, I made my own fibonacci sequence before reading this article (as practice for command-line arguments) but I used a recursive sequence that added the last and second-to-last numbers to get the next number. 1+1=2, 2+1=3, 3+2=5, 5+3=8, and so on. Seems like this method takes less overhead?
Thank you for your tutorials!
“On the authors machine, this program counted down to -11732 before terminating!”
Then you must have quite some stack memory, my computer stopped counting at -4607 xD
“Hahaha… apparently Linux doesn’t believe in stack overflows.
I ran your stack overflowing program and it just kept going all the way past -4,000,000, when I stopped it.”
Lmao, apparently you have infinite stack memory on your pc :P
Probably related to the compiler and your RAM, or maybe even the byte size of your operating system (I hit -130,146 before crashing, just like clementl below me, and I’ve got 12 GB of RAM using Dev-C++ on Windows 7 64-bit). Perhaps the compiler Quinn used had some kind of fancy dynamic/large stack, unless he has a few TB of RAM.
Fun to test, though. Someone should make a program using this principle that pops up error messages instead of cout’s to simulate the Windows experience for Mac/Linux users!
My pc stopped at -130146. Facinating!
#include
using std::cout;
using std::cin;
int main()
{
double nOld(0), nNew(1), nSum(0), nThfibo;
cout << "Numbers above the 30th, loose precision so \n";
cout << "the 29th and the 30th numbers are 514,229 and 832,040 maybe you should go manual from there \n \n";
cout <> nThfibo;
int iii = 1;
while (iii < nThfibo)
{
nSum = nOld + nNew;
nOld = nNew;
nNew = nSum;
iii++;
}
cout << nSum << " is the " << nThfibo << "th Fibonacci number.\n";
cin.clear();
cin.ignore(255, '\n');
cin.get();
return 0;
}
Faster way to get the Fibbo you want?
but above 30th number you loose precision anyway to fix it??
Greate site :)
Use int (int64 or something) instead of double, and you won’t loose precision.
hi every one i hope you can help me with this i found this countdown code in C
******************************
void countdown(int n)
{
if (n<10)
{
countdown()(n+1);
printf("%d\n", n);
}
}
void main()
{
countdown()(1);
getch();
}
*********************************
when it's done we can saw countdown printed like that
9
8
7
.
.
.
the problem is that i just can't understand how it works and why it print last numbers in the first place ? seek_help ;)
[...] from http://www.flickr.com/photos/22887580@N06/2198052702/?reg= 4. The Fibonacci diagram is from http://www.learncpp.com/cpp-tutorial/710-recursion/ 5. The Parthenon photo is from http://alexorbit.com/fibonacci/golden-ratio.htm Share [...]