Recursion-part(1)

Consider, you and your friend 👭 have created a walking game. It has few rules:

• The player has to start from a specific position called origin (where x=0).
• The player has to choose a number x from 0 to 100 (for example).
• If the value of x is even: player has to move 2 steps back 😫.
• If the value of x is odd: player has to move 1 step forward : ..🚶 (yay!).
• Finally, with every step the value x will be decremented by 1.
• Player has to stop as soon as value of x reaches 0 🙅

Your friend tasked you to change display boards every time the player moves to show them and the audience the next move player has to make. Since, you are a good programmer 💻 you rather decided to write a program which instructs the player for every step and displays result on the board, all at once. You know there's no time constraint. Players can go as far as to choose x as 100!. So, you decided to use the power of recursion.

But, WHAT IS RECURSION? Well, if you go as per the definition of oxford dictionary:

Recursion is the process of repeating a function, each time applying it to the result of the previous stage

In you and your friend's case, you would have opted for changing boards after every step for 100 times (for example)!. But rather, you decided to create a function which:

1. Break your problem into small chunks
2. Answer the problem using the information you already have
3. Develop a logic to solve that small chunk, in case the answer is not known

After giving all these information the function can call itself (rather than ask you what to do 😛) with a smaller input and display all the results at once.

How easy!. Right?

But... this can go forever, in which case "THE GAME MY FRIEND, WILL NEVER END!!" You need to know when to stop. Recursion consists of:

• A base case
• A function calling itself till it reaches the base case

In short, for the function to know when to stop, defining the base case is really important.

In this particular case, we know the player has to stop as soon as x becomes 0. It is also possible that the player chooses the value of x as '0', in which case the player doesn't have to move!

#Base case
if x == 0:
    print("Don't move")

Using all the information we have and decrementing value of x till we reach the base case, our target will be achieved! Below is the recursive function 'crazy_game' to display the combined movement, a player has to make if he/she chooses x=10. Feel free to try it by using more bigger value of x. Recursion is useful to solve a relatively bigger problem.

def crazy_game(x):
    #Base case
    if x == 0:
        print("Don't move!")
        return 
    #check if x is even
    if x % 2 ==0: 
        print("Move 2 steps backwards")
        #call the function for a smaller value (x-1) 
        crazy_game(x-1)
    #check if x is odd
    if x %2 !=0:
        print("Move 1 step forward")
        #call the function for a smaller value (x-1) 
        crazy_game(x-1)
    return "Game over!!"

print(crazy_game(10))

Interesting enough? How a bigger problem can be solved just by writing one simple function!

Result:

If you liked the first part of Recursion tutorial, stay tuned! I will cover problems from easy to hard in next blogposts.

---