Question

Devise a recursive algorithm that counts the number of times the integer 0 occurs in a list of integers.

Exercises 70–77 deal with some unusual sequences, informally called

self-generating sequences, produced by simple recurrence relations or rules. In particular, Exercises 70–75 deal with the sequence\(\left\{ {{\bf{a}}\left( {\bf{n}} \right)} \right\}\)defined by\({\bf{a}}\left( {\bf{n}} \right){\bf{ = n - a}}\left( {{\bf{a}}\left( {{\bf{n - 1}}} \right)} \right)\)for\({\bf{n}} \ge {\bf{1}}\)and\({\bf{a}}\left( {\bf{0}} \right){\bf{ = 0}}\).(This sequence, as well as those in Exercises 74 and 75, are defined in Douglas Hofstader’s fascinating book Gödel, Escher, Bach ((Ho99)).

\(\)

Short answer

Recursive algorithm has been found.

Step-by-step solution

Introduction

A recursive function is a function that its value at any point can be calculated from the values of the function at some previous points. For example, suppose a function\({\bf{f}}\left( {\bf{k}} \right){\bf{ = f}}\left( {{\bf{k - 2}}} \right){\bf{ + f}}\left( {{\bf{k - 3}}} \right)\)which is defined over non negative integer.

Step 2: Devise a recursive algorithm

Recurrence for number of multiplication used in algorithm:

\(T\left( 1 \right) = 0\), since the number of multiplications (base case)

Let\(T\left( n \right)\)be the number of multiplications that the function power\(\left( {b,n} \right)\)uses to compute\({b^n}\).

A recursive algorithm that counts the number of times the integer 0 occurs in q list of integers:

Procedure zero count

\(\left( {{x_1},{x_2},.............{x_n}:{\rm{ list of integers}}} \right)\)

If\(n = 1\)then

If\({x_1} = 0\)then zero count\(\left( {{x_1},{x_2},.............{x_n}} \right): = 1\)

Else zero count\(\left( {{x_1},{x_2},.............{x_n}} \right): = 0\)

Else

If\({x_n} = 0\)then zero count

\(\left( {{x_1},{x_2},.............{x_n}} \right): = {\rm{ zero count + }}\left( {{x_1},{x_2},.............{x_{n + 1}}} \right) + 1\)

Else zero count

\({\rm{zero count}}\left( {{x_1},{x_2},.............{x_n}} \right): = {\rm{zero count }}\left( {{x_1},{x_2},.............{x_{n - 1}}} \right)\)

Hence, recursive algorithm has been found.[a1] [a2]

[a1]

[a2]Explain what each part of the program does

Then, again give the complete program at the end