Recursion occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.
As an example, a recursion function is one that defines itself within itself.
void fun(int n) {
if(n>0) {
fun(n-1);
}
}
¶ Tracing
Recursion functions are traced in the form of a tree. The top of the tree represents the function passed with a parameter, and each branch represents an instruction from that function.
void fun(int n) {
if (n>0) {
printf("%d",n);
fun(n-1);
}
}
void main() {
int x=3;
fun(x);
}
In this example each iteration of the function fun will result in 2 more branches: the print statement, and the function call.
¶ Recursion Phases
Recursion functions have two phases: ascending and descending. During the ascending phase, the function will execute at calling time. Oppositely, during the descending phase, the function will execute at returning time. Any code before the function call itself is written during calling time while any code after the function is written in returning time.
void fun(int n) {
if (n>0) {
// ascending phase (calling time)
fun(n-1);
// descending phase (returning time)
}
}
A recursion function has both an ascending phase and descending phase. A loop however, has only an ascending phase.
¶ Static Variables in Recursion
Unlike local variables in a recursive function, static variables are shared among all of the functions. They are created only once at the program run time. In the following example, x will be a static variable with the value of 0.
int fun(int n) {
static int x=0;
if (n>0) {
x++;
return fun(n-1)+x;
}
return 0;
}
int main() {
int a=3;
printf("%d", fun(a));
}
Before each function recursion, the variable x is incremented, but is not added to fun(n-1) until the returning time. So x will not be added until the inter most function has completed, at which point, the latest version of x will be added. Then the second inter most function will add 3 to the result of its
function and that will then be the value for the third inter most function (and so on).
So fun(a) will equal 9 because the recursive function executed 3 times, each time adding 3 to its result. 3 x 3 = 9.
¶ Types of Recursion
There are 5 types of recursion:
- Tail Recursion
- Head Recursion
- Tree Recursion
- Indirect Recursion
- Nested Recursion
¶ Tail Recursion
If a recursive function is calling itself, and that recursive call is the last statement in the function, it is considered tail recursion. After the final call, there are no other steps to perform. This means that tail recursive functions will only operate in the ascending phase (call time). If any instructions are made after the recursive function call, then the function would not be considered a tail recursion.
void fun(int n) {
if (n>0) {
...
fun(n-1);
}
}
Because tail recursion always operates in the ascending phase, a loop can be used as alternative to complete the same task.
void fun(in n) {
while (n>0) {
...
n--;
}
}
This will output the same result as the tail recursive function. The primary difference is the space used in the memory. A tail recursive function will be as large as the amount of recursive functions that are iterated through, as well as the instructions per each iteration. A while loop takes only the space of the loop and its instructions once. Through each iteration, no other space is occupied. Because of this, whenever you find yourself using tail recursion, it is more space efficient to convert the code into a loop.
¶ Head Recursion
If a recursive function is calling itself, and that recursive call is the first statement in the function, it is considered head recursion. You can have many instructions after the call, but the call must be first inside the function. This means that head recursive functions will only operate in descending phase (return time).
void fun(int n) {
if (n>0) {
fun(n-1);
...
}
}
Head recursion functions can be translated into loops, but because loops only operate in the ascending phase, they require some changes for them to work the same.
¶ Linear Recursion
Linear Recursion is a more broad perspective of recursion types in that it ignores where the recursive function call is located in the function. By this definition, both Head and Tail Recursion can be considered linear recursion, but if the function call is between call time and return time code, it will still be considered linear recursion.
void fun(int n) {
if (n>0) {
...
fun(n-1);
...
}
}
The important thing to note is that there is only one recursive function call made in the outer function.
¶ Tree Recursion
In Linear Recursion (Head, Tail, or neither), a recursive function call is made inside an outer function, but it is only called once. If there are more than one recursive calls, it becomes tree recursion.
void fun(int n) {
if (n>0) {
...
fun(n-1);
fun(n-1);
...
}
}
With procedural logic, a function call must be completed before exiting. So when a function call exists within another function, the inner function must be completed before executing the instructions of the outer function.
void fun(int n) {
if (n>0) {
printf("%d ", n);
fun(n-1);
fun(n-1);
}
}
void main() {
fun(3);
}
This will output: 3 2 1 1 2 1 1.
¶ Indirect Recursion
In an Indirect Recursion, multiple functions are used to call each other in a circular fashion. Function A conditionally calls Function B and Function B conditionally calls Function A.
void funA(int n) {
if (n>0) {
printf("%d", n);
funB(n-1);
}
}
void funB(int n) {
if (n>1) {
printf("%d", n);
funA(n/2);
}
}
¶ Nested Recursion
In a Nested Recursion, the parameter of the nested function call is in itself, a nested function call. This creates recursion inside recursion or nested recursion.
void fun(int n) {
if (n>100)
return n-10;
else
return fun(fun(n+11));
}