12.9 Functions

intro-to-computer-science-gtiit-09-2024.pdf

The Big Picture

Problem decomposition: Breaking a problem into small, manageable pieces is crucial for writing large programs.
Imperative programming languages typically provide subroutines (in C, functions) to break programs into smaller functional components.
A program will now consist of one or more functions, one of them being main().
Program execution begins with main().
main() can invoke other functions, including library functions like printf() and rand().
Functions use program variables, whose access is determined by scope rules.

Function Definition

General Form:

type function_name(parameter list) { 
    declarations 
    statements 
}

Everything before the first brace is the header of the function.
Everything between the braces is the body of the function definition.
The parameter list is a comma-separated list of declarations.

Example:

int factorial(int n) { 
    int product = 1; 
    for (int i = 2; i <= n; i++) { 
        product = product * i; 
    } 
    return product; 
}

Detailed Description of the Example

A definition alone does not execute anything. The function needs to be called for something to happen.
Evaluating expression factorial(7) causes a call.
The effect is to execute the code in the function definition, with n having the value 7.

Explanation:

The value returned by the function has type int.
The parameter list includes the declaration int n. The function has a single parameter of type int.

Function Definition/Call Example

Example:

void wrt_address(void) {
    printf("%s\n%s\n%s\n%s\n", 
           "** SANTA CLAUS **", 
           "** NORTH POLE **", 
           "** EARTH **");
}

It does not return any value.
It does not have any parameters.

Function Call:

int main() {
    for (int i = 0; i < 3; i++) {
        wrt_address();
    }
    return 0;
}

Evaluating the expression wrt_address() calls the function.

Function Parameters and Local Variables

In the definition, the name of the function is followed by a parenthesized list of parameter declarations.
Parameters act as placeholders for values passed when the function is called.
Sometimes, these parameters are referred to as formal parameters to emphasize their placeholder role.
The function body is a block that may contain local variables.

Example 1:

int twice(int x) {
    return (2 * x);
}

Example 2:

int add(int a, int b, int c) {
    int sum = a + b + c;
    return sum;
}

One Job, One Function

Designing programs as collections of functions is essential for dealing with complexity.
Advantages:
Easier to reason about single functions and their behavior.
Simplifies writing and debugging.
Easier to maintain or modify modularized programs.
Enables rewriting only the affected functions without impacting the rest of the program.
Functions should be:
Clear, readable, and self-documenting.
Principles:
Each function should have a single responsibility.
Function names should reflect their behavior.

The Return Statement

The return statement may or may not include an expression.
The expression being returned can be enclosed in parentheses, but this is not required.
When a return statement is encountered:
Execution of the function is terminated.
Control is passed back to the calling environment.
If the return statement contains an expression, the value of the expression is passed back to the calling environment.

Examples:

return;
return ++a;
return (a * b);

Return Statements and Returned Values

Functions can have zero or more return statements.
If there is no return statement, control comes back to the calling environment at the end of the function body.
Even if a function returns a value, a program does not need to use it.

Examples:

getchar();       // Get a char and do nothing with it.
c = getchar();   // Get a char and assign it to c.

Function Prototypes

Like variables, C requires functions to be declared before they are used.
The syntax to declare a function is called a function prototype.
A prototype specifies:
The number and type of arguments passed to the function.
The type of value returned by the function.

Example:

char toUpper(char);

This declares that toUpper is a function that takes a single argument of type char and returns a char.

Example of Top-Down Design: Creating a Table of Powers

Code:

#include<stdio.h>

#define N 7

long power(int, int);
void prn_heading(void);
void prn_tbl_of_powers(int);

int main(void) {
    prn_heading();
    prn_tbl_of_powers(N);
    return 0;
}

void prn_heading(void) {
    printf("::::: A TABLE OF POWERS :::::\n\n");
}

void prn_tbl_of_powers(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j == 1) {
                printf("%3d", power(i, j));
            } else {
                printf("%6d", power(i, j));
            }
        }
        putchar('\n');
    }
}

long power(int m, int n) {
    int product = 1;
    for (int i = 1; i <= n; i++) {
        product = product * m;
    }
    return product;
}

Output:

::::: A TABLE OF POWERS :::::

  1     1     1     1     1     1     1
  2     4     8    16    32    64   128
  3     9    27    81   243   729  2187
  ...

Alternative Style

Alternative Style: Remove the prototypes and place function definitions before the calls.
Function definitions serve as their own prototypes.
This style positions main() at the end of the program.

Example:

long power(int m, int n) {
    // Implementation
}

void prn_tbl_of_powers(int n) {
    // Implementation
}

int main(void) {
    prn_heading();
    prn_tbl_of_powers(N);
    return 0;
}

Call-by-Value

How it works:
Functions are invoked by passing arguments in parentheses.
Arguments must match the number and type of the parameters in the function definition.
By Value: The value of the variable is passed, not the variable itself.
Implications:
Changes to the parameter inside the function do not affect the original variable.
Variables are safe from unintentional modifications.

Example

int compute_sum(int n);

int main(void) {
    int n = 3, sum;

    printf("%d\n", n);
    sum = compute_sum(n);
    printf("%d\n", n);
    printf("%d\n", sum);
    return 0;
}

int compute_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum = sum + n;
        --n;
    }
    return sum;
}

Function Call Summary

Each expression in the parameter list is evaluated.
Each value is assigned to its corresponding formal parameter at the beginning of the body of the function.
The body of the function is executed.
If a return statement is reached, it is executed, and control is passed back to the calling environment.
If the return statement includes an expression, it is evaluated, and that value is passed back to the calling environment.
If no return statement is reached, control is passed back to the calling environment when the end of the body of the function is reached.

Summary

Functions help structure C programs. They help break down a problem into smaller subproblems, each solved by a corresponding function.
A return statement ends the execution of a function and passes control back to the calling environment. If the return statement contains an expression, its value is passed back to the calling environment.
A function prototype tells the compiler the type and number of its parameters and the type of its returned value. If there are no parameters, the word void is used; if the function returns no value, void is also used as the return type.
Arguments to functions are passed by value in C. They must be type compatible with the corresponding types specified in the function prototype or definition.

Recursion

A recursive definition defines a concept in terms of itself.

Recursion in Algorithms:

A natural approach to solving many computational problems.
A recursive algorithm uses itself to solve one or more smaller, identical problems.

Recursion in Programming Languages:

Recursive functions implement recursive algorithms.
A recursive function includes a call to itself.

The Structure of a Recursive Definition

A recursive definition must include:

Base Cases:
- Simple cases that do not define the concept in terms of itself.
Recursive Cases:
- Cases defined in terms of simpler instances of the same concept.
Every recursive case must eventually reach a base case.

Components of a Recursive Algorithm

Decomposition:
- What is a smaller, identical problem?
Composition:
- How are the answers to smaller problems combined to solve the larger problem?
Base/Stopping Case:
- What is the smallest problem that can be solved easily without further decomposition?

An Example: Factorial Numbers

A classical example of a recursive definition in mathematics is the definition of factorial numbers:

Base Case:
The factorial of 1 is:
\(1! = 1\)
Recursive Case:
The factorial of a number \(n\) greater than 1 is \(n \times \text{factorial}(n - 1)\):
\(n! = n \times (n - 1)!\), provided \(n > 1\).

Factorial Function

Recursive Implementation:

int factorial(int n) {
    if (n < 0) 
        return -1;  // Error for negative input
    else {
        if (n == 1) 
            return 1;  // Base case
        else 
            return n * factorial(n - 1);  // Recursive case
    }
}

Execution Steps:

Start with a call, e.g., factorial(3).
Recursive calls:
- factorial(3) calls factorial(2).
- factorial(2) calls factorial(1).
Base case reached:
- factorial(1) returns 1.
Unwind and compute:
- factorial(2) returns \(2 \times 1 = 2\).
- factorial(3) returns \(3 \times 2 = 6\).

Visual Representation of Execution

Initial Call:
factorial(3) -> Computes \(3 \times \text{factorial}(2)\).
Next Call:
factorial(2) -> Computes \(2 \times \text{factorial}(1)\).
Base Case:
factorial(1) -> Returns \(1\).
Return Values:
- factorial(2) returns \(2\).
- factorial(3) returns \(6\).

Result printed:
The factorial of 3 is: 6.

Fibonacci Numbers

The numbers in the Fibonacci sequence can also be recursively defined.

Definition:

The \(n\)-th Fibonacci number is:
\(n\), if \(n \leq 1\)
The sum of the two previous Fibonacci numbers, if \(n > 1\):
\(\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)\)

Fibonacci Function

Recursive Implementation:

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

Explanation:

Base cases:
If \(n \leq 2\), return \(n - 1\).
Recursive case:
Return the sum of the Fibonacci numbers for \(n-1\) and \(n-2\).

Crucial Aspects of a Recursive Function

Case-Based Definitions:
Use if-else statements (or other branching structures).
Recursive Cases:
Perform recursive calls with "smaller" arguments or solve smaller versions of the same task (decomposition).
Combine results (composition) if necessary.
Base Cases:
Branches with no recursive calls, also known as stopping cases or base cases.

Template

... rec_func(...) {
    if ( ... )  // Base Case
    {
        ...
    } 
    else  // Decomposition & Composition
    {
        ...
    }
    return ... ;  // If not void method
}

Is This Correct?

public static int factorial(int n) {
    return factorial(n - 1) * n;
}

Analysis:

The code is not correct because it lacks a base case. Without a base case, the recursion would continue indefinitely, causing a stack overflow error.

Correction:

public static int factorial(int n) {
    if (n <= 1)  // Base Case
        return 1;
    else
        return factorial(n - 1) * n;  // Recursive Case
}

Infinite Recursion

Infinite Recursion
Incorrectly defined recursive solution
- No decomposition (recursive calls are not on smaller problem instances)
- Base cases may exist, and not be reachable
- (Insufficient base cases, incorrectly defined decomposition)
- No base case
- Stack: keeps track of function calls
- Method begins: add function local data onto the stack
- Method ends: remove function local data from the stack
- Recursion never stops; stack eventually runs out of space
- Stack overflow error

Number of Zeros in a Positive Number

Example: \(2030\) has 2 zeros
If \(n\) is smaller than 10, it has no digits
If \(n\) is greater than 10 (i.e., it has two or more digits)
The number of zeros is the number of zeros in \(n\) with the last digit removed
Plus an additional 1 if the last digit is zero
Examples:
Number of zeros in \(2030\) is the number of zeros in \(203\) plus \(1\)
Number of zeros in \(20031\) is the number of zeros in \(2003\) plus \(0\)

`zero_count` Function

int zero_count(int n) {
    if (n < 10) {
        return 0;
    } else {
        int prefix_count = zero_count(n / 10);
        if (n % 10 == 0) {
            return prefix_count + 1;
        } else {
            return prefix_count;
        }
    }
}

Summary

Recursive function: A function that calls itself.
Very powerful algorithm design technique.

Recursive Algorithm Design:

Decomposition: Break the problem into smaller, identical problems.
Composition: Combine results of smaller problems.
Base case(s) : Smallest problem, no recursive calls.

Implementation:

Use conditional statements (e.g., if-then-else) to separate different cases.
Avoid infinite recursion by ensuring:
Recursive calls work on smaller problem instances (decomposition).
Base cases exist and are reachable from all valid function calls.

‍

12.9 Functions

The Big Picture

Function Definition

General Form:

Example:

Detailed Description of the Example

Explanation:

Function Definition/Call Example

Example:

Function Call:

Function Parameters and Local Variables

Example 1:

Example 2:

One Job, One Function

The Return Statement

Examples:

Return Statements and Returned Values

Examples:

Function Prototypes

Example:

Example of Top-Down Design: Creating a Table of Powers

Code:

Output:

Alternative Style

Example:

Call-by-Value

Example

Function Call Summary

Summary

Recursion

Recursion in Algorithms:

Recursion in Programming Languages:

The Structure of a Recursive Definition

Components of a Recursive Algorithm

An Example: Factorial Numbers

Factorial Function

Recursive Implementation:

Execution Steps:

Visual Representation of Execution

Fibonacci Numbers

Definition:

Fibonacci Function

Recursive Implementation:

Explanation:

Crucial Aspects of a Recursive Function

Template

Is This Correct?

Analysis:

Correction:

Infinite Recursion

Number of Zeros in a Positive Number

zero_count​ Function

Summary

Recursive Algorithm Design:

Implementation:

`zero_count` Function