Thursday, June 11, 2015

Recursion part 1

Recursion is a programming concept where the same function is called within the same function directly or indirectly. Despite the rigorous meaning this is extensively used in mathematical and other algorithms.

For an example recursion is used to search within folders where each sub-folder is searched recursively by calling the search method again and again from sub-folders.

In this article an interesting scenario where a child buying toffees and returning toffee covers to get toffees again is discussed. Before moving on this is a simple example where recursion could be used to calculate factorial. Well this is not the most efficient way of calculating the factorial since recursive depth is limited by the programmers stack space. We'll be using python language this time.


Now here comes the real problem.

"Child can buy n toffees with Rs. n. He can get a toffee by returning 2 toffee covers. How many toffees he can try with 100 rupees?"

Analysis;
This is clearly a recursive call since the child will return toffee covers to buy toffees for the second time. So we should consider up coming chances for the kid to buy toffees.

Say he has 5 rupees, he take 5 toffees and has 5 covers. Then he returns 4 covers and take 2 toffees. Now he has 3 covers and he can buy another toffee and he has 1 cover in hand as well. So he can buy another toffee too. In total the fellow has 9 toffees eaten. So let's code this in python. The method is calculate().

No comments:

Post a Comment