In this article i’ll explain about pointers in computers, it’s behaviour and it’s usage with the programming language of C++.

When we refer to Computers or Systems Architecture there are 2 types of softwares ~ System Software & Application Software.
Whether implemented in System or Application Software, almost all data structures make extensive use of pointers and addresses.

A pointer is a data element containing the address of another data element.

An address is the location of a data element in a storage device. Addresses vary in content and representation, depending on the storage device being addressed.

Why we need pointers? 🤔

Normally a program being executed can only directly access the code section & stack. The program can’t directly access the heap because it is external to the program. Monitors, keyboards, files and even the internet network connections are all external to a program.

Since the program cant directly access these external components, it can use the help of Pointers to gain access to it.
As shown above, the program should have a Pointer created for it to be used to access anything external like heap, which could be some data type of an integer or even an array.

Memory Addresses & Model

Memory addresses can be complex if a segmented memory model is used. For the purpose of discussing pointers in data structures, a flat memory model is used, and memory addresses are represented by nonnegative integers.

Declaring & Initialisation of a Pointer

Let’s assume that the size of an integer is 2 bytes.
As shown above, a data block is created for the variable A and the pointer P. Both of these data blocks will be created during program execution inside the stack area.
As we can see during the declaration of a pointer or de-referencing of the pointer value, we use the * syntax.
When we assign/initialise we use the & syntax.

Reference in Data Structure using C++

Reference is an alias to a variable. If we declare a reference to another variable, we get to change that variable value at two places instead of one.
Therefore changing the variable at any one place will permanently change the values at both places.

Normally references are used for parameter passing.
This is a very useful feature in C++.

Pointers for Parameter Passing

There are 3 types of parameter passing.
Pass by value, Pass by address and Pass by reference.

Pass By Value

From the above code, parameters within the Swap() function inside main() function are called ACTUAL parameters. Parameters from the Swap() function, above the main() function are called FORMAL parameters.

As the program executes;
Within the Swap() function, a’s value is swapped with b’s value.
Once the Swap function is done executing, the printf() function would execute. But the values for a and b won’t be changed because the variables were passed by value. They won’t be affected outside the Swap() function.
Therefore, only the FORMAL parameters will be affected and not the ACTUAL parameters.

PASS BY ADDRESS

As shown above, variables are passed into the Swap() function by using the address of the variables because the now the Swap() function accepts parameters as pointers.
Whenever a pointer is used as a parameter we need to pass the address of the variable. This would make the pointer point to the address of the variable thus having the ACTUAL parameter’s value of the variable.

Therefore, printing the values using printf() function would show us the swapped values accordingly. Pass by address permanently changes the ACTUAL parameter’s value.

PASS BY REFERENCE

As shown above, the FORMAL parameters are the only changes made here. We added the & syntax (which is only available in C++) to denote the calling by reference of the variable. Once the Swap() function is executed, printf() function would show us the swapped values accordingly.

The advantage of using pass by reference over pass by address is it doesn’t take up more memory. Because for pass by reference, after compilation; the code section of the memory will merge the main() and Swap() function together.
Therefore, no extra activation records are created within the Stack area during program execution, thus the same variable values are used for computation.

That’s all folks. 😎🐍
I hope we all learn something useful about pointers in data structures.
I hope i’ll receive some feedbacks and comments about my article.

Please follow my mini-series on Data Structures…

👉🏾 Data Structures using (C++) ~ Basics & Main Memory Section

What are pointers ?? 🤔 was originally published in Thoughtful-Navin on Medium, where people are continuing the conversation by highlighting and responding to this story.

Greetings Everyone… 👋🏾
In this post, i would like to talk about tracing recursive functions & how we can tackle tracing different other type of functions in C++ language.

I would demonstrate two significant types of recursive functions to vaguely demonstrate the behaviour of computers, its main memory section during a recursive call.

Example 1: Recursive function with static variables
Example 2: Recursive function with for-loop

I will also share the crafty techniques i’ve learnt to solve large tracing problems more easily using the power of mathematics.
Im no Mathematician; but i will try to impart the beauty of simple mathematics which helped me solve problems easily.

Example 1: Recursive function with static variables

Let me run through the function behaviour once:

• Once the function is called, the static variable will be assigned with value 1.
• Then the function will check the variable n is ≥ 5.
  If the IF condition checks out, it stops the function from further propagating down the tree & returns the final value.
  Else it skips pass the IF condition
• variable n is assigned a new value by adding the static variable i to it.
• static variable i is incremented by 1.
• the function returns itself with a new value of variable n.

The interesting part of this function is the static variable i. As we discussed about static variables on my previous post we now, know that static variables are only created once within the code section (single copy) therefore, its being reused on every recursive call, if any.

Lets look at the tracing of this function:

We can see that the variable n value is updated according to the updated static variable i’s value, as per the (n=n+i;) statement call.
As we can see the static variable is declared outside the tracing tree.
This denotes that on every (f(n)) statement call, the updated i variable value is used instead because the static variable is created only once within the code section of the main memory.

The static variable i is created during the loading time of the program.

Whereas; compared to a non-static variable declaration within a function, those variables are created within the stack area on every function call. This means the variable value wont be reused like the above function.

Example 2: Recursive function with for-loop

Let me run through the function behaviour once:

• Once the function is called, the variables k & x will be declared and x will also be initialised with value 1.
• Then the function will check if the variable n is = 1.
  If the IF condition checks out, it stops the function from further propagating down the tree & returns the value x.
• Else it skips pass the IF condition and runs the FOR-LOOP condition until the condition
  (k < n) is not met.

Let’s trace it using the conventional way; only for the first part of the function.

As we can see that the recursive calls are made inside the for-loop. For our example above, the value given is 5. As it iterates through the loop it checks if the mutating variable k is less than the variable n which has the value of 5.

From tracing the first part of the function; we can deduce that tracing each recursive function will lead to a tedious amount of effort 🖊. Fred not, we can break this problem into smaller sub problems; by first solving the entire function with the smallest value of 1.

When the value is 1, the function returns the value of x.
The output value for fun(1) is 1.

Lets create a table with the n values in row 1 & fun(n) values in row 2
& update it accordingly:

When the value is 2, the function iterates only once.

From the table we already know the value for fun(1).
The final equation & output value for fun(2) would be (1 + 1 * 1 = 2 ).

Updated table:

When the value is 3, the function iterates twice.

From the table we already know the value for fun(1) & fun(2).
The final equation & output value for fun(3) would be
(1 + 1 * 2 + 2 * 1 = 5).

Updated table:

Now we realise that by breaking down the problem, it’s helping us to solve our rather daunting tracing task in hand. As we move on to solve fun(4), we can deduce a cute mathematical pattern here.
For fun(4), the loop iterates thrice because k is 1 and n is 4 so; (4 –1 = 3).
Yea we all know that, but if we lay them as 1, 2, 3 sequentially, we can see if whether the set contains odd or even numbered values. Then we can just use its values of n to perform the mathematical operations.

Odd => ( A, B, C )
Step 1: A * C
Step 2: B * B
Step 3: C * A

Even => ( A, B, C, D)
Step 1: A * D
Step 2: B * C
Step 3: C * B
Step 4: D * A

I hope everyone is able to realise that there is a mathematical pattern here. Maybe, there is a formal name for this type of pattern and if anyone knows it, please feel free to leave a comment or something.
Thank you in advance 🙏🏾.

Moving on; we can then use this pattern to help us solve our tracing problem faster, for the remaining values 4 & 5.

Voila, we got the chance to learn tracing recursive functions & also learnt how to solve a rather rudimentary recursive tracing problem more efficiently with some cute mathematical pattern 😝.

I hope everyone have learnt something from this article.
Please feel free to leave comments, just about anything related to this article content.

This is a series on Data Structures using C++.
Please feel free to check out my other articles related to this topic.

Cheers 🐍

Data Structures using (C++) ~ Tracing Recursive Functions was originally published in Thoughtful-Navin on Medium, where people are continuing the conversation by highlighting and responding to this story.

Greetings Everyone 👋🏾

Im here to share my knowledge on what i’ve learnt about Data Structures in Computer Science. Many of us reading this, might have a good amount of knowledge in this, but i’ve also realised many of us including me; don’t really know how to do it or how to use it in practical situations.

Im coming from an electrical engineering background out of college. Having the knowledge of how electricity is generated, stored & used, I always wondered how any sort of data is created, stored, converted and distributed within a computer.

I was always intrigued of the workings and capabilities of a computer using Data Structures.
Therefore, i have planned to write a mini series on Data Structures encompasses only of those details we might have missed out in school or while we were learning.
I hope i’m also able to shed some light on the inner workings & behaviour of the main memory with data. In this series, i will only be using the language C++ to demonstrate the function codes.

What is Data Structure/s ??

A Data Structure is a related group of primitive data elements organised for some type of common processing and is defined and manipulated in software. Computer hardware can’t manipulate data structures directly; it must deal with them in terms of their primitive components, such as integers, floating-point numbers, single characters, real numbers, boolean & even memory addresses.

Computers can also process more complex data, such as strings, arrays, text files, databases & digital representations of audio and image data, such as MP3, JPEG and MPEG files.

Complex data formats are commonly manipulated by system and application software by combining primitive data items to form useful aggregations. Therefore, developing programs of any kind just with primitive data types would be difficult.

In our series, we will regularly be touching on the main memory of a computer. It is also called the Random Access Memory (RAM).
I will be discussing on the different behaviours of the RAM in relation to the different data structures in use.

How does a Main Memory (RAM) look like ??

Let’s go from the bottom
Once the C/C++ program is compiled, any Static and Global variables, functions and the main function will be located in the Code Section. This is done with the help of the compiler and linker. Therefore, Static and Global variable’s value can be re-used in a function to satisfy certain purpose or functionality. As we move on further in this series, you’d see examples of such usages.

Within the Stack area, those local variables within a function and function parameters if any; will appear within the stack area. It piles upwards as the application program calls on every other function to execute the given instruction by the user. Stack area can run out of space and this usually happens when a function runs infinitely.

The Heap area is where more of the run-time dynamic allocations are done.

In C language, the allocation is done using the malloc function &
in C++ language, allocation is done using the new operator.

Every dynamic memory allocated must be manually deleted by the programmer using the delete operator because of the usage of pointers.

To learn about pointers goto my other article on pointers
👉🏾 What are pointers ?? 🤔

The block of memory size initialised during run time would be
(5 * 4(size of integer) = 20 bytes). The malloc function in C language is used to dynamically allocate a single large block of memory with the specified size. In our series on Arrays, we will see more usage of this function with 2 Dimensional arrays.

That’s all for now folks. 🤗 🐍
As this article is published on 01/01/2020; I would like to wish every living thing on this planet a Happy New Year 2020. It’s the start of a new decade, so let’s set some serious goals and focus on the process that helps accomplish our goals. 🌎 🎆

Stay tuned for new updates on this series.
👉🏾 Data Structures using (C++) ~ Tracing Recursive Functions

Data Structures using (C++) ~ Basics & Main Memory Section was originally published in Thoughtful-Navin on Medium, where people are continuing the conversation by highlighting and responding to this story.