[Leetcode] Memory and Recursion

Posted on | In , , |

Memory and Recursion

  • Heap: Used for dynamic allocation of memory. Once done, variables are available in Garbage Collection.
  • Stack: Functions waiting to execute are stored here, once executed, they are popped out of stack. (FIFO) Each function in the stack will create a frame to store local variables
  • Static Area: Store machine code, global static variables
    1
    2
    3
    4
    5
    6
    7
    8
    ------------
    |   Heap   |
    |----------|
    |   Stack  |
    |----------|
    |Static Var|
    |   Code   |
    |__________|

[Recursion]

  • Introduction: https://www.youtube.com/watch?v=neuDuf_i8Sg
  • A method that calls itself
  • With each method call the problem becomes simpler
  • Must have a condition that leads to the method no longer making another method call on itself

Tail & Non-Tail Recursion

Understand Tail Recursion: http://www.ruanyifeng.com/blog/2015/04/tail-call.html

[Recursion]

The general recursion solution for fibonacci problem will have exponential memory usage. 2^(n-1)

1
2
3
4
int factorial(int n) {
  if (n==0) return 1;
  return n*factorial(n-1);
}

[Tail Recursion]

Call function itself at the last step of the function.

  • No pending computation
  • Reuse existing stack frames
  • Use constant memory space, avoid stack overflow

To transform a non-tail recursion, we can add all the local variables as arguments to the function.

1
2
3
4
5
6
7
int factorial(int n) {
  return fact(n,1);
}
int fact(int n, int result) {
  if(n==0) return result;
  fact(n-1, n * result);
}