Calculate amount of memory needed for recursive function

Question

I have following function:

public static long Fibon(long num)
{
    if (num == 1)
    {
        return 1;
    }
    else if (num == 2)
    {
        return 1;
    }
    return fibon(num - 1) + fibon(num - 2);
}

this function uses recursion in order to calculate Fibonacci number. How can I calculate amount of required stack memory for executing this function before executing it? For example I want to execute this function in few separated threads with some big numbers, and before executing threads I want to know how much stack memory available I need to have.

It isn't a problem of "available" memory... it is a problem of stack size, that is an limited part of memory — xanatos, Jul 03 '15 at 09:11
Looks like you are trying to find a solution for the longest path problem https://en.wikipedia.org/wiki/Longest_path_problem — AgeDeO, Jul 03 '15 at 09:11
Here Hans says the default stack size: http://stackoverflow.com/q/5507574/613130 ... 1mb at 32 bits and 4mb at 64 bits. Note that you can change it with a constructor of `Thread` Now... how much memory is consumed in a recursive call is a different problem. — xanatos, Jul 03 '15 at 09:13
I've modified question with taking into account your clarifications. — Yuriy Zaletskyy, Jul 03 '15 at 09:17
http://stackoverflow.com/questions/14032515/how-to-get-the-amount-of-memory-used-by-an-application — Sreejith, Jul 03 '15 at 09:17
Ah... and your code is wrong.. it is `<= 1` or something similar... otherwise it won't work. — xanatos, Jul 03 '15 at 09:17
And note that that algorithm is mortally slow, even for a `fib(100)`... It is normally better to use memoization for fibonacci. This because the time necessary to calculate fib(x) == time(fib(x-1)) + time(fib(x-2))... so even the time grows in the same way of the fibonacci sequence! — xanatos, Jul 03 '15 at 09:22
Some useful references: http://stackoverflow.com/q/2901185/613130, http://stackoverflow.com/q/4513438/613130 — xanatos, Jul 03 '15 at 09:29
As a sidenote, if the amount of recursion/stacksize could become a problem, fibonacci can also be done iteratively to prevent the issue altogether. For example: http://www.dotnetperls.com/fibonacci. (Memoization could be used for both approaches) . As a 2nd sidenote, if the thread start simultaniously, you could use a single function that returns the required steps within the iteration. — Me.Name, Jul 03 '15 at 09:35

Jonah Mann · Answer 1 · 2015-07-03T09:31:14.537

1

Just looking at it, the code won't work because when num == 2, the method tries to find fibon(0).

Try

public static long Fibon(long num)
{
    if (num == 1)
    {
        return 1;
    }
    else if (num == 2)
    {
        return 1;
    }
    return fibon(num - 1) + fibon(num - 2);
}

will give you 1, 1, 2, 3, 5, ...

Sorry this wasn't an answer, I don't have the reputation to comment.

edit: You'll also be able compute greater entries bu using ulong.

edited Jul 03 '15 at 09:31

answered Jul 03 '15 at 09:28

Jonah Mann

23
5

I pass in that function only big numbers, so that bug will not appear – Yuriy Zaletskyy Jul 03 '15 at 09:30
1

Yes it will, because it reoccurs back down to num == 1. – Jonah Mann Jul 03 '15 at 09:32

score 1 · Answer 2 · answered Jul 03 '15 at 09:36

Since you only have to remember the previous two terms to calculate the current one, you will not face any memory problem if using a non-recursive procedure :

public static long Fibon(long num)
{
  long result ;
  if (num == 1) { return 1; }
  else if (num=2) { return 1; }
  long grandfather = 1 ;
  long father = 1 ;
  for (in i=2;i<=num;i++) 
  {
    result = father + grandFather;
    grandfather = father ;
    father = result ;
  }
  return result ;
}

score 0 · Answer 3 · answered Jul 03 '15 at 09:54

For nth Fibonacci term the amount of memory needed by your function is O(n), i.e., linear in the index of the term in the Fibonacci sequence. More precisely, it will be n-1 times the amount of memory needed for each recursive call, which is implementation-dependent (plus some constant).

The amount of memory needed is equal to the amount of memory in each recursive call plus the "depth" of the "execution tree". In each recursive call you either terminate or make two new calls, one on the argument n-1 and one on the argument n-2; it is obvious this has to stop after n-1 calls.

If you imagine the whole process as a binary tree with nodes labeled f(k), where the node f(k) has a left child labeled f(k-1) and a right child labeled f(k-2), then the space complexity of f corresponds to the depth of the execution tree.

score 0 · Answer 4 · answered Jul 03 '15 at 10:07

I believe the number of longs needed is actually equal to the returned long.

To return 2, you need to add 2 longs. To return 3, you need to add the number of longs needed to return 2 (which is 2 longs) to 1 which == 3. The pattern continues.

Since a long is 64 bits, the memory needed is equal to the fibonacci value * 64 bits.

Calculate amount of memory needed for recursive function

4 Answers4