What is Recursion?
A function that calls itself is called a recursive function.

In this article, we are going to see how recursion uses Static and Global Variables with the help of examples.

Table of Content

• INTRODUCTION
• Recursion Without using Static and Global Variables
• Static Variables in Recursion
• Global Variables in Recursion
• Conclusion

INTRODUCTION

We already know that recursion uses stack and that the memory is divided into three sections i.e. code section, stack and heap.
If a problem can be used repeatedly and split in the same way, recursive functions can be used to solve such problems.

Principles of writing recursive functions

1. Use sentences to describe the splitting method of the problem in the function
2. Use a branch at the beginning of the function to handle the inseparable situation separately (the function should end after the processing is completed)

Recursion Without using Static and Global Variables

To visualise how the static and global variables perform in recursion, let’s first take an example where we can see how the stack is created and utilised in a recursive function.
We, have a following simple recursive code in C language:

Implemented Code:

#include <stdio.h>
int fun (int n)
{
    if (n > 0)
    {
        return fun (n-1) + n;
    }
    return 0;
}

int main ()
{
    int a = 5;
    printf ("%d", fun(a));
    return 0;
}

Output

15

Code Explanation:
In the above code we have two functions : fun() and main() function. These two will appear in the code section of the main memory.
The program execution starts from the main functions and then the next fun function() is executed.
Inside the stack, the activation record for the main function is created and it will have its own variable that is x variable containing the value 5.
The first call fun() makes is to store 5 in n that also appears in the activation record in stack. Again, the recursive call fun(n-1) is made and now n will store 4.
This goes on till the termination condition is achieved that is (n>0) and from here the activation records starts getting deleted and the pervious recursive functions are called and completed.

Static Variables in Recursion

Static variables are created inside the code section especially maintained for global and static variables.
This also means that unlike previously, instead of being created every time in program when the function is called. Static variables are created only once at the loading time of the program.
All the recursive calls will use the same copy of x, but for n every time a new copy is created.
The following program in C language uses a static variable x:

Implemented Code

#include <stdio.h>
int fun1(int n)
{
    static int x=0;
    if (n > 0)
    {
        x++;
        return fun1 (n-1) + x;
    }
    return 0;
}

int main ()
{
    int a = 5;
    printf ("%d", fun1(a));
    return 0;
}

Output

25

Code Explained:
As discussed we see that the static variable x is created inside the code section and only one copy is made and used.
The following diagram shows all the activation record made as the recursive function fun1() is called again and again.
After the termination condition of (n<0) is reached the call terminates and the activation records starts getting deleted. And the previous calls are completed with the output printed.

Global Variables in Recursion

Similar to static variables, global variables are too formed inside the code section and are formed only once. So, only one copy is available while the program and recursive function is executed.
The following program in C language uses a global variable x:

Implemented Code

#include <stdio.h>
int x=0;
int fun (int n)
{
    if (n > 0)
    {
        x = x + 1;
        return fun (n-1) + x;
    }
    return 0;
}

int main ()
{
    int a = 5;
    printf ("%d", fun(a));
    return 0;
}

Output

25

Code Explained:
Variables declared outside a function are called global variables.
Since we already know that global variables are also formed inside the code section just like static variable.

Conclusion:

With this article at OpenGenus, you must have the complete idea of Static and Global Variables in Recursion.

Sometimes the result is inconsistent with our expectations because of not paying attention to the local variables and global variables in the recursive function.
Hence it was necessary to understand the lifetime and scope of static and global variable sin recursion which we have covered in detaisl in this chapter.