Counting recursive calls

Question

is there a mathematical formula to calculate how many times the recursive function is called for the following without having to check with my complier

How many times will mystery2 be called recursively when invoked with the call mystery2(1000)?

 public void mystery2(int n)
   {
  if (n <= 1)
    System.out.print(n);
  else 
  {
    mystery2(n / 2);            
    System.out.print(", " + n);
  }
}

1, 3, 7, 15, 31, 62, 125, 250, 500, 1000 = 10 times

score 3 · Answer 1 · edited Nov 28 '13 at 22:30

3

Use ceil from log2(n)

ceil(log2(1000)) = ceil(9.966) = 10

edited Nov 28 '13 at 22:30

Bartosz Ciechanowski

10,293
5
45
60

answered Nov 26 '13 at 02:26

Adrian Krupa

1,877
1
15
24

For that kind of recursive methods you can use logarithm with base=divisor. For example mystery2(n/3); http://www.wolframalpha.com/input/?i=log_%283%29%281000%29 – Adrian Krupa Nov 26 '13 at 18:06

Gene · Answer 2 · 2013-11-26T02:43:38.587

There is no "formula", but there is a general technique for solving recurrences. Here you have the recurrence

N(x) = 1 + N(floor(x / 2))

with the base case

N(1) = 1

The definition of N(x) is "the number of times mystery2 is called if its initial argument is x".

Recurrences are solved by "tricks" that are learned like integration formulas or else fancy math like generating functions. Sometimes approximations are the best you can do. In your case, if we do away with the floor operator (or assume x is a power of 2), then it's pretty clear that

N(x) = 1 + log_2(x)

We can verify this. if x is 1, we have N(x) = 1 + 0 = 1. For x = 2, we have N(x) = 1 + 1 = 2 and so forth... For x = 1024, it's N(x) = 1 + 10 = 11.

With the floor operator, the exact answer is more complicated, depending on the number of odd factors of x, but the formula above will always be close.

Guy · Answer 3 · 2013-11-26T03:25:38.763

Another option is to pass the count into your method;

public void mystery2(int n) {
  mystery2(n, 1);
}

public void mystery2(int n, int count) {
  if (n <= 1)
    System.out.print(n);
  else 
  {
    mystery2(n / 2, count+1);            
    System.out.print(", " + n + ":count=" + count);
  }
}

Edit: I thought of a better way to do it. You can return the count as you go like this.

public static void mystery2(int n) {
    System.out.print("\ncount = " + mystery2(n, 1));
}

public static int mystery2(int n, int count) {
    if (n <= 1) {
        System.out.print(n);
        return count;
    }

    System.out.print(n + ", ");
    return mystery2(n / 2, count + 1);
}

i used your idea to count the max depth of a binary tree. thanks! — jacoblambert, Mar 25 '16 at 11:38

score 1 · Answer 4 · answered Nov 26 '13 at 02:19

Use a static variable, or a global

public void mystery2(int n)
{
  static count = 0;
  count++;
  system.out.print("We have called this " + count + "times before...");
  if (n <= 1)
    System.out.print(n);
  else
  {
    mystery2(n / 2);            
    System.out.print(", " + n);
  }

}

MGHandy · Answer 5 · 2013-11-26T02:38:23.313

1

outside the method make a variable like mysteryCnt = 0; (must initialize to 0) then inside the ELSE block increment it after the method, mysteryCnt ++; that might work.

else{
   mystery2(n / 2);
   mysteryCnt ++;
   System.out.println(", " + n);
}

Jonny Z has the right idea but you cannot initialize the variable inside the method or it will never increment past 1; the way he did it, it will set to 0 then increment to 1 every time you call the method.

edited Nov 26 '13 at 02:38

answered Nov 26 '13 at 02:23

MGHandy

363
1
3
11

Actually, static variables are initialized only once. http://stackoverflow.com/questions/8943716/static-variable-in-method-call – Johnny Z Nov 26 '13 at 11:30

Counting recursive calls

5 Answers5