Recursive Function With Multiple Constraints

Computer Science Level 2

What is the output of the following Python program?

def func(a,b):
    if a == 0 and b == 0:
        return 0
    if a == 0: return 1 + func(a,b-1)
    if b == 0: return 1 + func(a-1,b)

    if a > b:
        return 1 + func(func(a-b,b),b-1)
    else:
        return 1 + func(a-1,func(b-a,a))

print func(31415,27182)

Bonus : What is the output of func(a,b) ?

The answer is 58597.

1 solution

Christopher Boo
Jun 10, 2016

The easiest approach is to copy this code and runs it in your machine. But if you are looking at this solution, I believe you didn't use that method.

There are no efficient way that I know of to figure out what's a recursive function is doing other than looking for patterns and then prove them to be true. Like many other techniques, this requires experiences. For this problem, func(a,b) turns out to be a function that returns a+b .

After identifying this pattern, all you need to do is to prove it. This is very similar to induction .

Base case : $a = 0, b = 0$

$f(0,0)=0+0=0$

Hence the base case is true.

Recursive step case 1 : $a>b>0$

$f(a,b) = 1 + f(f(a-b,b),b-1) = 1 + f(a-b+b,b-1) = 1 + f(a,b-1) = 1 + a + b - 1 = a + b$

Recursive step case 2 : $0<a \leq b$

$f(a,b) = 1 + f(a-1,f(b-a,a)) = 1 + f(a-1,b-a+a) = 1 + f(a-1,b) = 1 + a - 1 + b = a + b$

Actually, the cases 1 and 2 in your solution should be $a\gt b\gt 0$ and $0\lt a\leq b$ respectively.

Also, the cases $0=a\lt b$ and $a\gt b=0$ aren't covered up in your proof and need to be dealt with separately although not much work is needed to show that.

$f(0,b)=1+f(0,b-1)=f(0,0)+\sum_{i=1}^b 1=0+b=b~\forall~b\geq 1$

Similarly, we see that $f(a,0)=0+a=a~\forall~a\geq 1$ thus showing that $f(a,b)=a+b$ holds true for these cases too.

Prasun Biswas - 5 years ago

Yes, thanks for pointing that out!

Christopher Boo - 5 years ago

Copying it as it is didn't work as it led to stack overflow. But observing pattern of what it does on smaller inputs does work.

Cheng Wei Chang - 5 years ago

Yes. After observing the pattern, what we need to do is to prove that it's true.

Christopher Boo - 5 years ago

Nice problem that teaches proof by induction

Cheng Wei Chang - 5 years ago

a and b have no assigned value

Austin Li - 10 months, 1 week ago

Recursive Function With Multiple Constraints

The answer is 58597.

1 solution

0 pending reports