Assignment $1$: Recursion, Linked Lists, Stacks, and Queues

Harmonic number

Create a recursive solution for computing the $n^{th}$ Harmonic number, defined as $H_n={\displaystyle \underset{k=1}{\overset{n}{}}}\frac{1}{k}.$

Product of two numbers

Create a recursive solution to compute the product of two positive integers, $m$ and $n,$ using only addition and subtraction.

Find a bit in a binary string

You are given two positive integers i and $n.$ The binary string $S_n$ is formed using the following formula:

$S_1="1"$

$S_n=S_{n-1}+"0"+$ invert reverse $(S_{n-l}))$ for $n>1$

Where $+$ denotes the concatenation operation, reverse $($str$)$ should return the reversed of string str$,$ and invert $($str$)$ inverts all the bits in str $(0$ changes to $1$ and $1$ changes to $0).$ For example, the first four strings in the above sequence are:

$S_1=1$

$S_2=100$

$S_3=1000110$

$S_4=100011001001110$

Return the $i^{in}$ bit in $S_n.$ Assume that $i$ is valid for the given $n.$

Example $1$:

Input: $n=3,i=1$

Output: $"1"$

Explanation: S is $"1000110".$

The $1-$bit is $"1".$

Example $2$:

Input: $n=4,i=11$

Output: $"0"$

Explanation: Sis $"100011001001110".$