APS105 Textbook 11.4 Recursion Exercises

Question 5 in Fall 2013 Final Exam (Easy)

Consider the recursive C function factorial below. Give the printed output of the function that is produced if the function is called with an argument of 4.

int factorial(int n) {
  printf("ENTER: %d\n", n);
  int ret;
  if (n == 0 || n == 1)
    ret = 1;
  else
    ret = n * factorial(n - 1);
  printf("EXIT: %d\n", n);
  return ret;
}

My answer

ENTER: 4
ENTER: 3
ENTER: 2
ENTER: 1
EXIT: 1
EXIT: 2
EXIT: 3
EXIT: 4

BONUS: What is the returned value?

My answer

ret = 24

Question 10 in Fall 2013 Final Exam (Intermediate)

Write a function called revStr that makes use of recursion to reverse the characters of a string. The reversal should happen two elements at a time, from the ends to the centre of the string. The function prototype is given below. Parameter str is the string to be reversed and parameter len is the length of the string. For example, if the function is called with the string "Hello", it must reverse the characters so that the string contains "olleH".

void revStr(char *str, int len);

My answer

#include <stdio.h>

void revStr(char *str, int len) {
	// recursive function
	
	if (len < 2) return; // base step
	
	// recursive step
	len = len - 1;
	char tmp = *str;
	*str = str[len];
	str[len] = tmp;
	revStr(str + 1, len - 1);
}

int main(void) {
	// this part wasn't asked for, but I gave it anyways just to test the code
	char reverse[6] = {'b', 'r', 'u', 'h', 's', '\0'};
	revStr(reverse, 5);
	printf("reversed string of \"bruhs\": %s\n", reverse);
	return 0;
}

Explanation of the function

Line 6: if (len < 2) return;

This is the base step, and in the base step there is no logic to be performed so it just ends the function call; you can just return nothing if it's a void function.

You subtract 1 from len and then set the leftmost character in the string to character at index len in the string. This is necessary because the rightmost character is at index of len - 1, not len.

= temp

Setting the leftmost character in the string equal to the rightmost character.

Line 13: revStr(str + 1, len - 1)

This is the recursive step. You add 1 to str, which effectively feeds the string into the function with a starting index that is 1 greater than before. Additionally, you feed in a length that is 1 less than before (2 less than the original value fed into the function due to the len = len - 1 line) to match the change in the starting index.