Recursion

1. Definition:

Recursion is a process in which a function calls itself continuously. A function that calls itself is called recursive function.

Recursion is not recommended to solve all types of problems. However, it is best for a few questions such as searching, sorting, Inorder/Preorder/Postorder, Tree Traversal, and DFS of Graph algorithms.

2. Example 1:

For example, suppose we want to sum the integers from 0 to some value n:

int sum(int n) {

  if (n >= 1) {

    return sum(n - 1) + n;

  }

  return n;

}




void main() {

  print(sum(5));

}





15




There are two main requirements of a recursive function:


• A Stop Condition : the function returns a value when a certain condition is satisfied, without a further recursive call

• The Recursive Call : the function calls itself with an input which is a step closer to the stop condition

3. Example 2:

Watch the video to understand the Fibonacci Sequence

int fib(n) {

  if (n == 1 || n == 2) {

    return 1;

  }

  return fib(n - 1) + fib(n - 2);

}

 

main() {

  print(fib(5));

}





5