Week 9 Worksheet

Note: Try to solve these questions on your own.

Exercise 1: Palindrome Check

Write a recursive function named isPalindrome(), which receives a string and checks if a given string is a palindrome (reads the same forwards and backwards).

The function should take the string and relevant indices (start and end) as arguments and return 1 (true) or 0 (false).

In main(), you need to input a word from the user and pass it to the function, then display “Yes” if it is a palindrome and “No” otherwise.

Example:

Enter a word: racecar
Result: The word is a Palindrome

Example 2:

Enter a word: hello
Result: The word is not a Palindrome

Solution

#include <stdio.h>

int isPalindrome(char str[], int start, int end) {
    if (start >= end) {
        return 1;
    }
    if (str[start] != str[end]) {
        return 0;
    }
    return isPalindrome(str, start + 1, end - 1);
}

int main() {
    char word[100];
    printf("Enter the word: ");
    scanf("%s", word);
    
    int length, i = 0;
    while (word[i] != '\0') {
        i++;
    }
    length = i;
    
    // Updated output to match worksheet example
    if (isPalindrome(word, 0, length - 1)) {
        printf("Result: Yes\n");
    } else {
        printf("Result: No\n");
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int isPalindrome(const string& str, int start, int end) {
    if (start >= end) return 1;
    if (str[start] != str[end]) return 0;
    return isPalindrome(str, start + 1, end - 1);
}

int main() {
    string word;
    cout << "Enter the word: ";
    cin >> word;

    if (isPalindrome(word, 0, word.length() - 1)) {
        cout << "Result: Yes\n";
    } else {
        cout << "Result: No\n";
    }
    return 0;
}

Exercise 2: Sum of Digits

Write a recursive function named sumDigits(), that receives an integer num argument and recursively calculates the sum of its digits.

In main(), you need to ask the user for a non-negative integer, pass it to the function, and print the result.

Example:

Enter a number: 1234
Sum of digits: 10

(Calculation: \(1+2+3+4 = 10\))

Solution

#include <stdio.h>

int sumDigits(int n) {
    if (n == 0) {
        return 0;
    }
    return (n % 10) + sumDigits(n / 10);
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    printf("Sum of digits: %d\n", sumDigits(num));
    return 0;
}

#include <iostream>
using namespace std;

int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    cout << "Sum of digits: " << sumDigits(num) << "\n";
    return 0;
}

Exercise 3: Lake Volume Simulator

Assume we have a lake that changes in volume according to the daily weather conditions:

Sunny (35% probability): Loses 2% of volume.
Rainy (30% probability): Increases by 1% of volume.
Cloudy (35% probability): Volume stays the same.

Write a recursive function computeVolume(float V, int N) that takes the current volume V and number of days N, and returns the resulting volume after simulating N days.

In main(), input the initial volume and number of days from the user.

Example:

Enter initial volume: 1000
Enter number of days: 3
Day 1: Sunny (Vol: 980.00)
Day 2: Cloudy (Vol: 980.00)
Day 3: Rainy (Vol: 989.80)
Final Volume: 989.80

Note: Since weather is random, your output will vary.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

float computeVolume(float V, int N) {
    if (N == 0) {
        return V;
    }

    float prevVol = computeVolume(V, N - 1);

    int prob = rand() % 100;
    float currentVol = prevVol;

    if (prob < 30) {
        currentVol = prevVol * 1.01;
        printf("Day %d: Rainy (Vol: %.2f)\n", N, currentVol);
    } else if (prob < 65) {
        currentVol = prevVol * 0.98;
        printf("Day %d: Sunny (Vol: %.2f)\n", N, currentVol);
    } else {
        printf("Day %d: Cloudy (Vol: %.2f)\n", N, currentVol);
    }

    return currentVol;
}

int main() {
    srand(time(0));
    float startVolume;
    int days;

    printf("Enter initial volume and number of days: ");
    scanf("%f %d", &startVolume, &days);

    float finalVol = computeVolume(startVolume, days);
    printf("Final Volume: %.2f\n", finalVol);
    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;

float computeVolume(float V, int N) {
    if (N == 0) return V;

    float prevVol = computeVolume(V, N - 1);

    int prob = rand() % 100;
    float currentVol = prevVol;

    if (prob < 30) {
        currentVol = prevVol * 1.01;
        cout << "Day " << N << ": Rainy (Vol: " << fixed << setprecision(2) << currentVol << ")\n";
    } else if (prob < 65) {
        currentVol = prevVol * 0.98;
        cout << "Day " << N << ": Sunny (Vol: " << fixed << setprecision(2) << currentVol << ")\n";
    } else {
        cout << "Day " << N << ": Cloudy (Vol: " << fixed << setprecision(2) << currentVol << ")\n";
    }

    return currentVol;
}

int main() {
    srand(time(0));
    float startVolume;
    int days;

    cout << "Enter initial volume and number of days: ";
    cin >> startVolume >> days;

    float finalVol = computeVolume(startVolume, days);
    cout << "Final Volume: " << fixed << setprecision(2) << finalVol << "\n";
    return 0;
}

Exercise 4: Reverse String

Develop a recursive function named reverseString() that takes a String s and prints it in reverse.

Notice that the first character of the reverse is the last character of the original string.

In main(), you need to input a string from the user and call the function to display the reversed version.

Example:

Enter a string: structure
Reversed: erutcurts

Solution

#include <stdio.h>

void printReverse(char str[], int n) {
    if (n == 0) {
        return;
    }
    printf("%c", str[n - 1]);
    printReverse(str, n - 1);
}

int main() {
    char word[100];
    printf("Enter the string: ");
    scanf("%s", word);
    
    int length, i = 0;
    while (word[i] != '\0') {
        i++;
    }
    length = i;
    
    printf("Reversed: ");
    printReverse(word, length);
    printf("\n");
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

void printReverse(const string& str, int n) {
    if (n == 0) return;
    cout << str[n - 1];
    printReverse(str, n - 1);
}

int main() {
    string word;
    cout << "Enter the string: ";
    cin >> word;

    cout << "Reversed: ";
    printReverse(word, word.length());
    cout << "\n";
    return 0;
}

Exercise 5: Max Element in Array

Write a recursive function named findMax() that finds the maximum number in an array of integers.

In main(), define an array (e.g., [10, 5, 20, 8]) or ask the user to fill one, and print the maximum value found by your function.

Example:

Enter number of elements: 4
Enter elements: 10 5 20 8 
Max number is: 20

Solution

#include <stdio.h>

int findMax(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }

    int mx = findMax(arr, n - 1);

    if (arr[n - 1] > mx) {
        return arr[n - 1];
    } else {
        return mx;
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("Max number is: %d\n", findMax(arr, n));
    return 0;
}

#include <iostream>
using namespace std;

int findMax(int arr[], int n) {
    if (n == 1) return arr[0];
    int mx = findMax(arr, n - 1);
    return (arr[n - 1] > mx) ? arr[n - 1] : mx;
}

int main() {
    int n;
    cout << "Enter number of elements: ";
    cin >> n;

    int arr[n];
    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) cin >> arr[i];

    cout << "Max number is: " << findMax(arr, n) << "\n";
    return 0;
}

Exercise 6: Find the Output

Consider the following recursive function. What will be the output if fun(3) is called?

void fun(int n) {
    if (n == 0)
        return;
    printf("%d ", n);
    fun(n - 1);
    printf("%d ", n);
}

void fun(int n) {
    if (n == 0)
        return;
    cout << n << " ";
    fun(n - 1);
    cout << n << " ";
}

Solution

Expected output: 3 2 1 1 2 3

Expected output: 3 2 1 1 2 3

Exercise 7: Find the Output

Consider the following recursive function. What will be the output if fun(4, 3) is called?

int fun(int x, int y) {
    if (x == 0)
        return y;
    return fun(x - 1, x + y);
}

Solution

Expected output: 13

Expected output: 13

Exercise 8: Print Sequence

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

\[3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\]

Your task is to simulate the execution of the algorithm for a given value of n.

Example

Input:
3

Output:
3 10 5 16 8 4 2 1

Solution

#include <stdio.h>

void calc(int n) {
    printf("%d ", n);
    if (n == 1) {
        return;
    }
    if (n % 2 == 0) {
        calc(n / 2);
    } else {
        calc(3 * n + 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    calc(n);
    return 0;
}

#include <iostream>
using namespace std;

void calc(int n) {
    cout << n << " ";
    if (n == 1) return;
    if (n % 2 == 0) {
        calc(n / 2);
    } else {
        calc(3 * n + 1);
    }
}

int main() {
    int n;
    cin >> n;
    calc(n);
    return 0;
}

Exercise 9: Calculate the Power of a Number

Write a function that takes a base x and an exponent y, and returns x to the power of y.

Solution

#include <stdio.h>

int power(int x, int y) {
    if (y == 0) return 1;
    return x * power(x, y - 1);
}

int main() {
    int base, exp;
    printf("Enter base: ");
    scanf("%d", &base);
    printf("Enter exponent: ");
    scanf("%d", &exp);
    printf("Result: %d\n", power(base, exp));
    return 0;
}

#include <iostream>
using namespace std;

int power(int x, int y) {
    if (y == 0) return 1;
    return x * power(x, y - 1);
}

int main() {
    int base, exp;
    cout << "Enter base: ";
    cin >> base;
    cout << "Enter exponent: ";
    cin >> exp;
    cout << "Result: " << power(base, exp) << endl;
    return 0;
}

Exercise 10: Count Specific Digits

Write a function that counts how many times a specific digit appears in a number (e.g., counting how many 7s are in 7071 should return 2).

Solution

#include <stdio.h>

int countDigits(int num, int target) {
    if (num == 0) 
        return 0;
    int lastDigit = num % 10;
    if (lastDigit == target) 
        return 1 + countDigits(num / 10, target);
    else 
        return countDigits(num / 10, target);
}

int main() {
    int num, target;
    printf("Enter a number: ");
    scanf("%d", &num);
    printf("Enter digit to count: ");
    scanf("%d", &target);
    printf("Count: %d\n", countDigits(num, target));
    
    return 0;
}

#include <iostream>
using namespace std;

int countDigits(int num, int target) {
    if (num == 0) 
        return 0;
    int lastDigit = num % 10;
    if (lastDigit == target) 
        return 1 + countDigits(num / 10, target);
    else 
        return countDigits(num / 10, target);
}

int main() {
    int num, target;
    cout << "Enter a number: ";
    cin >> num;
    cout << "Enter digit to count: ";
    cin >> target;
    cout << "Count: " << countDigits(num, target) << endl;
    
    return 0;
}

Exercise 11: Count Occurrences of an Item

Write a function that takes an array and a target value, and returns how many times that target value appears in the array.

Solution

#include <stdio.h>

int countOccurrences(int arr[], int size, int target) {
    if (size == 0) 
        return 0;
    
    if (arr[size - 1] == target)
        return 1 + countOccurrences(arr, size - 1, target);
    else
        return countOccurrences(arr, size - 1, target);
}

int main() {
    int size;
    printf("Enter number of elements: ");
    scanf("%d", &size);
    
    int arr[size];
    printf("Enter elements: ");
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    
    int target;
    printf("Enter target: ");
    scanf("%d", &target);
    
    printf("Count: %d\n", countOccurrences(arr, size, target));
    
    return 0;
}

#include <iostream>
using namespace std;

int countOccurrences(int arr[], int size, int target) {
    if (size == 0) 
        return 0;
    
    if (arr[size - 1] == target)
        return 1 + countOccurrences(arr, size - 1, target);
    else
        return countOccurrences(arr, size - 1, target);
}

int main() {
    int size;
    cout << "Enter number of elements: ";
    cin >> size;
    int arr[size];
    cout << "Enter elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }
    int target;
    cout << "Enter target: ";
    cin >> target;
    cout << "Count: " << countOccurrences(arr, size, target) << endl;
    return 0;
}

Exercise 12: Count the Vowels in a String

Write a recursive function that takes a string and returns the total number of vowels (A, E, I, O, U) inside it.

Solution

#include <stdio.h>

int countVowels(char str[], int index) {
    if (str[index] == '\0') {
        return 0;
    }
    char ch = str[index];
    int isVowel = (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
                   ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') ? 1 : 0;
    return isVowel + countVowels(str, index + 1);
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);
    
    printf("Number of vowels: %d\n", countVowels(str, 0));
    return 0;
}

#include <iostream>
using namespace std;

int countVowels(char str[], int index) {
    if (str[index] == '\0') {
        return 0;
    }
    char ch = str[index];
    int isVowel = (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
                   ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U') ? 1 : 0;
    return isVowel + countVowels(str, index + 1);
}

int main() {
    char str[100];
    cout << "Enter a string: ";
    cin >> str;
    
    cout << "Number of vowels: " << countVowels(str, 0) << endl;
    return 0;
}

Exercise 13: Check if an Array is Sorted

Write a recursive function that takes an array of numbers and returns True if it is sorted in ascending order, and False if it isn’t.

Solution

#include <stdio.h>

int isSorted(int arr[], int size) {
    if (size == 0 || size == 1) 
        return 1;
    if (arr[size - 1] < arr[size - 2])
        return 0;
    return isSorted(arr, size - 1);
}

int main() {
    int size;
    printf("Enter number of elements: ");
    scanf("%d", &size);
    
    int arr[size];
    printf("Enter elements: ");
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    
    if (isSorted(arr, size)) {
        printf("Array is sorted.\n");
    } else {
        printf("Array is not sorted.\n");
    }
    
    return 0;
}

#include <iostream>
using namespace std;

bool isSorted(int arr[], int size) {
    if (size == 0 || size == 1)
        return true;
    if (arr[size - 1] < arr[size - 2])
        return false;
    return isSorted(arr, size - 1);
}

int main() {
    int size;
    cout << "Enter number of elements: ";
    cin >> size;
    
    int arr[size];
    cout << "Enter elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }
    
    if (isSorted(arr, size)) {
        cout << "Array is sorted." << endl;
    } else {
        cout << "Array is not sorted." << endl;
    }
    
    return 0;
}

Exercise 14: Binary to Decimal Conversion

Write a recursive function that takes a binary string and returns its decimal equivalent (e.g., "1010" becomes 10).

Solution

#include <stdio.h>
#include <math.h>

int binaryToDecimal(char binary[], int length, int power) {
    if (length == 0) 
        return 0;
    int bit = binary[length - 1] - '0';
    return bit * (int)pow(2, power) + binaryToDecimal(binary, length - 1, power + 1);
}

int main() {
    char binary[100];
    printf("Enter a binary number: ");
    scanf("%s", binary);
    
    int length = 0;
    while (binary[length] != '\0') {
        length++;
    }
    
    printf("Decimal representation: %d\n", binaryToDecimal(binary, length, 0));
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

int binaryToDecimal(char binary[], int length, int power) {
    if (length == 0) 
        return 0;
    int bit = binary[length - 1] - '0';
    return bit * (int)pow(2, power) + binaryToDecimal(binary, length - 1, power + 1);
}

int main() {
    char binary[100];
    cout << "Enter a binary number: ";
    cin >> binary;
    
    int length = 0;
    while (binary[length] != '\0') {
        length++;
    }
    
    cout << "Decimal representation: " << binaryToDecimal(binary, length, 0) << endl;
    return 0;
}

Exercise 15: Count Subsequences with Target Sum

Write a recursive function CountSubsequences() that receives an integer array, its size, current index, current running sum, and a target sum. The function should calculate and return the number of subsequences (contiguous or non-contiguous) of the array whose elements add up to the target sum.

In main(), read the number of elements and fill the array. Then read the target sum, call the recursive function, and print the resulting count.

Example:

Enter number of elements: 3
Enter 3 elements: 1 2 3
Enter target sum: 3
Number of subsequences: 2

Solution

#include <stdio.h>

int CountSubsequences(int arr[], int size, int index, int currentSum, int targetSum) {
    if (index == size) {
        return currentSum == targetSum ? 1 : 0;
    }

    int take = CountSubsequences(arr, size, index + 1, currentSum + arr[index], targetSum);
    int dontTake = CountSubsequences(arr, size, index + 1, currentSum, targetSum);

    return take + dontTake;
}

int main() {
    int size, targetSum;
    int arr[50];

    printf("Enter number of elements: ");
    scanf("%d", &size);

    printf("Enter %d elements: ", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

    printf("Enter target sum: ");
    scanf("%d", &targetSum);

    int count = CountSubsequences(arr, size, 0, 0, targetSum);
    printf("Number of subsequences: %d\n", count);

    return 0;
}

#include <iostream>
using namespace std;

int CountSubsequences(int arr[], int size, int index, int currentSum, int targetSum) {
    if (index == size) {
        return currentSum == targetSum ? 1 : 0;
    }

    int take = CountSubsequences(arr, size, index + 1, currentSum + arr[index], targetSum);
    int dontTake = CountSubsequences(arr, size, index + 1, currentSum, targetSum);

    return take + dontTake;
}

int main() {
    int size, targetSum;
    int arr[50];

    cout << "Enter number of elements: ";
    cin >> size;

    cout << "Enter " << size << " elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    cout << "Enter target sum: ";
    cin >> targetSum;

    int count = CountSubsequences(arr, size, 0, 0, targetSum);
    cout << "Number of subsequences: " << count << endl;

    return 0;
}