Compution using recursive method

Problem:

The number n! is defined as n × ( n – 1 ) × ( n – 2 ) × … × 2 × 1 .

(a) Can you write up a recursive method to calculate the value of n! ?

(b) You are given a function called print( n ) which shows the value of n on the screen. Using your idea in (a) above, can you write up a recursive method to print numbers from n to 0 on the screen?

Follow-up:

(a) The number n! is defined as n × ( n – 1 ) × ( n – 2 ) × … × 2 × 1 .
We can express its computation as a recursive method below. Assume n > 1 .

Calculate_Factorial(n)

1. Is n = 1?
2. If yes, then answer is: 1
3. If no, then answer is: n x Calculate_Factorial(n-1)

(b) Using an idea similar to the above, we can solve the “printing” problem as follows. Assume n>0 .

Show_n_downto_0(n)

1. print(n)
2. Is n = 0?
3. If yes, then we are done
4. If no, then do: Show_n_downto_0(n-1)

Problem:

We observe that . Assume n is a power of 2.

Can you write up a recursive method to calculate the value?

Follow-up:

We can express this computation as a recursive method below.

Calculate_Power(a, n)

1. Is n = 1?
2. If yes, then answer is: a
3. If no, then:
4.        b = Calculate_Power(a, n/2)
5.        answer is then: b x b