Too many calls

Computer Science Level 3

Consider the following recursive function: 

1
2
3
4
5
 
def fun(n):
    if n < 1:
        return
    fun(n-1)
    fun(n-3)

If fun(8) is called how many times will the fun() function be invoked (including the call fun(8) ) ?


The answer is 55.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Daniel Lim
Nov 25, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
count=0

def fun(n):
    global count
    count+=1
    if n < 1:
        return
    fun(n-1)
    fun(n-3)

fun(8)
print(count)

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Zeeshan Ali
Dec 21, 2015

Here is the algorithm I followed; 

// Algorithm starts

    global count <- 0;

    func(n) starts
        count <- count+1;
        if (n<1)
            return;
        call func(n-1);
        call func(n-3);
    func(n) ends

    main() starts
        call func(8);
        print count;
    main() ends

// Algorithm ends

And what I got was 55 \boxed{55}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...