Laboratory: Recursion

Gábor Horváth / Zsolt Kohári · 2020.11.19.

All the tasks involve recursive functions.

It is very important to trace your program, watch your call stack and your variables. It is especially interesting for the Fibonacci program.

Preparation for lab:

  • Review lecture topics on recursion.

1. Arithmetic sequence

We can get any element of an arithmetic sequence (arithmetic progression) by adding the common difference to the previous element:

an = an-1 + d

Considering the sequence as a function, realize a recursive function than returns the nth element of the sequence! The parameters of the function are: arithmetig_seq(n, start, diff), the sequence number of the required element, the starting value and the difference. What shall be the base case for this recursion?

Realize a similar (recursive) function that returns the nth element of a geometric sequence. The definition is very similar to AP but a quotient is given and multiple instaed of add:

bn = bn-1 · q

Complete the program to print the first 10 elements of the sequences! For arithmetic, the base case is 1 and it is increasing by 5, for geometric sequence the first element is 2 and the multiplication factor is 2.

    1     6     11    16    21    26    31    36    41    46 
    2     4     8     16    32    64   128   256   512  1024

Solution

The base case for either sequence is that the very first element is the start value. 

#include <stdio.h>

double arithmetic(int n, double start, double diff) {
    if (n == 0)
        return start; /*base case*/
    else
        return diff + arithmetic(n - 1, start, diff);
}

double geometric(int n, double start, double quot) {
    if (n == 0)
        return start; /*base case*/
    else
        return quot * geometric(n - 1, start, quot);
}
 
 
int main(void) {
    for (int n = 0; n < 10; ++n)
        printf("%g  ", arithmetic(n, 1, 5));
    printf("\n");
    
    for (int n = 0; n < 10; ++n)
        printf("%g  ", geometric(n, 2, 2));
    printf("\n");
	return 0;
}

2. Fibonacci

The Fibonacci-series is defined as: F0=0, F1=1, Fn=Fn-1+Fn-2. Write a recursive function to calculate the nth element! Test your function for n=40! What happens? (Hint: remember the lecture topic.)

Trace your program in the debugger. Start it and see how it works for n=5. You may implement your own tracing method: your fib() function should first print the value of the parameter (n).

Solution

#include <stdio.h>

/* Fibonacci series */
int fib(int n) {
    /* base cases (terminating terms) */
    if (n == 0) return 0; /* element 0. is 0 */
    if (n == 1) return 1; /* element 1. is 1 */

    /* general term */
    return fib(n - 1) + fib(n - 2); /* the nth element is the sum of the previous two */
}

int main(void) {
    for (int i = 0; i < 40; i++)
        printf("%d\n", fib(i));

    return 0;
}

3. Printing text

Test the following two functions. What is the difference between the two functions? What is the difference between the outputs? (putchar(c) prints a single character like printf("%c",c) would do.) 

#include <stdio.h>

void print_string_1(char *text) {
    if (text[0] == '\0')
        return;
    putchar(text[0]);
    printf("%s", text + 1);     // !
}


void print_string_2(char *text) {
    if (text[0] == '\0')
        return;
    putchar(text[0]);
    print_string_2(text + 1); // !
}


int main(void) {
    print_string_1("word");
    print_string_2("word");
    
    return 0;
}

4. Array forwards and backwards

Write a recursive function to print the elements of an array a) forwards b) backwards. Both functions should receive the array and its size on the parameter list. Create in main an array of five, and another one of ten integers (initialized). Call both functions for both arrays.

Solution

#include <stdio.h>

void array_print_forward(int a[], int n) {
  if(n > 0) {                      /* If it is not empty */
    printf("%d ", a[0]);           /* Print first element */
    array_print_forward(a+1, n-1); /* Print rest of the array by calling the same function */
                                   /* such that we pass a pointer to the next element */
  }
}

void array_print_backward(int a[], int n) {
  if(n > 0) {                       /* If it is not empty */
    array_print_backward(a+1, n-1); /* Print the array except the first element, backwards */
    printf("%d ", a[0]);            /* Print first element */
  }
}

int main(void) {
    int a5[] = {1,2,3,4,5}, a10[] = {1,2,3,4,5,6,7,8,9,10};

    array_print_forward(a5, 5); printf("\n");
    array_print_backward(a5, 5); printf("\n");
    array_print_forward(a10, 10); printf("\n");
    array_print_backward(a10, 10); printf("\n");

    return 0;
}

5. Numeral system

Write a function that takes two parameters: a positive integer value, and the base of a numeral system. Print the value in the given numeral system. Why is the solution much simpler using recursion than an iterative solution?

Hint

To print for example 1234 in base 10 numeral system first the 1234/10 (123) should be printed, and then the 1234%10 (4). Using recursion it is easy to reverse the order of printing.

Solution

#include <stdio.h >

/* This works for numeral systems with base r<=10  */
void convert(int n, int r) {
    /* If n>r, recursive call */
    if (n / r > 0)
        convert(n / r, r);
    /* print the remainder (last digit) */
    printf("%d", n % r);
}

/* This version can make use of the whole English alphabet (up to base 36) */
void convert2(int n, int r) {
    char *s = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    /* If there are more digits to print, recursive call */
    if(n / r > 0)
        convert2(n / r, r);
    /* print the remainder (last digit) */
    putchar(s[n % r]);
}

int main(void) {
    convert(27, 5);  /* 102 */
    printf("\n");
    convert(13, 2);  /* 1101 */
    printf("\n");
    convert2(64519, 16);  /* FC07 */

    return 0;
}

6. Pretty print numbers

Write a function that prints the positive integer received as a parameter in an easy to read format: form groups of three digits and separate them by spaces. Example: 16 077 216. Test for other values, too: 999, 1000, 12, 0, 1000222.

Hint

Use recursion, it is the same as printing in base 1000 numeral system.

To printf 3 digits with leading zeros use %03d in the format string.

Solution

#include <stdio.h>

void printnum(int n) {
    /* If we have more than 3 digits */
    if (n / 1000 > 0) {
        printnum(n / 1000);        /* Cut last 3 digits and call the function recursively */
        printf(" %03d", n % 1000); /* Print a space and the last 3 digits */
    }
    else
        printf("%d", n);           /* Otherwise we print the number without modifications */
}

int main(void) {
    printnum(16077216);

    return 0;
}

7. Further problems for practicing

Try to write the iterative solution (no recursion but loops) of the above problems. Which algorithms are easy to implement this way, and which ones are hard?