(DS1) Recursion

Questions Code Examples Factorial Multiplication of Natural Numbers Fibonacci Sequence Binary Search Towers of Hanoi Length of A String Copy One String to Another Palindrome Strings

It’s just a function that calls itself until a particular exit condition is met.

Questions

Q. List the properties of recursive functions.

Q. What are recursive chains?

It refers to the fact that a function need not call itself to be recursive. Two functions can call each other too.

Q. What are the advantages and disadvantages of recursion?

Q. What is the difference between iteration and recursion?

Code Examples

Factorial

If n == 0 or n == 1, then the factorial of the number will be 1 itself. Otherwise, the function will call itself for each n-1 value.


int factorial(int n) {
	if (n == 0 || n == 1) {
		return 1;
	} else {
		return n * factorial(n-1);
	}
}

(C actually has a built-in tgamma() function, in the <math.h> header. This isn’t necessary.)

Multiplication of Natural Numbers

The product a * b, where a and b are positive integers, is defined as a added to itself b times, which is an iterative definition.


int multiply(int a, int b) {
	if (b == 1) {
		return a;
	} else {
		return a + multiply(a, b-1);
	}
}

(I believe this just exists to prove how bloated recursion can be.)

Fibonacci Sequence

Each element here is the sum of two preceding elements. The Fibonacci number for 0 or 1 is the number itself, so they’ll act as the exit condition.


int fibonacci(int n) {
	if (n == 0 || n == 1) {
		return n;
	} else {
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

Binary Search

Honestly the first implementation of recursion that I find useful. It cuts down the array in half with every iteration, thus making the complexity O(log n).

Recommended Video - https://www.youtube.com/watch?v=P3YID7liBug

(Tom Scott’s video for more useless information - https://www.youtube.com/watch?v=KXJSjte_OAI)


int search(int item, int list[], int low, int high) {
	int mid;
	if (low > high) {
		return -1; // "bro please give a proper input"
	}
	mid = (low + high) / 2;
	
	if (item == list[mid]) {
		return mid;
	} else if (item < list[mid]) {
		high = mid - 1; // cut the top half off
		return search(item, list, low, high);
	} else {
		low = mid + 1; // cut the bottom half off
		return search(item, list, low, high);
	}
}

Towers of Hanoi

Recommended Video - https://www.youtube.com/watch?v=rf6uf3jNjbo

A Shorter Video - https://www.youtube.com/watch?v=YstLjLCGmgg


void towers(int n, char source, char temp, char destination) {
		if (n == 1) {
				printf("move disk 1 from %c to %c", source, destination);
				return;
		}

		// moving n-1 disks from A to B using C as auxiliary
		towers(n-1, source, destination, temp);

		printf("move disk %d from %c to %c", n, source, destination);

		// moving n-1 disks from B to C using A as auxiliary
		towers(n-1, temp, source, destination);
}

Length of A String


int strLen(char *str) {
		static int length = 0;
		if (*str != '\0') {
				length++;
				strLen(++str);
		}
		return length;
}

Copy One String to Another


void copy(char str1[], char str2[], int index) {
		str2[index] = str1[index];
		if (str1[index] == '\0') return;
		copy(str1, str2, index + 1);
}

Palindrome Strings


void main(){
		char inputString[100];
		printf("Enter a string for palindrome check\n");
		scanf("%s", inputString);
		if(isPalindrome(inputString, 0, strlen(inputString) - 1))
				printf("%s is a Palindrome \n", inputString);
		else 
				printf("%s is not a Palindrome \n", inputString);
		getch();
}