Indirect Recursion in Python

by
5/5 - (1 vote)
def ping(i):
    if i>0:
        return pong(i-1)
    return "0"

def pong(i):
    if i>0:
        return ping(i-1)
    return "1"

print(ping(29))

What is the output of this code snippet?

Recursion is a powerful tool in your coding toolbox. Understanding it is a key skill on your path to mastery. Stephen Hawking used a concise explanation: “to understand recursion, one must first understand recursion.”

This puzzle uses indirect recursion where a function f calls a function g which calls function f. Each time we call a function, it solves a slightly easier problem.
In recursive problem solving, a function knows the result for some base cases (i.e., the naive solutions). It breaks a complex problem into a combination of less complex subproblems. As the subproblems are getting easier, they finally reach the base cases.
These are the least complex subproblems and we know their solutions. The idea is to build the solution of the complex problem from the solutions of the subproblems.

So when calling ping(29), the ping function reduces this question to pong(28)—the easier problem. The calling function ping waits for pong to return a solution. But pong asks back ping(27) and waits for a solution. On a higher level, ping receives odd and pong even argument values for the initial input i=29. The last call is pong(0), which returns 1. Each calling function waiting for the result receives the value 1 and returns it to its calling function.
Thus, the function ping returns 1 if i is an odd value.


Are you a master coder?
Test your skills now!

Related Video

Algorithms: Recursion

Solution

1

Leave a Comment