The equivalent function 1

Computer Science Level 2

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

Which of the following is equivalent to the recursive function shown above?

Assumptions

$b$ is a non-negative integer.

a+b

a(a+b)

a^{b}

a\cdot b

2 solutions

A Former Brilliant Member
Oct 18, 2015

If we write it step by step:
fun(a,b) -> a+fun(a,b-1) or 1 a + fun(a,b- 1 ) -> a + a + fun(a,b-2) or 2 a + fun(a,b- 2 ) -> .... -> ( b )a + fun(a,b- b ) -> ( b )a + 0 -> b.a

At every step b is decreasing by one and and another a is being added . There will come a time when a will be added b times and as the second argument of function will become zero the recursive function will end. Hence, the answer will be b.a or a.b .

Jose Solsona
Jan 18, 2016

This is a case of primitive recursion, wich is of the form (in a classical mathematical notation):

1
2
3

f : NxN -> N
f(a, 0)    = 0                      base case
f(a, S(b)) = f(a, b)+a              recursive case.

Where $S(b)$ denotes the sucesor of $b$ .

An equivalent Haskell version of $f$ as a infix operator:

1
2
3

(f) :: Int -> Int -> Int
a f 0     = 0
a f (b+1) = (a f b)+a

We observe that the recursive case is using the following Peano Axiom for multiplication: $(\forall a)(\forall b)(a\times S(b)=(a \times b)+a)$

So, $f(a, b)$ is just $\boxed{a \times b}$

The equivalent function 1

2 solutions

0 pending reports