What is Recursion?

What is Recursion

In Computer Science, recursion is a method in which a function calls itself. We can use recursion to solve many different problems such as:

  • Towers of Hanoi
  • Tree Traversals
  • DFS(Depth First Search) For Graphs

An analogy that better explains this term is as follows:

"I'll be back in 10 minutes. But If I am not, just read this message again."


Recursion vs. Iteration

Recursion

  • Recursive functions call themselves until a condition (base case) is met.

Iteration

  • iteration uses a looping structure (while, do while, for, foreach) in order to repeat a section of code until a certain condition is met.

  • Code Examples

    Iteration

    carbon(2).png

    This code snippet is an example of a basic for loop. Here, we are iterating or looping through all the numbers until we reach 100.

    • If the number is divisible by 3 & 5, we print "FizzBuzz" to the console.
    • If the number is only divisible by 3, we print "Fizz" to the console.
    • If the number is only divisible by 5, we print "Buzz" to the console.
    • Finally, if it is not divisible by any of these numbers, print the number to the console.
    • Recursion

      carbon(3).png

      This code snippet is an example of using recursion to solve the same problem.

      • Our base case or condition is: If the number is greater than 100, stop the function.
      • After establishing our base case, now we can start our loop.
      • If the number is divisible by 3 & 5, we print "FizzBuzz" to the console.
      • If the number is only divisible by 3, we print "Fizz" to the console.
      • If the number is only divisible by 5, we print "Buzz" to the console.
      • At the end, we call our function within itself and keep incrementing by one.