More Recursion in C

Recursion is a repetitive process where a function calls itself directly or indirectly. A function is directly recursive when it calls itself from within its scope, and it is indirectly recursive when it calls other functions that eventually calls it back.

In general, we use two approaches to writing repetitive algorithms. The first approach is the iterative approach using loops, the other uses recursion.  For example, let’s consider a factorial:

factorial (n) = 1 if n = 0
                n * (n -1) * (n -2) ... 1 if n > 0

A repetitive function is iterative when the definition of the function involves only the parameters and not the function itself. A repetitive function is defined recursively whenever the function appears within the definition itself. To look at factorials again, we would define them as:

factorial(n) = 1 if n = 0
               n * factorial(n - 1) if n > 0

 

We will write two functions, one two solve the factorial problem in an iterative manner, and the other to solve the factorial problem in a recursive manner.

#include <stdio.h>
#include <stdlib.h>

long itFactorial(int n){
    int i;
    long rValue = 1;
    for(i = 1; i <= n; i++){
        rValue = rValue * i;
    }
    return rValue;
}

long recFactorial(int n){
    if(n==0) { return 1;}

    return n * recFactorial(n-1);

}

int main()
{

    printf("%li\n", itFactorial(7));

    printf("%li\n", recFactorial(7));

    return 0;
}

Recursive functions have two elements, solving one part of the problem, and/or reducing the size of the problem. The call that delivers a definitive solution is known as the base case. Every recursive function must have a base case.

When implementing a recursive function, we should bear in mind how the function’s arguments are put on the stack. The stack frame grows by push operations caused by function calls, and it shrinks by pop operations by function returns. Each call gets a fresh copy of automatic variables that are totally independent of the previous set of values.

A popular example of a recurrence relation is the Fibonacci sequence, in which a number is the sum of the previous two numbers. The first few numbers of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. To start the sequence, we define the first two numbers as 0 and 1, so that the third number is also 1 (0 + 1), and the fourth number in the sequence is 2 (1 + 1).

We will see two examples of the recursive Fibonnaci function.

#include <stdlib.h>
#include <stdio.h>

int fibA(int iParam){
    int rValue;

    //base case for 0 and 1 in the sequence
    if(iParam == 0 || iParam == 1) { return iParam; }

    //calls itself twice
    rValue = fibA(iParam - 1) + fibA(iParam - 2);

    printf("Returning %d\t", rValue);

    return rValue;
}

int fibB(int iNum, int iPrevOne, int iPrevTwo){
    int rValue;

    if(iNum == 0){
        printf("iNum == 0, returning %d\n", iPrevTwo);
        return iPrevTwo;
    } else if (iNum == 1){
        //when count reaches 1, returning back the final number
        //reached by adding iPrevOne and iPrevTwo
        printf("iNum == 1, returning %d\n", iPrevOne);
        return iPrevOne;
    } else {
        printf("%d, %d, %d\n", iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        rValue = fibB(iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        return rValue;
    }
}


int main()
{

    int i = 0;

    printf("\nfibA(5) = %d\n", fibA(5));
    printf("\nfibA(8) = %d\n", fibA(8));

    printf("\nfibB(7) = %d\n\n", fibB(7, 1, 0));
    printf("\nfibB(9) = %d\n", fibB(9, 1, 0));

    return 0;
}

We can also use a recursive function to find the greatest common denominator. The function will return the second parameter if the first parameter modulo the second parameter is 0, meaning that they divide evenly. Otherwise, the function will call itself, with the second parameter as the first argument, and the remainder of the modulo operation as the second argument.

#include <stdlib.h>
#include <stdio.h>

int findGCD(int a, int b){
    int remainder;
    if((remainder = a % b) == 0){
        return b;
    }
    return findGCD(b, remainder);
}


int main()
{
    printf("The GCD of 100 and 8 is %d\n", findGCD(100, 8));
    printf("The GCD of 150 and 5 is %d\n", findGCD(150, 5));

    return 0;
}

One of the most famous examples of a recursive s0lution is the Towers of Hanoi problem, but we will look at that at another time.

 

 

 

 

Advertisements

Very Short Look at the Big O and Nested For Loops

Big O notation is used to indicate the runtime of an algorithm as it processes large amounts of data, in which case the determining factor of the execution time is the term with the largest exponent, ignoring all other terms and even the coefficient as the data set to be processed grows extremely large. Big O notation therefore drops the constants, which can be confusing.

#include <time.h>
#include <stdlib.h>

void populateArray(int array[], int size, int num_max);
void printArray(int arrayParam[], int size);
void minMaxA(int iArray[], int size, int num_max);
void minMaxB(int iArray[], int size, int num_max);

int main() {
	
	const int array_size = 2056;
	const int num_max = 7800;

	int iArray[array_size];
	int iMax = 0;

	populateArray(iArray, array_size, num_max);
	printArray(iArray, array_size);

	minMaxA(iArray, array_size, num_max);
	minMaxB(iArray, array_size, num_max);

	return 0;

}

void printArray(int arrayParam[], int size) {
	int *iArray = arrayParam;
	for (int i = 0; i < size; i++) {
		printf("%d ", *iArray++);
	}
}

//populate the array with random numbers
void populateArray(int array[], int size, int num_max) {
	srand(time(NULL));
	for (int i = 0, x = 0; i < size; i++) {
		x = rand() % num_max;
		array[i] = x;
	}
}

//one loop 
void minMaxA(int iArray[], int size, int num_max) {
	int iMin = num_max;
	int iMax = 0;
	for (int i = 0; i < size; i++) {
		//check for minimum 
		if (iArray[i] < iMin) { iMin = iArray[i]; } 		       //check for maximum 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}

//two loops
void minMaxB(int iArray[], int size, int num_max) {
	//start search from highest value
	int iMin = num_max;
	//start search from lowest value
	int iMax = 0;
	//loop one
	for (int i = 0; i < size; i++) {
		if (iArray[i] < iMin) { iMin = iArray[i]; }
	}
	//loop two
	for (int i = 0; i < size; i++) { 		
                if (iArray[i] > iMax) { iMax = iArray[i]; }
	}

	printf("\nThe maximum value is %d\n\n", iMax);
	printf("\nThe minimum value is %d\n\n", iMin);
}


Note that the minMaxA() and minMaxB() functions have the same time complexity, since we drop the coefficient. Likewise, we drop all other other non-dominant terms, meaning that the term or terms with the largest exponents are the only ones that we need to concern ourselves with.

void printSumProducts(int iArray[], int length);

int main() {
	
	int iArray[7] = {73, 4, 8, 15, 16, 23, 42 };
	printSumProducts(iArray, 7);

	return 0;

}


//this function takes O(2) time
//the fact that it loops twice is irrelevant 
void printSumProducts(int iArray[], int length) {
	long long int sum = 0;
	//initialize product to 1, not 0
	long long int product = 1;

	for (int i = 0; i < length; i++) {
		sum += iArray[i];
	}

	for (int i = 0; i < length; i++) {
		product *= iArray[i];
	}

	printf("Sum of the array: %lld\n", sum);
	printf("Product of the array: %lld\n", product);

}

Runtimes tend to increase as loops are called within loops. For example, a nested loop that iterates through the entire list once for each loop as O(n^2) time.

void printPairs(int iArray[], int arraySize);
void printUnorderedPairs(int iArray[], int arraySize);

int main() {
	
	const int array_size = 10;

	int iArray[array_size] = { 1138, 151, 191, 47, 353, 383, 16, 32, 64, 128 };

	printPairs(iArray, array_size);

	printf("\n\n");

	printUnorderedPairs(iArray, array_size);

	return 0;

}

//both of these functions take O(n^2) time
void printPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) { 		
           for (int j = arraySize - 1; j >= 0; j--) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

//inner loop starts at i + 1
//stil takes O(n^2) time
void printUnorderedPairs(int iArray[], int arraySize) {
	int iNumPairs = 0;
	for (int i = 0; i < arraySize; i++) {
		for (int j = i + 1; j < arraySize; j++) {
			printf("(%d, %d) \t", iArray[i], iArray[j]);
			iNumPairs++;
		}
		printf("\n");
	}
	printf("Printed %d pairs total.\n", iNumPairs);
}

Even though the second function performs roughly half as many operations as the first, it still has the same time complexity.

Another illustration of this is given with the following code, which contains a function that reverses an array.

void reverseArray(int array[], int lengthParam);
void printArray(int array[], int length);

int main() {
	
	const int array_length = 11;

	int iArray[array_length] = { 10538, 1, 451, 47, 1865, 73, 6174, 1701, 2001, 8675309, 8086 };

	printArray(iArray, array_length);
	reverseArray(iArray, array_length);
	printArray(iArray, array_length);

	return 0;

}


void reverseArray(int array[], int lengthParam) {
	int halfLength = lengthParam / 2;
	int temp;
	for (int i = 0, j = lengthParam - 1; i < halfLength; i++) {
		temp = array[i];
		array[i] = array[j - i];
		array[j - i] = temp;
	}
}

void printArray(int array[], int length) {
	for (int i = 0; i < length; i++) {
		printf("%d ", array[i]);
	}
	printf("\n\n");
}

Even though our reverseArray() function only goes through half of the array, or less, the big O time is still considered to be O(n).

 

 

Pointer pointers

Pointer pointers are pointers that point to pointers. We’re really down the rabbit hole, folks.

A pointer pointer is a memory location that holds the address of a pointer. We use pointer pointers when attempting to manipulate another pointer by reference, essentially. We mostly encounter pointer pointers in the wild when dealing with dynamically allocated data structures that need to be passed ‘by value’ to a function.

A pointer pointer will hold the address of a pointer, which in turn holds the address of the block of data we want to work with. Pointer pointers are can also be called double indirection.

Pointer pointers aren’t as difficult as they sound, but they’re as far out as I personally am willing to get.

int main() {

	int iNum = 42;
	int *iNumPtr = NULL;
	int **iNumPtrPtr = NULL;

	printf("The address of the actual data is %p and it holds %d\n", &iNum, iNum);
	
	//assign address of iNum to iNumPtr
	iNumPtr = &iNum;

	printf("The address of the pointer to the data is %p and it holds %p\n", &iNumPtr, iNumPtr);

	//assign address of iNumPtr to iNumPtrPtr
	iNumPtrPtr = &iNumPtr;

	printf("The adress of the pointer to the pointer to the data is %p and it holds %p\n", &iNumPtrPtr, iNumPtrPtr);


	printf("We can access the original data via the pointer pointer. It's %d!!!\n", **iNumPtrPtr);

	return 0;

}

One of the virtues of pointer pointers is that they enable us to perform the dynamic initialization of arrays and strings from within a function. We note here that the C language copies all function parameters onto the stack, thus creating a unique variable that we then use as a local variable in the function. To pass by value, we pass the function the address of the data we wish to use locally in the function, which is then copied onto the stack. So within the function, the pointer itself is a unique copy, even if the data it points to has scope outside the function.

void workingWithParameters(char *string, char **szPtr);

int main() {

	char *string = "Nice boat!";

	printf("The address of the string is %p\n", &string);
	printf("And its value is %s\n", string);

	workingWithParameters(string, &string);

	printf("Back in main() the value is now %s\n", string);

	return 0;

}


void workingWithParameters(char *string, char **szPtr) {
	printf("The address of the string on the stack is %p\n", &string);
	printf("But back in main() the string is located really at %p\n", *szPtr);
	printf("And its value is %s\n", *szPtr);
	*szPtr = "For great justice!";
}

 

Pointer pointers are typically used as function parameters. It’s important to remember that all function parameters are local to the function, even ones that are passed by reference via the pointer mechanism.

Memory Management and Strings in C

C has an extremely flexible – some would say, dangerous – ability to allocate, use, and deallocate memory. Memory can be allocated statically, dynamically, or automatically in C. Static memory allocation occurs when variables are declared with the static keyword, and have scope set to the file; static memory also occurs when variables are declared outside the scope of any function, these variables may be used globally via the extern keyword. Dynamic memory allocation is the result of calling malloc() or another related function to get memory from the heap, and persists until free() is called. Automatic memory allocation occurs when a variable is declared within a function.

One of that nice things about static variables is that we can declare them within a function, and yet they persist beyond the lifetime of a function.

int useStaticVar(int iNum = 1);

int main()
{

	int i = 1;
	int iSum = 0;
	while (i++ < 10) {
		useStaticVar(i);
	}
	
	printf("Value is %d\n", useStaticVar());

    return 0;
}


int useStaticVar(int iNum) {
	static int iProduct = 1;
	iProduct *= iNum;
	return iProduct;
}

Remember, automatic variables are allocated on the stack. They are allocated and deallocated for us when the program enters and leaves their scopes.

Both automatic and static variables share the same problem – their size must be declared, and therefore known, at compile time. Dynamic memory allocation allows memory to be allocated by the program while it is running as needed. The malloc() function enables us to allocate variable amounts of memory that can be utilized via a pointer that is returned by the function.

#include <stdlib.h>
#include <string.h>

char * allocateString(int iLength);

int main()
{
	char * ourString = allocateString(256);
	strcpy_s(ourString, 256, "With sufficient thrust, pigs fly just fine.");

	printf("%s\n", ourString);

    return 0;
}

char * allocateString(int iLength) {
	char *str = NULL;
	if (iLength > 0) {
		str = (char*)malloc(iLength);
	}
	return str;
}

Note that to modify a pointer that is a parameter in a function, we must pass it as a pointer to a pointer, using **.

#include <stdlib.h>
#include <string.h>

#define STRING_LENGTH 256

void appendString(char ** szTarget, int iTotalLength, char *szSource);

int main()
{
	char *szString = (char *)malloc(STRING_LENGTH);
	strcpy_s(szString, STRING_LENGTH, "A strange game.The only winning move is not to play.");
	appendString(&szString, STRING_LENGTH, " All your base are belong to us.");

	printf("%s\n", szString);

    return 0;
}

void appendString(char ** szTarget, int iTotalLength, char *szSource) {
	int i = 0;
	int j = 0;
	//with single indirection, the pointer arithmetic would be
	//*(szTarget+i)
	//with double indirection, we have to deallocate once
	//just to get to where we would be with single indirection
	while (*(*szTarget+i) != '\0') { i++; }

	iTotalLength--;
	while ((i < iTotalLength) && (*(szSource + j) != '\0')) {
		*(*szTarget + i) = *(szSource + j);
		i++;
		j++;
	}

	*(*szTarget + i) = '\0';
}

Converting an integer to a string is fun, but there are three things to bear in mind. First, the characters that make up strings themselves have an integer value, which is set by the ASCII standard. To get the ASCII equivalent of an integer between 0-9, we need to add the integer value of the character 0 to the integer. Second, while strings in English are read left to right, numbers are read right to left. This means that the easiest thing to do for us will be to write the string equivalent of the integer backwards.

Finally, we should keep in mind that the value of any digit in a number is the digit itself multiplied by 10 for each place it is left of the starting position.  So, for example, the ‘9’ in 90210 itself is 9 * 10 * 10 * 10 * 10, or 90,000. The ‘2’, therefore, is 2 * 10 * 10, or 200.

#include <stdlib.h>
#include <string.h>

#define STRING_LENGTH 256

char * intToString(int iNum);

int main()
{
	char *s = intToString(8675309);

	printf("\n%s\n", s);

    return 0;
}

char * intToString(int iNum) {

	int iNumCopy = iNum;
	int iLength = 0;
	
	//numbers are read right from left, not left to right 
	//as words are
	do {
		iLength++;
		printf("iNumCopy = %d\n", iNumCopy);
		iNumCopy /= 10;
	} while (iNumCopy != 0);

	printf("Number has %d places\n", iLength);

	//one extra char needed 
	char *rString = (char *)malloc(iLength + 1);

	//terminate string
	*(rString + iLength) = '\0';

	while (--iLength >= 0) {
		printf("%d\n", iNum % 10);
		*(rString + iLength) = (iNum % 10) + '0';
		iNum /= 10;
	}

	return rString;

}

Please note that the example above does not, for reasons of simplicity, handle negative numbers. However, it would be easy enough to add that capability.

Incidentally, reversing a number is even easier. We just have to remember that multiplication and division are the opposites of each other.

#include <stdlib.h>

int reverseNumber(int iNum);

int main()
{
	int i = 73;
	int j = reverseNumber(i);

	int x = 501;
	int y = reverseNumber(x);

	printf("%d \t %d\n", i, j);
	printf("%d \t %d\n", x, y);

    return 0;
}

int reverseNumber(int iNum) {
	int iReturnNum = 0;
	while (iNum != 0) {
		//shift iReturnNum left one position
		//except when at the first position
		//as 0 * 10 = 0
		iReturnNum *= 10;
		iReturnNum += iNum % 10;
		//dividing by 10
		//removes the rightmost digit 
		//from an integer
		iNum /= 10;
	}

	return iReturnNum;
}