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 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!