Recursion

C functions also support recursion – a concept that gives most beginning (and many experienced) programmers severe headaches as they try to wrap their minds around the execution of a recursive function. The idea behind recursion is that a function can call itself in order to complete an iterative process where each successive step is defined in terms of the previous result. The best, and probably easiest example where a recursive function is more efficient than a non-recursive one is the calculation of factorials.

Example

RecursiveFunction.png


The factorial function on the previous example would be evaluated like this if it were passed a value of 5. This is primarily a conceptual process for the evaluation of this function, and is not necessarily the actual way the function is evaluated. The stack shown here is not necessarily the same thing as the main stack implemented by the C compiler.

  • In the first iteration, the partial evaluation of 5! = 5 * 4! is pushed onto the stack. It will not be fully evaluated until 4! is calculated.
  • In the second iteration, the partial evaluation of 4! = 4 * 3! is pushed onto the stack.
  • In the third iteration, the partial evaluation of 3! = 3 * 2! is pushed onto the stack.
  • In the fourth iteration, the partial evaluation of 2! = 2 * 1! is pushed onto the stack.
  • In the fifth iteration, the full evaluation of 1! = 1 is pushed onto the stack.
  • Now, the 1! on level [1] is replaced with the value 1 from level [0] and level [1] is evaluated to 2.
  • Next, the 2! on level [2] is replaced with the value 2 from level [1] and level [2] is evaluated to 6.
  • Next, the 3! on level [3] is replaced with the value 6 from level [2] and level [3] is evaluated to 24.
  • Next, the 4! on level [4] is replaced with the value 24 from level [3] and level [4] is evaluated to 120, which is the final result.
© 2024 Microchip Technology, Inc.
Notice: ARM and Cortex are the registered trademarks of ARM Limited in the EU and other countries.
Information contained on this site regarding device applications and the like is provided only for your convenience and may be superseded by updates. It is your responsibility to ensure that your application meets with your specifications. MICROCHIP MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND WHETHER EXPRESS OR IMPLIED, WRITTEN OR ORAL, STATUTORY OR OTHERWISE, RELATED TO THE INFORMATION, INCLUDING BUT NOT LIMITED TO ITS CONDITION, QUALITY, PERFORMANCE, MERCHANTABILITY OR FITNESS FOR PURPOSE. Microchip disclaims all liability arising from this information and its use. Use of Microchip devices in life support and/or safety applications is entirely at the buyer's risk, and the buyer agrees to defend, indemnify and hold harmless Microchip from any and all damages, claims, suits, or expenses resulting from such use. No licenses are conveyed, implicitly or otherwise, under any Microchip intellectual property rights.