What is Recursion?

This lesson explains the basics of recursion.

We'll cover the following

Introduction

Are you completely new to recursion? No idea what it means or what we’re talking about? After a lot of intimidating comments regarding recursion, you ended up here hoping to learn and solve recursive problems all by yourself.

We start with the very basics of recursion using Java as our base language, and we build up to relatively complex problems that you’ll be able to solve by yourself as you progress. Awesome, right?

What is recursion?

Recursion is when a method calls itself again and again until it reaches a specified stopping condition. In general, the method mentioned above is called a recursive method.

Why recursion?

• Recursive code is generally shorter to write as compared to an iterative code.

• In general, loops are converted into recursive methods when they are compiled or interpreted.

• A recursive method is most useful for tasks that can be defined in terms of similar subtasks.

Format of a recursive method

Each recursive method consists of $2$ parts:

1. Base Case: The base case is where the call to the method stops, meaning, it does not make any subsequent recursive calls.
2. Recursive Case: The recursive case is where the method calls itself again and again until it reaches the base case.

Generic recursive algorithm

RecursiveMethod() {  // Base Case  if (base case condition) {    return some base case value;  }  else {    // Recursive Case    return (some work and then a recursive call to RecursiveMethod())  }}