What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

Properties :

1. Same operation is performed multiple times with different input.
2. In every step we try to make the problem smaller.
3. We mandatorily need to have a base condition, which tells the system when to stop the recursion.

Let’s say we want to search for value ‘4’ in the below tree.

Sudo code :

fun search(root, valueToSearch) {
 if (root == null) {
    return null
 } 
 else if (valueToSearch == root.value) {
    return root
 } 
 else if (valueToSearch > root.value) {
    search(root.right, valueToSearch)
 } esle { search(root.left, valueToSearch) }
}

Why should we learn recursion ?

• Because it makes the code easy to write(compared to iterative) whenever a given problem can be broken down into similar sub-problems.
• Because it is heavily used in DS like Tree, Graphs etc….
• It is also heavily used in techniques like “Divide & Conquer”, “Greedy”, “Dynamic Programming”.

Format of a “Recursion” Function :

• Recursive case -> Case where function recurs.
• Base case -> Case where the function does not recur(Success or Failure).

Example :

sampleRecursion(parameter) {
 if (base case is satisfied) {
    return some base case value
 } else {
    sampleRecursion(modified parameter)
 }
}

How Recursion works internally ?

foo(n) {
 if (n < 1) {
    return
 } else {
    foo(n-1)
    print(“I am in foo” + n)
 } 
}
main() {
 foo(3)
}

Here we a have method called “foo(n)” which takes integer as a parameter. It checks if the input is less than 1 it simply returns and if it is greater than 1 it calls itself with a different input.

Also in the else case we have a “print” statement which prints a random text.

Last we have “main()”method which calls foo(3) method with an input of 3.

In above diagram we a have a stack memory which works in a LIFO(last in first out) fashion.

So in memory, the main() method gets stored first and foo(3), foo(2), foo(1). Since we have print(“I am in foo” + n) statement in the else case so the system knows there is some pending action to be done, and it decides to store the recursive method calls in memory.

We will try to solve mathematical problem using Recursion.

Factorial (n!) -:

int factorial(int value) {
 if (value == 0) {
    return 1;
 } else {
    return value * factorial(value -1);
 }
}

Fibonacci -:

int fibonacci(n) {
 if (n < 1) {
    return “Error message”
 } else if (n ==1 || n ==2) {
    return n -1
 } else {
    return fibonacci(n-1) + fibonacci(n-2)
 }
}

Recursion v/s Iteration :

https://sumeetpanchal21.wixsite.com/website