Recursion is a function which calls itself within a new call stack frame. Which means that a recursive function will call itself, and then resume once the nested call returns.
Just to be absolutely clear in case there's any confusion - Recursion is
NOT a "goto" statement.
One way to visualise it is to un-roll the function to something a little more straightforward and procedural; For example, calcuating Factorial 4 in C++ could look like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
int factorial(int n)
{
std::cout << "factorial(" << n << ") called" << std::endl;
int answer;
if (n > 1)
{
answer = n * factorial(n-1);
}
else
{
answer = 1;
}
std::cout << "factorial(" << n << ") is: " << answer << std::endl;
return answer;
}
int main()
{
std::cout << "Final Result: " << factorial(4) << std::endl;
}
| |
Which produces output:
1 2 3 4 5 6 7 8 9
|
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(1) is: 1
factorial(2) is: 2
factorial(3) is: 6
factorial(4) is: 24
Final Result: 24
| |
See the order of the output -
int main()
calls
factorial(4)
, which in turn calls
factorial(3)
, which in turn calls
factorial(2)
, etc.
To un-roll that without the recursion, but with the same function flow the C++ code could look more like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
int factorial1() // (n == 2 - 1) && (n == 1)
{
int n = 1;
std::cout << "factorial" << n << "() called" << std::endl;
int answer = n;
std::cout << "factorial" << 1 << "() is: " << answer << std::endl;
return answer;
}
int factorial2() // (n == 3 - 1) && (n == 2)
{
int n = 2;
std::cout << "factorial" << n << "() called" << std::endl;
int answer = n * factorial1();
std::cout << "factorial" << n << "() is: " << answer << std::endl;
return answer;
}
int factorial3() // (n == 4 - 1) && (n == 3)
{
int n = 3;
std::cout << "factorial" << n << "() called" << std::endl;
int answer = n * factorial2();
std::cout << "factorial" << n << "() is: " << answer << std::endl;
return answer;
}
int factorial4() // (n == 4)
{
int n = 4;
std::cout << "factorial" << n << "() called" << std::endl;
int answer = n * factorial3();
std::cout << "factorial" << n << "() is: " << answer << std::endl;
return answer;
}
int main()
{
std::cout << "Final Result: " << factorial4() << std::endl;
}
| |
Which produces output:
1 2 3 4 5 6 7 8 9
|
factorial4() called
factorial3() called
factorial2() called
factorial1() called
factorial1() is: 1
factorial2() is: 2
factorial3() is: 6
factorial4() is: 24
Final Result: 24
| |
Again, It's worth noting the order of the output -
int main()
calls
factorial4()
, which in turn calls
factorial3()
, which in turn calls
factorial2()
, etc. This is precisely the same as the recursive version of the code.
Recursion is a form of repetition, albeit one which consumes space on the stack - unlike an ordinary loop (for/while) or a goto statement, the flow of your program doesn't "jump" to a different line, it enters a new function call with its own independent stack frame.
A stack frame is a function's local variable space in memory which is released when a function returns.