Concepts in Programming Languages and Functions

CS112 Level 1 Programming Languages 1 Lecture 1 Functions, Function Overloading, Recursion, and Call-by-Reference versus Call-by-Value Course & Lectures are based on their counterparts in the following courses: o Harvard University'sCS50; An introduction to the intellectual enterprises of computer science and the art of programming, Harvard School of Engineering and Applied Sciences. o UNSW'sCS1: Higher Computing, by Richard Buckland The University of New South Wales. o MIT's6.087 Practical Programming in C (2010), 6.096 Introduction to C++ (2011), and 6.S096 Introduction to C and C++ (2013), MIT (Massachusetts Institute of Technology) OpenCourseWare. 1

Functions Why Functions? Copy-Paste Coding User-Defined vs. Built-in Functions Functions Declarations Functions Declaration Syntax Functions Prototypes & Libraries Returning Values and Arguments Types Returning a Value Argument Type Matters? Function Overloading Recursion (Recursive Functions) Factorial Fibonacci Passing Arguments Call / Pass by Value Call / Pass by Reference Returning multiple values 2 O u t l i n e Outline 2

Revision Functions .. Why Functions? User-Defined vs. Built-in? Functions Declarations? Functions Prototypes? 3

Why Functions? #include <stdio.h> int main() { int threePowerFour = 1; for (int i = 0; i < 4; i = i + 1) { threePowerFour = threePowerFour * 3; } printf(" 3^4 is %d \n", threePowerFour); int sixPowerFive = 1; for (int i = 0; i < 5; i = i + 1) { sixPowerFive = sixPowerFive * 6; } printf(" 6^5 is %d \n", sixPowerFive); int twelvePowerTen = 1; for (int i = 0; i < 10; i = i + 1) { twelvePowerTen = twelvePowerTen * 12; } printf(" 12^10 is %d \n", twelvePowerTen); return 0; } Copy-Paste Coding (bad!)

Why Functions? Instead .. with a function #include <stdio.h> / * Some code which raises an arbitrary integer to an arbitrary power */ int main() { int threePowerFour = raiseToPower( 3, 4 ); printf( "3^4 is %d", threePowerFour ); int sixPowerFive = raiseToPower( 6, 5 ); printf( 6^5 is %d", sixPowerFive ); int twelvePowerTen = raiseToPower( 12, 10 ); printf( 12^10 is %d", twelvePowerTen ); return 0; }

Functions Functions are reusable sections of code that serve a particular purpose. o Functions can take inputs and outputs, and can be reused across programs. o Organizing programs into functions helps to organize and simplify code. o This is an example of abstraction; after you've written a function, you can use the function without having to worry about the details of how the function is implemented. Because of abstraction, others can use (or "call") the function without knowing its lower-level details as well. 6

All programs you've written in C already have one function: main. However, programs in C can have more functions as well. Built-in vs. User-Defined Functions xy Pow (math.h) (x, y) You've probably used plenty of C functions already like printf() from the stdio library or pow() from the math library. Hello Printf (stdio.h) ( Hello ) But we can also write our own functions and incorporate them into our code. Basically the point of functions is to help you to partition your code into manageable pieces.

Why define your own functions? Readability: sqrt(5) is clearer than copy-pasting in an algorithm to compute the square root. Maintainability: To change the algorithm, just change the function (instead of changing it everywhere you ever used it). Code reuse: Lets other people use algorithms you ve implemented.

Function Declaration Syntax Function name int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; }

Function Declaration Syntax Return Type int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; }

Function Declaration Syntax Parameter 1 int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; } Parameters order matters: raiseToPower( 2, 3 ) is 2^3 = 8 raiseToPower( 3, 2 ) is 3^2 = 9

Function Declaration Syntax Parameter 2 int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; } Parameters order matters: raiseToPower( 2, 3 ) is 2^3 = 8 raiseToPower( 3, 2 ) is 3^2 = 9

Function Declaration Syntax Signature ( function header ) int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; }

Function Declaration Syntax int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; } Body

Function Declaration Syntax int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i+ 1 ) { result = result * base; } return result; } Return Statement

#include <stdio.h> int raiseToPower( int base, int power ) { int result = 1; for ( int i = 0; i < power; i = i + 1 ) { result = result * base; } return result; } Function Declaration Function Invocation ( Function Call ) int main() { int threePowerFour = raiseToPower( 3, 4 ); printf( "3^4 is %d", threePowerFour ); int sixPowerFive = raiseToPower( 6, 5 ); printf( "6^5 is %d", sixPowerFive ); int twelvePowerTen = raiseToPower( 12, 10 ); printf( "12^10 is %d", twelvePowerTen ); return 0; }

Function Declaration Function declarations need to occur before invocations. For example: int foo() { return bar()*2; / / E R R O R ; bar hasn t been declared yet } int bar() { return 3; }

Function Declaration Function declarations need to occur before invocations. Solution 1: reorder function declarations. For example: int bar() { return 3; } int foo() { return bar()*2; / / O k }

Function Declaration Function declarations need to occur before invocations. Solution 1: reorder function declarations. Solution 2: use a function prototype; it informs the compiler that you will implement it later. For example: int bar(); int foo() { return bar()*2; / / O k } FunctionPrototype int bar() { return 3; }

Function Prototype Function signature of the method, though argument names don t matter. prototypes should match the For example: int square( int ); int square( int x ); int square( int z ); int cube( int x ) { return x*square(x); } int cube( int x ) { return x*square(x); } int cube( int x ) { return x*square(x); } int square( int x ) { return x*x; } int square( int x ) { return x*x; } int square( int x ) { return x*x; }

Function Prototype Function prototypes are generally put into separate header files. Separates specification of the function from its implementation. For example: / / myLib.h - header / / contains prototypes / / myLib.cpp - implementation #include "myLib.h" int square( int ); int cube( int ) ; int cube( int x ) { return x * square( x ); } int square( int x ) { return x * x; }

Libraries Libraries are generally distributed as the header file containing the prototypes, and a binary .dll/.so file containing the (compiled) implementation. Don t need to share your .c code. For example: // myLib.h header // contains prototypes doublesquareRoot( doublenum ); myLib.dll

Libraries Library user only needs to know the function prototypes (in the header implementation source code (in the .c file). The Linker (part of the compiler) takes care of locating the implementation of functions in the .dll file at compile time. file), not the For example: // myLib.h header // contains prototypes doublesquareRoot( doublenum ); myLib.dll // libraryUser.c some other guy s code #include "myLib.h" double fourthRoot(double num ) { returnsquareRoot( squareRoot( num ) ); }

Returning Values and Arguments Types 24

Returning a Value Up to one value may be returned; it must be the same type as the return type. For example: int foo() { return "hello"; // error } On the other hand: int foo() { return 2; // ok }

Returning a Value Up to one value may be returned; it must be the same type as the return type. If no values are returned, give the function a void return type. For example: void printNumber( int num ) { printf( "number is %d ", num ); } int main() { printNumber( 4 ); // the number is 4 return 0; }

Returning a Value Up to one value may be returned; it must be the same type as the return type. If no values are returned, give the function a void return type. Note that you cannot declare a variable of type void. For example: int main() { void x; / / E R R O R return 0; }

Returning a Value Return statements don t necessarily need to be at the end. Function returns as soon as a return statement is executed. For example: void printNumberIfEven( int num ) { if ( num % 2 == 1) { printf("Odd number"); return; } printf("Even number; the number is %d", num); } int main() { int x = 4; int y = 5; printNumberIfEven( x ); // PRINTS: Even number; number is 4 printNumberIfEven( y ); // PRINTS: Odd number }

Argument Type Matters? void printOnNewLine( int x ) { printf( "%d" , x ); } Consider the following function invocations? printOnNewLine( 3 ) printOnNewLine("hello") Will anyone of them result in an error?

Argument Type Matters? void printOnNewLine( int x ) { printf( "%d" , x ); } printOnNewLine( 3 ) works printOnNewLine("hello") will not compile

Argument Type Matters? void printOnNewLine( int x ) { printf( "%d" , x ); } void printOnNewLine( char x ) { printf( "%c" , x ); } Consider the following function invocations? printOnNewLine( 3 ) printOnNewLine('A') Will anyone of them result in an error?

Argument Type Matters? void printOnNewLine( int x ) { printf( "%d" , x ); } void printOnNewLine( char x ) { printf( "%c" , x ); } printOnNewLine( 3 ) works printOnNewLine('A') also works

Function Overloading 33

Function Overloading Many different arguments. The function called is the one whose arguments match the invocation. functions with the same name, but For example: void printOnNewLine( int x ) { printf( "Integer: %d", x ); } void printOnNewLine( char x ) { printf( "Character: %c", x ); } printOnNewLine( 3 ) prints Integer: 3 printOnNewLine('A' ) prints Character: A

Function Overloading Many different arguments. The function called is the one whose arguments match the invocation. functions with the same name, but For example: void printOnNewLine( int x ) { printf( "One Integer: %d", x ); } void printOnNewLine( int x, int y ) { printf( "Two Integers: %d,%d", x, y ); } printOnNewLine( 3 ) prints One Integer: 3 printOnNewLine( 4, 5 ) prints Two Integers: 4,5

Recursion .. ? Recursive Functions 36

Recursion Recursion is a programming concept whereby a function invokes itself. Input Output Recursion is typically used to solve problems that are decomposable into sub-problems that are just like the original problem, but a step closer to being solved.

Recursion without a Base Case Here s a recursive function called foo. What happens when this function is called? void foo( string str ) { printf( %s\n , str ); foo( str ); } foo will print a string and call itself, which will print another string and call itself again, which will print another string and call itself yet again .. and on and on infinitely. However, every time a function is called, some space is set aside in the stack called a frame and every function call results in a new frame being created.

Recursion without a Base Case So, if foo calls itself infinitely, we ll eventually run out of stack memory and try to access memory void foo( string str ) { printf( %s\n , str ); foo( str ); } that doesn t belong to us, in which case our program will fail with a segmentation fault. To avoid this situation, we need to make sure there s always a way to break out of recursive calls -- we ll call this the base case. When the base condition is met, the function should return without making a recursive call. Let s make sure we have a base case in the next example :)

Factorial For our next example, let s think about the factorial operation. The factorial operation is a perfect candidate for recursion because it is a problem that can easily be broken up into similar smaller problems! n! = n * (n - 1) * (n - 2) * * 1 5! = 5 * 4 * 3 * 2 * 1 So if we want to calculate the factorial of 5, we can think of it as multiplying 5 by the factorial of 4: 5! = 5 * 4! Similarly, to calculate the factorial of 4, we multiply 4 by the factorial of 3: 4! = 4 * 3! And so on .. Let s implement a factorial function in C!

This recursive function calculates the factorial of its integer argument, and unlike the last function we saw, this one has a base case! Think through what happens when you pass this function an argument of 3: unsigned int factorial(unsigned int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } factorial(3) returns 3 * factorial(2) factorial(2) returns 2 * factorial(1) factorial(1) is the base case and returns 1

Once the base case is reached, all of the factorial() calls will return in succession to give us an answer of 6. factorial(3) = 3 * factorial(2) 2 * factorial(1) 1 Let s see what s going on in the stack as this recursive function executes!

Lets zoom in on the stack as this function executes: main() calls factorial(3) heap factorial ( 3 ) main ( ) stack Every function call results in a new frame being created. These frames are arranged on top of each other in the stack, with the frame for the most recently called function (the active frame) at the top.

main() calls factorial(3) factorial(3) calls factorial(2) heap factorial ( 2 ) factorial ( 3 ) main ( ) stack factorial(2) is now the active frame.

main() calls factorial(3) factorial(3) calls factorial(2) factorial(2) calls factorial(1) heap factorial ( 1 ) factorial ( 2 ) factorial ( 3 ) main ( ) stack factorial(1) is now the active frame.

main() calls factorial(3) factorial(3) calls factorial(2) factorial(2) calls factorial(1) heap factorial(1) returns 1 to factorial(2). Its frame is destroyed, and the one for the function below (in this case factorial(2)) becomes active again. 1 factorial ( 2 ) factorial ( 3 ) main ( ) stack factorial(1) returns 1 to factorial(2)

main() calls factorial(3) factorial(3) calls factorial(2) factorial(2) calls factorial(1) heap factorial(2) returns 2 to factorial(2). Its frame is destroyed, and the one for the function below (in this case factorial(3)) becomes active again. 2 factorial ( 3 ) main ( ) stack factorial(1) returns 1 to factorial(2) factorial(2) multiplies 1 * 2 and returns 2 to factorial(3)

main() calls factorial(3) factorial(3) calls factorial(2) factorial(2) calls factorial(1) heap factorial(3) returns 6 to main(). Its frame is destroyed, and the one for the function below (in this case main()) becomes active again. Nice! Our function calculated the correct answer! 3! = 3 * 2 * 1 = 6 6 main ( ) stack factorial(1) returns 1 to factorial(2) factorial(2) multiplies 1 * 2 and returns 2 to factorial(3) factorial(3) multiplies 2 * 3 and returns 6 to main()

Fibonacci fib( n ) = fib( n - 1 ) + fib( n - 2 ) .. .. can be easily expressed via a recursive implementation. How?

Fibonacci fib( n ) = fib( n - 1 ) + fib( n - 2 ) .. .. can be easily expressed via a recursive implementation. int fibonacci( int n ) { i f (n == 0 || n == 1) { return n; } else { return fibonacci( n 2 ) + fibonacci( n 1 ); } }