Recursion – local variables

One of the mysteries of recursion is local variables. Ever time a new instance of a function is invoked, any local variables within the function (including parameters) are allocated a new piece of memory. This is one of the reasons why recursive functions can become resource heavy. To illustrate the memory allocations of local variables, consider the following C function reMem(). On a side note, C is a great language for looking into low-level things because it provides the format specifier %p, which prints the address of a pointer or any other variable.

include 
 void reMem(int n)
 {
    printf("level %d: location of n -> %p\n", n, &n);
    if (n < 5)
       reMem(n+1);
 }
 int main(void)
 {
    reMem(1);
    return 0;
 }

The function reMem() recurses down five levels, at each level of the recursion it prints the level number, and the memory address of the local variable n. Here is the output from the program, showing the differing hex addresses when each instantiation of n is stored.

level 1: location of n -> 0x7fff5e69ca2c
level 2: location of n -> 0x7fff5e69ca0c
level 3: location of n -> 0x7fff5e69c9ec
level 4: location of n -> 0x7fff5e69c9cc
level 5: location of n -> 0x7fff5e69c9ac

This can also be achieved in Fortran using the intrinsic loc() function.

program recurseMemory
   call reMem(1)
contains
   recursive subroutine reMem(n)
      integer, intent(in) :: n
      integer :: m
      m = loc(n)
      write(,) 'level ',n,': location of n -> ',m
      if (n < 5) then
         call reMem(n+1)
      end if
   end subroutine reMem
end program recurseMemory

The output here represents the memory addresses as integers:

level            1 : location of n ->    185261820
level            2 : location of n ->   1421158904
level            3 : location of n ->   1421158360
level            4 : location of n ->   1421157816
level            5 : location of n ->   1421157272

This illustrates that even something as innocuous as a single parameter passed to a function can have resource issues when related to stack storage.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.