Wednesday, July 30, 2014

Practice Questions for Recursion | Set 6 | GeeksforGeeks



Read full article from Practice Questions for Recursion | Set 6 | GeeksforGeeks
Consider the following recursive C function. Let len be the length of the string s and num be the number of characters printed on the screen, give the relation between num and len where len is always greater than 0.
void abc(char *s)
{
    if(s[0] == '\0')
        return;
 
    abc(s + 1);
    abc(s + 1);
    printf("%c", s[0]);   
}
Following is the relation between num and len.
 num = 2^len-1 
s[0] is 1 time printed
s[1] is 2 times printed
s[2] is 4 times printed
s[i] is printed 2^i times
s[strlen(s)-1] is printed 2^(strlen(s)-1) times
total = 1+2+....+2^(strlen(s)-1)
      = (2^strlen(s)) - 1 
For example, the following program prints 7 characters.
#include<stdio.h>
 
void abc(char *s)
{
    if(s[0] == '\0')
        return;
 
    abc(s + 1);
    abc(s + 1);
    printf("%c", s[0]);
}
 
int main()
{
    abc("xyz");
    return 0;
}
Question 2
#include<stdio.h>
int fun(int count)
{
    printf("%d\n", count);
    if(count < 3)
    {
      fun(fun(fun(++count)));
    }
    return count;
}
 
int main()
{
    fun(1);
    return 0;
}
Output:
 1
 2
 3
 3
 3
 3
 3
The main() function calls fun(1). fun(1) prints “1” and calls fun(fun(fun(2))). fun(2) prints “2” and calls fun(fun(fun(3))). So the function call sequence becomes fun(fun(fun(fun(fun(3))))). fun(3) prints “3” and returns 3 (note that count is not incremented and no more functions are called as the if condition is not true for count 3). So the function call sequence reduces to fun(fun(fun(fun(3)))). fun(3) again prints “3” and returns 3. So the function call again reduces to fun(fun(fun(3))) which again prints “3” and reduces to fun(fun(3)). This continues and we get “3” printed 5 times on the screen.
Read full article from Practice Questions for Recursion | Set 6 | GeeksforGeeks

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts