Types of Recursion

Types of Recursion

Recursive functions can be classified  on the basis of :
a.) If the functions call itself directly or indirectly – Direct / Indirect
b.) If an operation is pending at each recursive call – Tail Recursive/ Not
c.) based on the structure of the function calling pattern – Linear / Tree

Direct Recursion:

• If a function explicitly calls itself it is called directly recursive.
• When the method invokes itself it is direct.

#include <iostream>

int testfunc(int num)
{
  if (num == 0)
    return 0;
  else
    return (testfunc(num - 1));
}

int main()
{
  int num = 5;
  std::cout << testfunc(num) << std::endl;
  return 0;
}

Here, the function ‘testfunc’ calls itself for all positive values of num.

Indirect Recursion

• This occurs when the function invokes other method which again causes the original function to be called again.
• If a method ‘X’ , calls method ‘Y’, which calls method ‘Z’ which again leads to ‘X’ being invoked is called indirect recursive or mutually recursive as well.

#include <iostream>

int testfunc1(int num)
{
  if (num == 0)
    return 0;
  else
    return (testfunc2(num - 1));
}

int testfunc2(int num2)
{
  return testfunc1(num2 - 1);
}

int main()
{
  int num = 5;
  std::cout << testfunc1(num) << std::endl;
  return 0;
}

Tail / Bottom Recursion

A function is said to be tail-recursive, if no operations are pending when the recursive function returns to its caller.

• Such functions, immediately return the return value from the calling function.
• It is an efficient method as compared to others, as the stack space required is less and even compute overhead will get reduced.
• Recollect the previously discussed example, factorial of a number. We had written it in non tail recursive way, as after call operation is still pending.

#include <iostream>

int fact(int n)
{
  if (n == 1)
    return 1;
  else
    return (n * fact(n - 1));
}

int main()
{
  int num = 5;
  std::cout << fact(num) << std::endl;
  return 0;
}

In order to make it tail recursive, information about pending tasks has to be tracked.

#include <stdio.h>

int fact2(int n, int result);

int main() {
  int n = 5;
  printf("%d! = %d\n", n, fact(n));
  return 0;
}

int fact(int n){
  return fact2(n, 1);
}

int fact2(int n, int result) {
  if (n == 1) return result;
  return fact2(n - 1, n * result);
}

If you observe, the ‘fact2’ has a similar syntax to the original fact. Now, ‘fact’ in tail recursion case does not have pending calculations/operations to perform on return from recursive function calls.
The value computed by fact2 is simply returned. Thus, the amount of space required on stack reduces considerably. ( just for value of n and result , space required.

Linear and Tree Recursion

Depending on the structure the recursive function calls take, or grows it can be either linear or non linear.
It is linearly recursive when, the pending operations do not involve another recursive call to the function. Our Factorial recursive function is linearly recursive as it only involves multiplying the returned values and no further calls to function.
Tree recursion is when, pending operations involve another recursive call to function.
For example –  Fibonacci series, the pending operations have recursive call to the fib() recursive function to compute the results.

When not to use recursion?

Essentially, any problem that can be solved by recursion can be also solved by iteration. Although for certain applications like Tower of Hanoi, certain artificial intelligence problems etc recursion is used since it defines the problem naturally, still there are certain times when recursion should not be used.

1. Iterations are faster than their recursive counterparts. So, for speed we would normally use iteration.
2. If the stack limit is constraining then we will prefer iteration over recursion.
3. Some problems are naturally programmed recursively, here recursion would suit better.
4. The overhead involved in recursion in terms of time and space consumed both discourages to use recursion often.