Ejercicios Recusión y Complejidad

01. [análisis de recursión]

Determina el output de foo(0,5). Analiza su complejidad.

void foo(int n, int m)  {
  if (n < m) {
      for (int i = 0; i < m; i++) {
          if (i > n) cout << "*";
          else       cout << " ";
      }
  }
}

02. [complejidad recursiva]

Determina la complejidad de fah. La función partition devuelve un índice entre low y high y requiere exactamente n pasos, donde n = high - low + 1

int fah(int A[], int low, int high, int kth) {
    int i;
    i = partition(A[], low, high);
    if (i == kth)     return A[i];
    else if (i > kth) fah(A, low, i-1);
    else              fah(A, i+1, high);
}

03. [complejidad recursiva]

The following recursive function can be used to count the nodes of a singly linked list.

int count (Node *c) {
  if (!c) return 0;

  return 1 + count (c->next);
}

Find recursive T(n) of count, then convert to non-recursive form to estimate Big-Oh notation.

04. [complejidad recursiva]

The following function divides an array a[l], …, a[r] to a[l], …, a[m] and a[m+1], …, a[r]. Then, it finds the maximum element in each of the two parts (recursively), and returns the larger of the two as a maximum element in the overall array. If the array size is even, both parts have the same size. However, if it is odd, the sizes of the two parts of the array differ by 1. Also, it is worth mentioning that for the data type ‘Item’, we must have overloaded the comparison operator ‘>’ to run the following function.

Item max (Item a[], int l, int r) {
  if (l == r) return a[l];

  int m = (l+r) / 2; 

  Item u = max (a, l, m);
  Item v = max (a, m+1, r);

  if (u > v)
    return u;
  else
    return v;
}

Find the recursive T(n) of this function, then convert to the non-recursive form to estimate Big-Oh notation.

05. [complejidad recursiva]

The following “divide and conquer” recursive function can be used to design marks on a ruler. More specifically, to design the marks on a ruler, we first design the appropriate signs in the left half, then the longest mark in the middle, and then the appropriate signs in the right half.

void rule (int l, int r, int h) {
  int m = (l+r) / 2;

  if (h > 0) {
    rule (l, m, h-1);
    mark (m, h); // painting function.
    rule (m, r, h-1);
  }
}

Asume that the mark(m,h) function draws a vertical line of of height h at x = m. Describe the type of marks produced by this function. For example, run it with rule(0,16, 3).

Determine the recursive T(n), then convert to non-recursive form.

06. [complejidad recursiva]

The following recursive function can be used to generate a sequence of Fibonacci numbers. This implementation, however, is a better solution than the previous one because it retains memory (Dynamic Programming) from which it can derive the results directly in future calls without having to recalculate a sequence from the beginning.

int F (int i) {
  static int knownF[maxN];

  if (knownF[i] != 0) return knownF[i];

  int t = i;

  if (i < 0) return 0;

  if (i > 1) t = F (i-1) + F (i-2);

  return knownF[i] = t;
}

Determine the recursive T(n), then convert to non-recursive form.

07. [analizar función recursiva]

Determina el output haciendo hand-tracing.

int suspense ( int n, int &x ) {
    int rr, qq;

    if ( n <= 1 ){
        x = 1;
        return 1;
    }

    rr = suspense ( n-1, x );

    qq = rr + x;
    x = rr;

    return qq;
}

int main() {
    int x = 0;
    cout << suspense(4, x) << endl;
    cout << x << endl;
    return 0;
}

08. [analizar función recursiva]

Determina el output haciendo hand-tracing.

void funny(int n) {
    if(n > 0) {
        funny(n-2);
        cout << n << " ";
        funny(n-2);
    }
}

int main() {
    funny(5);
    return 0;
}

09. [analizar función recursiva]

Determina el output haciendo hand-tracing.

#include<stdio.h>
int uy(int n) {
    cout <<  n << endl;
    if(n < 3) {
        uy(uy(uy(++n)));
    }
    return n;
}

int main() {
    uy(1);
    return 0;
}

10. [analizar función recursiva]

Determina el output haciendo hand-tracing.

int what(int a, int b) {
    if (b == 0)
        return 0;
    if (b % 2 == 0)
        return what(a+a, b/2);

    return what(a+a, b/2) + a;
}

int main() {
    cout << what(4,3);
    return 0;
}

Many of these exercises taken from: https://efxa.org/2011/03/31/recursive-functions/