(DS1) Recursion

(DS1) Recursion

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


Q. List the properties of recursive functions.
notion image
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.
notion image
Q. What are the advantages and disadvantages of recursion?
notion image
Q. What is the difference between iteration and recursion?
notion image

Code Examples


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.
notion image
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).
(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

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(); }