Recursion

2078 Chaitra

Explain how recursive uses stack data structure. Usage of factorial of number calculation to illustrate the concept.

Solution:

Recursion uses a stack to keep track of function calls. Each call creates a new stack frame with local variables and return addresses. The stack follows Last In, First Out (LIFO), ensuring functions return in reverse order of calls.

#include <stdio.h>

int fibo(int n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fibo(n - 1) + fibo(n - 2);
    }
}

int main() {
    int n;

    printf("Enter value of n for series: ");
    scanf("%d", &n);

    printf("The Fibonacci series up to %d terms is:\n", n);
    for (int i = 1; i <= n; i++) {
        printf("%d ", fibo(i));
    }

    return 0;
}

2078 Poush

Explain different types of recursion. Construct a recursion tree for Tower of Hanoi with 3 disks.

Solution:

The different types of recursion are:

• Direct Recursion: A function calls itself within the definition of the function through direct recursion.
• Indirect Recursion:In indirect recursion, a function calls another function, which in turn calls the first function. This creates a cycle of function calls.
• Tail Recursion: A recursive function is tail recursion , when recursive call is the last thing executed by the function. so, when nothing is left to do after comming back from the recursive call.
• Head Recursion:In head recursion, the recursive call is made before any other operations in the function. This means that the function must complete all recursive calls before it can start processing the results.
• Linear Recursion:In linear recursion, the function makes a single recursive call, and each call processes a smaller portion of the problem until a base case is reached.
• Tree Recursion:In tree recursion, the function makes multiple recursive calls, creating a branching structure. This is often used in problems like calculating Fibonacci numbers or traversing trees.
• Nested Recursion:In nested recursion, a recursive function calls another recursive function. This can lead to complex scenarios where multiple levels of recursion are involved.

Here's the recursion tree for 3 disks:

2078 Baisakh

How recursive algorithm uses STACK to store intermediate results, illustrate with an example? Distinguish between normal function and recursive function.

Solution:

When a recursive function is called, the computer uses a stack to remember which function call it is currently processing. Each time the function is called, a new stack frame is created and added to the top of the stack. This frame contains the function's local variables, parameters and the return address. Sample

#include <stdio.h>

int factorial(int n) {
    if (n == 0) {
        return 1;  // Base case: factorial of 0 is 1
    } else {
        return n * factorial(n - 1);  // Recursive case
    }
}

int main() {
    int n = 5;
    printf("Factorial of %d is: %d\n", n, factorial(n));
    return 0;
}

Difference Between Recursive Function and Normal Function

2072 Ashwin

Do you think recursive function is slow? Compare recursive and non-recursive functions. Draw recursion tree for Tower of Hanoi assuming 4 disks.

Solution:

Yes, recursive functions can be slow due to repeated calculations and high memory usage (stack frames). However, they can be optimized with memoization or tail recursion.

2066 Bhadra

Explain recursion with its disadvantages? Draw the recursive tree diagram for the fibonacci sequence : fib(5)

Solution:

The process in which the function call itself directly or indirectly is called recursion. Some of the disadvantages of recursion are:

• It is difficult to trace the logic of the function.
• It consumes more storage space than other techniques such as Iteration, Dynamic programming etc.
• Each function called will occupy memory in stack. Which will lead to stack overflow.
• If base condition is not set properly then it may create a problem such as a system crash, freezing etc.,

2065 Shrawan

'A function or a object calls itself', Explain this statement using the idea behind it. Give recursive algorithm for Fibonacci series and TOH (tower of honoi).

Solution:

A function calling itself is recursion, used to solve problems by breaking them into smaller parts. An object referencing itself is self-referencing, common in data structures like linked lists. Both rely on self-replication for efficiency.

Algorithm for Fibonacci series:

START
Procedure fibonacci(int n)  {
  if(n == 0 or n == 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}
END

Algorithm for Tower of Hanoi (TOH):

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     
      move disk from source to dest          
      Hanoi(disk - 1, aux, dest, source)     
   END IF
   
END Procedure
STOP

Here's the recursion tree for 4 disks: