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!
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.