INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56 (992 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB #05 TOPIC: Recursion

Instructor: Bashir M. Ghandi

Objective: Understand how to declare and use recursive functions

Appreciate the inefficiency of recursive functions.

What is recursion?

· So far, we have seen that a C program consists of the function main() and a zero or more other functions.

· That each of the other functions can be called by main() or by other functions.

· In addition, C also allows a function to call itself. Such a function is called a recursive function.

· Recursion is essentially another way of performing iteration.

· It is a very powerful tool for simplifying algorithms and coding of functions that involve repetitions

· It generally involves using the divide and conquer approach to problem solving.

· In this approach, a large problem is solved by breaking it into two or more sub-problems and solving the sub-problems. The sub-problems are solved by further sub-dividing them into more simpler problems. This sub-division continue until the simples form of the problem is obtained, the solution to which is obvious.

Examples of recursive functions.

· Recursive functions generally consists of two parts:

• Base Case: Which provides a solution to the simplest form of a problem.
• Recursive Case: Which solves a general form of the problem in terms of the next simpler version of the problem.

Example 1:

· The function sum above can be computed as follows:

Iterative Solution	Recursive Solution
int sumton(int n) { int i, sum=0; for (i=1; i<=n; i++) sum+=i*i; return sum; }	int sumton(int n) { if (n ==1) return 1; else return (n*n+sumton(n-1)); }

Example2: Fibonacci Sequence:

This is defined recursively as:

f₀ = 0, f₁ = 1 f_i+1 = f_i + f_i-1 for i=1,2, ..

i.e. except for f₀ and f₁, every element is the sum of its previous two elements:

0, 1, 1, 3, 5, . . .

· The following functions implements computes the nth Fibonacci number.

Iterative Solution	Recursive Solution
int fibonacci (int n) { int i,sum1=0, sum2=1, sum; if (n<=1) return n; else { for (i=2; i<=n; i++) { sum=sum1+sum2; sum1=sum2; sum2=sum; } return sum; } }	int fibonacci(int n) { if (n<=1) return n; else return (fibonacci(n-1) + fibonacci(n-2)); }

Programming Exercise:

1. Write a recursive function power that takes a float variable x, and an integer variable n, and returns the value of xⁿ . Write a main program to test the function.

2. The greatest common divisor, GCD, of two numbers can be defined as follows:

GCD(x,y) is y if x is divisible by y, otherwise, is the GCD of y and the result of dividing x by y. Write a recursive function, GCD that computes the GCD of two integer numbers. Write a main program to test the function.

3. A small ball is dropped from a height of h centimeters. Given that each time the ball bounces it reaches 0.75 of its previous height. Write a recursive function, bounce, which count the number of bounces before the height of the ball is less than 0.1 centimeter. Write a main program to test the function.

4. A palindrome is a string that reads the same forward or backward. Write a recursive function ispalindrome, that returns true if a string is a palindrome and false otherwise. Write a main program to test the function.

Exercises:

1. Write a recursive function for calculating the Hermite polynomial Hn(X), for a value x of type double and a non-negative integer n, given that:

H₀(x)=1.0

H₁(x)=2x

H_n(x) = 2xH_n-1(x) – 2(n-1)H_n-2(x) for n>1

Write a main program to test your function by computing the value of H₂(2.0)

2. An employee earns an annual salary of SR10,000.00 If he is given an increment of 10% (of the previous year) each year, write a recursive function that computes the number of years he must work before his annual salary is over SR30,000.00 Write a main program to test the function.