Recursion - ISC Class 12 Computer Science Questions with Answers, Page 2

quiz(36922) returns 3 (verified by running the code for real). Dry run: quiz(36922) = (36921%2) + quiz(3692) = 1 + quiz(3692) quiz(3692) = (3691%2) + quiz(369) = 1 + quiz(369) quiz(369) = (368%2) + quiz(36) = 0 + quiz(36) quiz(36) = (35%2) + quiz(3) = 1 + quiz(3) quiz(3) = (2%2) + quiz(0) = 0 + quiz(0) quiz(0) = 0 (base case, n<=1) Unwinding: quiz(3)=0, quiz(36)=1, quiz(369)=1, quiz(3692)=2, quiz(36922)=3 Return value: 3

Apart from recursion, at each call the function decrements n by 1 and, if that decremented value is odd, adds 1 to a running total; it then continues on the value obtained by discarding the last digit of the decremented value (integer division by 10), repeating until the remaining value is <= 1. It finally returns the total count of decremented values that were odd along this chain.

task(30, 45): m < n, so it calls task(30, 45 - 30) = task(30, 15) task(30, 15): m > n, so it calls task(30 - 15, 15) = task(15, 15) task(15, 15): m == n, so it returns 15 The function returns 15.

It finds the HCF (GCD) of m and n by repeated subtraction.

import java.util.*;
class Gcd
{
    int num1, num2;

    Gcd()
    {
        num1 = 0;
        num2 = 0;
    }

    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter first number: ");
        num1 = sc.nextInt();
        System.out.print("Enter second number: ");
        num2 = sc.nextInt();
    }

    int gcd(int x, int y)
    {
        if (y == 0)
            return x;
        return gcd(y, x % y);
    }

    void display()
    {
        System.out.println("GCD of " + num1 + " and " + num2 + " = " + gcd(num1, num2));
    }

    public static void main(String[] args)
    {
        Gcd ob = new Gcd();
        ob.accept();
        ob.display();
    }
}

The recursive method uses Euclid's algorithm: gcd(x, y) = gcd(y, x % y) until y becomes 0. Sample run: 48 and 18 gives 6.

Direct recursion: a function calls itself directly, e.g. int f(int n) { ... f(n-1) ... }. Indirect recursion: a function calls another function, which in turn calls the first function back, e.g. A() calls B() and B() calls A().

Answer: (b) 12 Toy(56) = 6 + Toy(5) = 6 + (5 + Toy(0)) = 6 + 5 + 1 = 12, since Toy(0) returns 1.

import java.util.*;
class Fibo
{
    int start, end;

    Fibo()
    {
        start = 0;
        end = 0;
    }

    void read()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter start: ");
        start = sc.nextInt();
        System.out.print("Enter end: ");
        end = sc.nextInt();
    }

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

    void display()
    {
        System.out.println("Fibonacci series from " + start + " to " + end + ":");
        int i = 0, t = fibo(0);
        while (t <= end)
        {
            if (t >= start)
                System.out.print(t + " ");
            i++;
            t = fibo(i);
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        Fibo ob = new Fibo();
        ob.read();
        ob.display();
    }
}

fibo(n) is recursive: fibo(0) = 0, fibo(1) = 1, otherwise the sum of the previous two terms. display() prints the terms that lie between start and end. Sample run: start 2, end 50 gives 2 3 5 8 13 21 34.

Iteration uses less memory and is usually faster, because it does not create a new stack frame for every repeated call as recursion does (so there is no risk of stack overflow).

Dry run for test(4) (count is reduced by --count before the recursive call, so the line printed after the call shows the reduced value): test(4): count is not 0, prints Bye4, then count becomes 3 and test(3) is called test(3): prints Bye3, count becomes 2, calls test(2) test(2): prints Bye2, count becomes 1, calls test(1) test(1): prints Bye1, count becomes 0, calls test(0) test(0): count == 0, prints a blank line (a space) and returns Back in test(1): prints " 0" Back in test(2): prints " 1" Back in test(3): prints " 2" Back in test(4): prints " 3" Output: Bye4 Bye3 Bye2 Bye1 (blank line) 0 1 2 3 (verified by running the code)

Dry run for n = 25: check(25): 25 is odd, so return 1 + check(25/2 + 1) = 1 + check(13) check(13): odd, so 1 + check(13/2 + 1) = 1 + check(7) check(7): odd, so 1 + check(7/2 + 1) = 1 + check(4) check(4): even, so 1 + check(2) check(2): even, so 1 + check(1) check(1): n <= 1, so return 1 Unwinding: check(2) = 1 + 1 = 2; check(4) = 1 + 2 = 3; check(7) = 1 + 3 = 4; check(13) = 1 + 4 = 5; check(25) = 1 + 5 = 6 Return value for n = 25: 6 Dry run for n = 10: check(10): even, so 1 + check(5) check(5): odd, so 1 + check(5/2 + 1) = 1 + check(3) check(3): odd, so 1 + check(3/2 + 1) = 1 + check(2) check(2): even, so 1 + check(1) check(1): returns 1 Unwinding: check(2) = 2; check(3) = 1 + 2 = 3; check(5) = 1 + 3 = 4; check(10) = 1 + 4 = 5 Return value for n = 10: 5 (i) n = 25 returns 6; (ii) n = 10 returns 5 (verified by running the code).

num=43629, x=3, y=4 (verified by running the code for real: it returns 76) Dry run (z is the last/units digit of num at each call): Mystery(43629,3,4): num≥10, z=43629%10=9 (odd) → return 9*4 + Mystery(4362,3,4) = 36 + Mystery(4362,3,4) Mystery(4362,3,4): z=4362%10=2 (even) → return 2*3 + Mystery(436,3,4) = 6 + Mystery(436,3,4) Mystery(436,3,4): z=436%10=6 (even) → return 6*3 + Mystery(43,3,4) = 18 + Mystery(43,3,4) Mystery(43,3,4): z=43%10=3 (odd) → return 3*4 + Mystery(4,3,4) = 12 + Mystery(4,3,4) Mystery(4,3,4): num=4<10 → return 4 (base case) Unwinding: Mystery(43,3,4)=12+4=16 Mystery(436,3,4)=18+16=34 Mystery(4362,3,4)=6+34=40 Mystery(43629,3,4)=36+40=76 Return value: 76

The function returns the binary equivalent of n (written as a decimal number). Verified by running the code: magicfun(7) = 111 and magicfun(10) = 1010. Dry run for n = 7: magicfun(7) = magicfun(3)*10 + 7%2 = magicfun(3)*10 + 1 magicfun(3) = magicfun(1)*10 + 3%2 = magicfun(1)*10 + 1 magicfun(1) = magicfun(0)*10 + 1%2 = magicfun(0)*10 + 1 magicfun(0) = 0 (base case) Unwinding: magicfun(1) = 0*10 + 1 = 1; magicfun(3) = 1*10 + 1 = 11; magicfun(7) = 11*10 + 1 = 111 Return value for n = 7: 111 Dry run for n = 10: magicfun(10) = magicfun(5)*10 + 10%2 = magicfun(5)*10 + 0 magicfun(5) = magicfun(2)*10 + 5%2 = magicfun(2)*10 + 1 magicfun(2) = magicfun(1)*10 + 2%2 = magicfun(1)*10 + 0 magicfun(1) = magicfun(0)*10 + 1 = 1 Unwinding: magicfun(2) = 1*10 + 0 = 10; magicfun(5) = 10*10 + 1 = 101; magicfun(10) = 101*10 + 0 = 1010 Return value for n = 10: 1010