Difference between revisions of "recursive"
m |
|||
(5 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
+ | [[Category:Knowledge Base]] |
||
− | A function is called recursive it is calls itself. On most modern processors, the calling conventions (ABI) used by the compiler are such that recursive calling is not a problem. |
||
+ | A function is called recursive if it calls itself. On most modern processors, the calling conventions (ABI) used by the compiler are such that recursive calling is not a problem. |
||
However, even with the compiler supporting this, extreme care needs to be taken to use recursion in a way that does not create problems. |
However, even with the compiler supporting this, extreme care needs to be taken to use recursion in a way that does not create problems. |
||
Typically, this means: |
Typically, this means: |
||
Line 17: | Line 18: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
Well actually, this is not a great example, for the following reasons: |
Well actually, this is not a great example, for the following reasons: |
||
− | * The recursion is not limited. If called with a parameter of 1000000, then there will be one million invocations, most likely causing a stack overflow |
+ | * The recursion is not limited. If called with a parameter of 1000000, then there will be one million invocations, most likely causing a stack overflow. |
− | * The variable used for storage is limited, so it will only work up to 4G (0xFFFF_FFFF) on a 32-bit CPU. (Or more precisely a CPU for which the compiler uses a 32-bit value for type unsigned) |
+ | * The variable used for storage is limited, so it will only work up to 4G (0xFFFF_FFFF) on a 32-bit CPU. (Or more precisely a CPU for which the compiler uses a 32-bit value for type unsigned.) |
− | * The recursion is not really necessary |
+ | * The recursion is not really necessary. It can be easily eliminated by changing the routine as below: |
<syntaxhighlight lang="c"> |
<syntaxhighlight lang="c"> |
||
unsigned CalcFactorial(unsigned n) { |
unsigned CalcFactorial(unsigned n) { |
||
Line 33: | Line 34: | ||
===Bad example=== |
===Bad example=== |
||
− | TBD |
||
− | |||
== Problems with using recursive functions== |
== Problems with using recursive functions== |
||
− | * Debugging: Debugging a recursive function can be quite tricky, as |
+ | * Debugging: Debugging a recursive function can be quite tricky, as a breakpoint will work on all instances and can not be specific to a particular invocation. |
* Stack usage: Every invocation uses a certain amount of stack space. Thus excessive recursion can lead to stack overflow. |
* Stack usage: Every invocation uses a certain amount of stack space. Thus excessive recursion can lead to stack overflow. |
||
== Good programming practice == |
== Good programming practice == |
||
− | * Use recursion only where really necessary or where it at least has massive advantages |
+ | * Use recursion only where really necessary or where it at least has massive advantages. |
− | * If used, then one of the recursion |
+ | * If used, then one of the recursion parameters used must be the recursion level, starting with 0 on the first call. This helps to avoid stack overflow due to excessive recursion. |
Latest revision as of 13:26, 16 May 2024
A function is called recursive if it calls itself. On most modern processors, the calling conventions (ABI) used by the compiler are such that recursive calling is not a problem. However, even with the compiler supporting this, extreme care needs to be taken to use recursion in a way that does not create problems. Typically, this means:
- All parameters are passed as arguments directly to the function (not statics)
- The function does not need any static variables
Contents
Examples (C-Language)
Good example
unsigned CalcFactorial(unsigned n) {
if (n == 1) {
return 1;
}
n *= CalcFactorial(n -1);
return n;
}
Well actually, this is not a great example, for the following reasons:
- The recursion is not limited. If called with a parameter of 1000000, then there will be one million invocations, most likely causing a stack overflow.
- The variable used for storage is limited, so it will only work up to 4G (0xFFFF_FFFF) on a 32-bit CPU. (Or more precisely a CPU for which the compiler uses a 32-bit value for type unsigned.)
- The recursion is not really necessary. It can be easily eliminated by changing the routine as below:
unsigned CalcFactorial(unsigned n) {
unsigned r;
r = n;
while (n > 2) {
n--;
r *= n;
}
return r;
}
Bad example
Problems with using recursive functions
- Debugging: Debugging a recursive function can be quite tricky, as a breakpoint will work on all instances and can not be specific to a particular invocation.
- Stack usage: Every invocation uses a certain amount of stack space. Thus excessive recursion can lead to stack overflow.
Good programming practice
- Use recursion only where really necessary or where it at least has massive advantages.
- If used, then one of the recursion parameters used must be the recursion level, starting with 0 on the first call. This helps to avoid stack overflow due to excessive recursion.