Question

1 Problem Description

If someone asks us what the set of natural numbers is, she/he is interested in the definition of the set of natural numbers. We usually would write 0, 1, 2, 3, . . . as our answer. Since the set is infinite, we cannot write it out completely, even though each natural number is finite. Notice that . . . after 3 is for humans to understand because we (human beings) are intelligent. However, we cannot use it to define things for a machine such as a computer or in a computer program. Another example would be to define the factorial of a positive natural number. We would let n be a positive natural number and let n! the factorial of n. We could write n! = n × (n − 1) × . . . × 2 × 1. Again, we use . . . in our definition.

How could we define things without using . . .? One of the answers is to use a recursive (or inductive) definition. This allows machines, as well as human beings, to follow the definition. The programs that we write in this lab will follow the definitions exactly.

2 Purpose

Learning recursive definitions (inductive definitions) and programming using recursion.

3 Design

Let us look at a few examples of recursive definitions.

Example One: Defining a natural number

• Basis: 0 is a natural number.
• Recursion (induction): X is a natural number provided X −1 is a natural number.

Note that we used a natural number to define a natural number, which is recursive and may seem to be circular. However, it is well defined (not circular) because X − 1 is smaller and we have the basis where 0 is a natural number. The definition assumes we understand subtraction or −. From the definition, we know that 0 is a natural number (from the basis), 1 is a natural number (1 − 1 is 0, using the recursion once and the basis), 2 is a natural number (2 − 1 is 1, using recursion and the previous statement), and so on. Here is the idea!

Example Two: Defining the factorial of a positive natural number

• Basis: n! = 1, when n = 1
• Recursion (induction): n! = n × (n − 1)!, when n > 1.

Note again that we used (n − 1)! factorial to define n! factorial, which is recursive. However, it is well defined because n − 1 is smaller than n and we have the basis where 1! is 1. The definition assumes we understand multiplication or ×. From the definition, we know that 1! is 1 (from the basis), 2! is 2 (2 × 1!), 3! is 6 (3 × 2!), and 4! is 24 (4 × 3!), and so on.

If someone writes the following:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . It would be harder for us to know what is the number after 144, right? This is the sequence of Fibonacci numbers F0, F1, F2, . . .

Example Three: Defining Fn, the nth Fibonacci number

• Bases: F₀ = 1, F₁ = 1
• Recursion (induction): F_n = F_n−1 + F_n−2, when n > 1.

Note again that we used two smaller Fibonacci numbers (F_n−1, F_n−2) to define a larger Fibonacci number(F_n), which is recursive. However, it is well defined because n − 1, n − 2 are smaller than n and we have the bases where F₀ = 1, and F₁ = 1. The definition assumes we understand addition or +.

A sequence of n integers, a₁, a₂, . . . , a_n is in a nondecreasing order if a₁≤ a₂ ≤ . . . ≤ a_n. Again, we use the . . . in defining nondecreasing order. The following is a recursive definition.

Example Four: Defining a1, a2, . . . , an is in a nondecreasing order

• Basis: a_n is in nondecreasing order, n = 1
• Recursion (induction): a₁, a₂, . . . , a_n is in nondecreasing order provided that a₁ is a smallest element among a₁, a₂, . . . , a_n and a₂, . . . , a_n is in nondecreasing order, when n > 1.

We could follow the above definition to rearrange a sequence of integers (or an array of int) into nondecreasing order. We simply find a smallest value and put it in the first place, recursively rearrange the remaining integers in the same way. Rearranging is what we call sorting.

Write three recursive functions to compute n!, F_n, and sorting; and one function to output sorted values in one line.

int factorial(int n);
int fibonacci(int n);

void sort (int * seq, int size);

void display(int * seq, int size);

4 Implementation

Factorial function:

1. If n is 1, return 1.
2. Return n times factorial(n-1). This is a recursive call (the factorial function calls itself). If we forget to test n is 1 above, we get an infinite loop! Can you see that? If you do not believe us, try it for yourself.

Fibonacci number:

1. If n is 0, return 1.
2. If n is 1, return 1.
3. Otherwise, return the sum of fibonacci(n-1) and fibonacci(n-2). This step involves two recursive calls. The fibonacci function calls itself twice. If we forget to test if n is 0 or if n is 1 above, we will again get an infinite loop!

Sorting:

Note seq is an array of integers (int) and n tells us the number of elements in the array.

1. If size is 1, return.
2. Find the smallest value in the array and put it in seq[0]
3. Recursively call sort(seq+1,n-1). Note seq+1 is pointer arithmetic, so in effect, we pass the array without the first element. Think about it! This tests your true understanding of parameter passing.

Display:

Note seq is an array of integers (int) and n tells us the number of elements in the array.

1. Write a loop to go through each element in seq and output all the numbers on a single line. Numbers should be separated by a comma, and there should be no space between numbers.

You may implement the display function using recursion if you want, but it is not required for this lab. Note that solving the three main problems, factorial, fibonacci, and sorting involves the concept of looping. However, in the hints provided in the recursive implementation no loop is involved! In general, there is a strong connection between looping and recursion. Please also note how the implementation follows the corresponding recursive definition.

5 Test and evaluation

Testing should have been done in the main program that calls these functions and during the implementation. You are STRONGLY recommended to trace the execution of recursive functions to understand recursion, say observe the order of calls and the parameter values. Output (cout) the values as in debugging and see if the values are what you expect. Your main program should call each function in order to demonstrate that those functions work as expected.

Answer 1

#include <iostream>
using namespace std;

int factorial(int n);
int fibonacci(int n);
void sort (int * seq, int size);
void display(int * seq, int size);
int main()
{
int n;
int ar[10];

cout << "Enter a Number eg=5";
cin >> n;

cout << "factorial of " << n << " = " << factorial(n)<<endl;
cout << "fibonacci of " << n << " = " << fibonacci(n)<<endl;
  
cout << "Enter element for array"<<endl;
//get element for array
for(int i=0;i<n;i++)
cin>>ar[i];
//call sort method to sort array element using recursive approach
sort(ar,n);
// call display method to show sorted data of array
display(ar,n);
return 0;
}

int factorial(int n) {
if (n>=1)
return n*factorial(n-1);
else
return 1;
}

int fibonacci(int n)
{
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

void sort (int * seq, int size)
{
if (size == 1)
return;
for (int i=0; i<size-1; i++)
if (seq[i] > seq[i+1])
{
int tmp = seq[i];
seq[i] = seq[i+1];
seq[i+1]= tmp;
}
sort(seq, size-1);
}

void display(int * seq, int size)
{
for (int i=0; i < size; i++)
cout<<seq[i]<<",";
}