More on Recursion
-
Two frogs are sitting at bottom of a flight of $10$ steps and debating in how many ways can they jump up the stairs. They can jump one, two or three steps at a time. For example they can cover the 10 steps by jumping $(3, 3, 3 , 1)$ or $(2 ,3, 3, 2)$ or other suitable combinations. Their mathematics is not very strong (being frogs) and they approach you for help. Develop an efficient Python function that provides a general solution (not only for $10$ but for general $n$ steps). Note that $(3,3,3,1)$ is distinct from $(1,3,3,3)$ and likewise and that we only want to count the number of solutions and not report the solutions. Perform the timing analysis of your solution.
-
Write a Python program to count the number of ways for a rook to move from the southwest corner of a $p \times q$ chessboard to the northeast corner by moving one square at a time eastward or northward only. Note that rook is a chess piece that can move horizontally and vertically on a chess board. Give a recursive formulation and do not use a formula.
-
Develop a higher order function and show its use in computing fastpower (from Assign1), perfect numbers, $e^{x}$ up to some $n$-th term, and the higher order double summation function to compute $\Sigma_{i = a}^{b}\Sigma_{j=c}^{d}$. Provide proof of correctness and timing analysis.
-
Define a higher order composition function
compose(f, g,x)in Python and use it to implement a functionrepeat(f,n)to compute $f^n(x)$.