LECTURE 09

Recursion and Storage

Classes

1
Contents
 Storage Classes
 Recursion
 Recursion Vs. Iteration
 Function with Empty Parameter Lists
 Inline Functions
 Reference and Reference Parameter

2
Storage Classes
 A storage class defines the scope (visibility) and
life-time of variables and/or functions within a C+
+ Program. These specifiers precede the type
that they modify. There are following storage
classes, which can be used in a C++ Program.
 auto
 register
 static
 extern
 mutable

3
Storage Classes
The auto keyword allows the compiler to automatically
infer the type of a variable based on its initializer.
 The register keyword hints to the compiler that the
variable should be stored in a CPU register for faster
access (if possible). It's mostly deprecated in modern C+
+ compilers, as they optimize variable storage
automatically.
 The static keyword gives a variable a persistent lifetime
and ensures that its value is retained across function
calls. It can be used for both local and global variables.
 The extern keyword is used to declare a variable or
function that is defined in another file or outside the
current scope. It tells the compiler that the variable
exists, but the definition is elsewhere.

4
1. #include <iostream>
2. using namespace std;
3. // Function declaration
4. void func(void);
5.
6. static int count = 10; /* Global variable */
7.
8. main() {
9. while(count--) {
10. func();
11. }
12.
13. return 0;
14. }
OUTPUT
15. // Function definition
16. void func( void ) {
17. static int i = 5; // local static variable
18. i++;
19. cout << "i is " << i ;
20. cout << " and count is " << count << endl;
21. }

5
Recursion
A recursive function is defined as a function that calls itself to
solve a smaller version of its task until a final call is made which
does not require a call to itself. Every recursive solution has two
major cases, they are:
Base Case: program is simple enough to be solved directly
without making any further calls to the same function.
Recursive Case:
1. The problem at hand is divided into simpler sub parts.
2. The function calls itself but with sub parts of the problem
obtained in the first step.
3. result is obtained by combining the solutions of simpler sub

6
parts.
Recursion
void recurse()
{
... .. ...
recurse();
... .. ...
}
int main()
{
... .. ...
recurse();
... .. ...
}

7
Recursion
 Example: factorial
n! = n * ( n – 1 ) * ( n – 2 ) * … * 1
 Recursive relationship ( n! = n * ( n – 1 )! )
5! = 5 * 4!
4! = 4 * 3!…
 Base case (1! = 0! = 1)

8
1. #include <iostream>
2. using namespace std;

3. unsigned long factorial( unsigned long ); // function prototype

4. int main()
5. {
6. // Loop 10 times. During each iteration, calculate
7. // factorial( i ) and display result.
8. for ( int i = 0; i <= 10; i++ )
9. cout<< i << "! = " << factorial( i ) << endl;
10.
11. return 0; // indicates successful termination
12. } // end main
13. // recursive definition of function factorial
14. unsigned long factorial( unsigned long number )
15. {
OUTPUT
16. // base case
0! = 1
17. if ( number <= 1 ) 1! = 1
18. return 1; 2! = 2
19. 3! = 6
20. // recursive step 4! = 24
5! = 120
21. else
6! = 720
22. return number * factorial( number - 1 );
7! = 5040
23. 8! = 40320
24. } // end function factorial 9! = 362880 9
10! = 3628800
 Example Using Recursion:
Fibonacci Series
 Fibonacci series: 0, 1, 1, 2, 3, 5, 8...
 Each number sum of two previous ones
 Example of a recursive formula:
 fib(n) = fib(n-1) + fib(n-2)
 C++ code for Fibonacci function
long fibonacci( long n )
{
if ( n == 0 || n == 1 ) // base case
return n;
else
return fibonacci( n - 1 ) +
fibonacci( n – 2 );
}

10
 Example Using Recursion:
Fibonacci Series

f( 3 )

return f( 2 ) + f( 1 )

return f( 1 ) + f( 0 ) return 1

return 1 return 0

11
1. #include <iostream>
2. using namespace std;
3. unsigned long fibonacci( unsigned long ); // function prototype
4. int main()
5. {
6. unsigned long result, number;
7. // obtain integer from user
8. cout << "Enter an integer: ";
9. cin >> number;
10. // calculate fibonacci value for number input by user
11. result = fibonacci( number );
12. // display result
13. cout << "Fibonacci(" << number << ") = " << result << endl;
14. return 0; // indicates successful termination  Enter an integer: 4
15. } // end main  Fibonacci(4) = 3
16. // recursive definition of function fibonacci  Enter OUTPUT
an integer: 5
 Fibonacci(5) = 5
17. unsigned long fibonacci( unsigned long n ) Enter an integer: 0
 Enter an integer: 6
18. { 
Fibonacci(0) = 0
Fibonacci(6) = 8
19. // base case  Enter an integer: 10
20. if ( n == 0 || n == 1 ) 
Enter an integer: 1
Fibonacci(10) = 55
Fibonacci(1) = 1
21. return n;  Enter an integer: 20
22.  Fibonacci(20) = 6765

Enter an integer: 2
23. // recursive step Enter an integer: 30

Fibonacci(2) = 1
Fibonacci(30) = 832040
24. else  Enter an integer: 35
25. return fibonacci( n - 1 ) + fibonacci( n - 2 ); 
Enter an integer: 3
Fibonacci(35) = 9227465 12
26. } 
Fibonacci(3) = 2
Advantages and Disadvantages
Recursion
 Advantages of C++ Recursion
 It makes our code shorter and cleaner.
 Recursion is required in problems concerning data
structures and advanced algorithms, such as Graph
and Tree Traversal.
 Disadvantages of C++ Recursion
 It takes a lot of stack space compared to an iterative
program.
 It uses more processor time.
 It can be more difficult to debug compared to an
equivalent iterative program.

13
Recursion vs. Iteration
 Repetition
 Iteration: explicit loop
 Recursion: repeated function calls
 Termination
 Iteration: loop condition fails
 Recursion: base case recognized
 Both can have infinite loops
 Balance between performance (iteration)
and good software engineering (recursion)

14
Empty Parameter Lists
 Empty parameter list
 Specified by writing either void or nothing at
all in parentheses
 For example:
void print();
void print(void);
Specifies that function print does not take
arguments and does not return a value

15
1. #include <iostream>
2. using namespace std;
3. void function1(); // function prototype
4. void function2( void ); // function prototype
5. int main()
6. {
7. function1(); // call function1 with no arguments
8. function2(); // call function2 with no arguments
9. return 0; // indicates successful termination
10. } // end main
11. // function1 uses an empty parameter list to specify that
12. // the function receives no arguments
13. void function1()
14. {
15. cout << "function1 takes no arguments" << endl;
16. } // end function1
OUTPUT
17. // function2 uses a void parameter list to specify that
function1 takes no arguments
18. // the function receives no arguments
function2 also takes no arguments
19. void function2( void )
20. {
21. cout << "function2 also takes no arguments" << endl;
22. } // end function2
23.

16
Inline Functions
 To eliminate the cost of calls to small functions C++ proposes a new
feature called inline function. An inline function is a function that is
expanded in line when it is invoked that is compiler replaces the
function call with the corresponding function code.
 Keyword inline before function
 Reduce function-call overhead

 Compiler can ignore inline

 Good for small, often-used functions

 Example
inline double cube( const double s )
{ return s * s * s; }
 const tells compiler that function does not modify s

17
Remember that inline keyword merely send a request not a command, to
compiler. The compiler may ignore this request if the function
definition is too long or too complicated and compile the function as
normal function.

Some of the situations where inline expansion may not work are:

1. For functions returning values , if a loop, a switch or a goto exists.

2. If function contains static variables.
3. If inline functions are recursive.
1. #include <iostream>
2. using namespace std;
3. // Definition of inline function cube. Definition of function
4. // appears before function is called, so a function prototype
5. // is not required. First line of function definition acts as
6. // the prototype.
7. inline double cube( const double side )
8. {
9. return side * side * side; // calculate cube
10.
11. } // end function cube
12. int main()
13. {
14. cout << "Enter the side length of your cube: ";
15. double sideValue;
16. cin >> sideValue;
OUTPUT
17. // calculate cube of sideValue and display result
Enter the side length of
18. cout << "Volume of cube with side " your cube: 3.5
19. << sideValue << " is " << cube( sideValue ) << endl; Volume of cube with side 3.5
20. return 0; // indicates successful termination is 42.875

21. } // end main

22.

19
1. #include <iostream>
2. using namespace std;

3. inline void displayNum(int num) {

4. cout << num << endl;
5. }

6. int main() {
7. // first function call
8. displayNum(5);

9. // second function call

10. displayNum(8);

11. // third function call

12. displayNum(666);
OUTPUT

13. return 0; 5
14. } 8
666

20
 References and Reference
Parameters
 Call by value
 Copy of data passed to function
 Changes to copy do not change original
 Prevent unwanted side effects
 Call by reference
 Function can directly access data
 Changes affect original

21
References and Reference
Parameters
 Reference parameter
 Alias for argument in function call
 Passes parameter by reference
 Use & after data type in prototype
 void myFunction( int &data )
 Read “data is a reference to an int”

 Function call format the same

 However, original can now be changed

22
1. #include <iostream>
2. using namespace std;
3. int squareByValue( int ); // function prototype
4. void squareByReference( int & ); // function prototype
5.
6. int main()
7. {
8. int x = 2;
9. int z = 4;
10.
11. // demonstrate squareByValue
12. cout << "x = " << x << " before squareByValue\n";
13. cout << "Value returned by squareByValue: "
14. << squareByValue( x ) << endl;
15. cout << "x = " << x << " after squareByValue\n" << endl;
16. // demonstrate squareByReference
17. cout << "z = " << z << " before squareByReference" << endl;
18. squareByReference( z );
19. cout << "z = " << z << " after squareByReference" << endl;
20.
21. return 0; // indicates successful termination
22. } // end main
23.

23
24. // squareByValue multiplies number by itself, stores the
25. // result in number and returns the new value of number
26. int squareByValue( int number )
27. {
28. return number *= number; // caller's argument not modified
29.
30. } // end function squareByValue
31. // squareByReference multiplies numberRef by itself and
32. // stores the result in the variable to which numberRef
33. // refers in function main
34. void squareByReference( int &numberRef )
35. {
36. numberRef *= numberRef; // caller's argument modified
37.
38. } // end function squareByReference
OUTPUT

 x = 2 before squareByValue
 Value returned by squareByValue: 4
 x = 2 after squareByValue

 z = 4 before squareByReference
 z = 16 after squareByReference

24
 References and Reference
Parameters
 References as aliases to other variables
 Refer to same variable
 Can be used within a function
int count = 1; // declare integer variable count
Int &cRef = count; // create cRef as an alias for count
++cRef; // increment count (using its alias)
 References must be initialized when
declared
 Otherwise, compiler error

25
1. #include <iostream>
2. using namespace std;

3. int main()
4. {
5. int x = 3;
6. // y refers to (is an alias for) x
7. int &y = x;
8.
9. cout << "x = " << x << endl << "y = " << y << endl;
10. y = 7;
11. cout << "x = " << x << endl << "y = " << y << endl;
12.
13. return 0; // indicates successful termination
14.
15. } // end main
OUTPUT

x = 3
y = 3
x = 7
y = 7

26
1. #include <iostream>
2. using namespace std;

3. int main()
4. {
5. int x = 3;
6. int &y; // Error: y must be initialized
7.
8. cout << "x = " << x << endl << "y = " << y << endl;
9. y = 7;
10. cout << "x = " << x << endl << "y = " << y << endl;
11.
12. return 0; // indicates successful termination
13.
14. } // end main

OUTPUT
Borland C++ command-line compiler error message:
Error E2304 Fig03_22.cpp 11: Reference variable 'y' must be
initialized­in function main()

Microsoft Visual C++ compiler error message:

D:\cpphtp4_examples\ch03\Fig03_22.cpp(11) : error C2530: 'y' : 27
references must be initialized