Page 128 - Open Soource Technologies 304.indd

Unit 7: Functions

“Classic” recursion is a divide-and-conquer method. For example, consider merge sorting. Notes
The idea behind merge sorting is to divide an array into two halves, and sort each half. Then,
you “merge” the two sorted halves to sort the entire list.
Thus, to solve the big problem of sorting an array, solve the smaller problem of sorting
part of an array, and use the solution of the smaller sorted array to solve the big problem
(by merging).
How do you solve the smaller version of the problem? You break that smaller problem into
even smaller problems, and solve those.
Eventually, you get to the smallest sized problem, which is called the base case. This can be
solved without using recursion.
Recursion allows you to express solutions to a problem very compactly and elegantly. This
is why people like using recursion.
However, recursion can use a lot of stack, and if you’re not careful, you can overflow the stack.
For recursion to be successful, the problem needs to have a recursive substructure. This is a
fancy term that says that to solve a big problem (say of size N), you should be able to solve a
smaller problem (of smaller size) in exactly the same way, except the problem size is smaller.

As an analogy, you might have to, say, sweep the floor. Sweeping half the floor is the same
as sweeping the entire floor, except you do it on a smaller area. A problem that is solved
recursively is generally needs to have this property.

7.12 Self Assessment Questions

1. ______________ in PHP is a collection of key/value pairs.
2. ______________ is like C++ are supported by PHP.

3. Array elements can be accessed by using the $arr[key] notation.
(a) True (b) False
4. Arrays in PHP are implemented using hash tables.

(a) True (b) False
5. PHP also allows you to return variables ______________ .
6. Array elements can be accessed by using the ______________ .

(a) $arr[key] notation (b) Z. arr[key] notation
(c) P arr[key] notation (d) all of the above.

7.13 Review Questions

1. Define the Function scope.

2. What are user defined functions?
3. What is function scope?
4. Define the returning value.

5. What is default parameters?
6. Define static variables.

LOVELY PROFESSIONAL UNIVERSITY 123