Recursive Function

A Recursive Function is a function whose function definition includes a reference to the function.

• Example(s):
  • [math]\displaystyle{ ƒ(n) = ƒ(n-1) + ƒ(n-2) }[/math], for a Fibonacci number sequence.
  • …
• Counter-Example(s):
  • Iterative Function.
• See: Recursive Rule, Sequence, Recursive Algorithm.

---

---

References

• http://en.wiktionary.org/wiki/recursive_function
• http://en.wikipedia.org/wiki/Recursive_function_theory
• http://en.wikipedia.org/wiki/Recursion_(computer_science)

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/recursion_(computer_science)#Recursion_versus_iteration Retrieved:2015-7-9.
  • Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used. In imperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in functional languages recursion is preferred, with tail recursion optimization leading to little overhead, and sometimes explicit iteration is not available.

    Compare the templates to compute x_n defined by x_n = f(n, x_n-1) from x_base:

function recursive(n) if n==base return xbase else return f(n, recursive(n-1))

function iterative(n) x = xbase for i = n downto base x = f(i, x) return x

For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.

For example, the factorial function may be implemented iteratively in C by assigning to an loop index variable and accumulator variable, rather than passing arguments and returning values by recursion:

unsigned int factorial(unsigned int n) {
 unsigned int product = 1; // empty product is 1
 while (n) {
   product *= n;
   --n;
 }
 return product;
}

---