Difference between revisions of "recursive"

From SEGGER Wiki
Jump to: navigation, search
m
m (Problems with using recursive functions)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 17:
 
</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 recursion is not really necessary, it can be easily eliminated by changing the routine as below:
 
  +
* The recursion is not really necessary. It can be easily eliminated by changing the routine as below:
* 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)
 
 
<syntaxhighlight lang="c">
 
<syntaxhighlight lang="c">
 
unsigned CalcFactorial(unsigned n) {
 
unsigned CalcFactorial(unsigned n) {
 
unsigned r;
 
unsigned r;
 
r = n;
 
r = n;
while (n > 1) {
+
while (n > 2) {
 
n--;
 
n--;
 
r *= n;
 
r *= n;
Line 33: Line 33:
   
 
===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 a breakpoint will work on all instances and can not be specific to a particular invocation
+
* 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 paramters used be the recursion level, starting with 0 on the first call. This helps to avoid stack overflow due to excessive 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 21:25, 6 June 2019

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

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.