This article is all about recusion.
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition. Specifically this defines an infinite number of instances (function values), using a finite expression that for some instances may refer to other instances, but in such a way that no loop or infinite chain of references can occur. The term is also used more generally to describe a process of repeating objects in a self-similar way.
Recursion is basis Dynamic programming, another important area in algorithms.
Best way to learn about recursion is to solve recursion problem.
Recusion problems
Factorial
Given n of 1 or more, return the factorial of n, which is n * (n-1) * (n-2) … 1 Compute the result recursively (without loops).
factorial(1) → 1
factorial(2) → 2
factorial(3) → 6
Total BunnyEars
We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).
bunnyEars(0) → 0
bunnyEars(1) → 2
bunnyEars(2) → 4
Even/Odd BunnyEars
We have bunnies standing in a line, numbered 1, 2, … The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we’ll say have 3 ears, because they each have a raised foot. Recursively return the number of “ears” in the bunny line 1, 2, … n (without loops or multiplication).
bunnyEars2(0) → 0
bunnyEars2(1) → 2
bunnyEars2(2) → 5
Triangle
We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.
triangle(0) → 0
triangle(1) → 1
triangle(2) → 3
Sum of Digits
Given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
sumDigits(126) → 9
sumDigits(49) → 13
sumDigits(12) → 3
Count no 7
Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
count7(717) → 2
count7(7) → 1
count7(123) → 0
Count X in String
Given a string, compute recursively (no loops) the number of lowercase ‘x’ chars in the string.
countX(“xxhixx”) → 4
countX(“xhixhix”) → 3
countX(“hi”) → 0
Count Hi
Given a string, compute recursively (no loops) the number of times lowercase “hi” appears in the string.
countHi(“xxhixx”) → 1
countHi(“xhixhix”) → 2
countHi(“hi”) → 1
Change XY String
Given a string, compute recursively (no loops) a new string where all the lowercase ‘x’ chars have been changed to ‘y’ chars.
changeXY(“codex”) → “codey”
changeXY(“xxhixx”) → “yyhiyy”
changeXY(“xhixhix”) → “yhiyhiy”
public String changeXY(String str) {
}
Change PI
Given a string, compute recursively (no loops) a new string where all appearances of “pi” have been replaced by “3.14”.
changePi(“xpix”) → “x3.14x”
changePi(“pipi”) → “3.143.14”
changePi(“pip”) → “3.14p”
public String changePi(String str) {
}
No X in String
Given a string, compute recursively a new string where all the ‘x’ chars have been removed.
noX(“xaxb”) → “ab”
noX(“abc”) → “abc”
noX(“xx”) → ““
public String noX(String str) {
}
No Star in String
Given a string, compute recursively a new string where all the adjacent chars are now separated by a “*”.
allStar(“hello”) → “h*e*l*l*o”
allStar(“abc”) → “a*b*c”
allStar(“ab”) → “a*b”
public String allStar(String str) {
}
Substring
It’s also convenient to have a function that, given a sentence, selects a small portion
of a sentence for us. For example, if we had the sentence:
(russians declare war rington vodka to be excellent)
We could imagine using a hypothetical subsentence function that would let us pull out the first few words
of that sentence, if we tell it where to start and stop the selection:
(subsentence ‘(russians declare war rington vodka to be excellent) 1 3)
(russians declare war)
(subsentence ‘(no shirt no shoes no service) 4 4)
(shoes)
Write the function subsentence, which takes in three arguments: a sentence, the starting endpoint, and the stopping endpoint. It should return back a sentence that includes the words between the start and stop endpoints. Assume that the user is nice, and won’t give weird input. In Scheme notation, we mean that we can assume (<= 1 start stop (count sent)) is always true.
String permutation non repeating
Write all the non repeating permutations of given string i.e.
For string ABC
ABC, ACB, BAC, BCA, CAB, CBA
Detailed solution with explanation can be found here
This code will output reapeated string if input string given is say ‘ABA’.
To avoid that store all the strings generated in array/hash and compare everytime for uniquesness.
Power (x, n)
Write a C program to calculate pow(x, n)
For e.g
Solution Idea is that if power is even then multiply evenly i.e.
For will be (2 * 2) * (2 * 2)
For will be 2 * (2 * 2)
1 2#include <stdio.h> 3 4float power(float x, int n) 5{ 6 float temp; 7 if( n == 0) 8 return 1; 9 temp = power(x, n/2); 10 if ((n % 2) == 0) 11 return temp*temp; 12 else 13 { 14 if(n > 0) 15 return x*temp*temp; 16 else 17 return (temp * temp) / x; 18 } 19} 20 21int main() 22{ 23 float res = power(2, 4); 24 printf("Result 2^4 = %f \n", res); 25 26 res = power(2, 3); 27 printf("Result 2^3 = %f \n", res); 28 29 res = power(2, -2); 30 printf("Result 2^-2 = %f \n", res); 31 32 res = power(2, -4); 33 printf("Result 2^-4 = %f \n", res); 34 35 res = power(-2, -3); 36 printf("Result 2^4 = %f \n", res); 37 38 return 0; 39}